111qqz的小窝

老年咸鱼冲锋!

bzoj 2463: [中山市选2009]谁能赢呢? (博弈论)

2463: [中山市选2009]谁能赢呢?

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 1826  Solved: 1347
[Submit][Status][Discuss]

Description

小明和小红经常玩一个博弈游戏。给定一个n×n的棋盘,一个石头被放在棋盘的左上角。他们轮流移动石头。每一回合,选手只能把石头向上,下,左,右四个方向移动一格,并且要求移动到的格子之前不能被访问过。谁不能移动石头了就算输。假如小明先移动石头,而且两个选手都以最优策略走步,问最后谁能赢?

Input

输入文件有多组数据。

输入第一行包含一个整数n,表示棋盘的规模。

当输入n为0时,表示输入结束。

 

Output

对于每组数据,如果小明最后能赢,则输出”Alice”, 否则输出”Bob”, 每一组答案独占一行。

Sample Input

2
0

Sample Output

Alice

HINT

对于所有的数据,保证1<=n<=10000。

 

思路:手写了下几组猜是奇偶性..写了下就过了。

证明:

首先对于n是偶数,一定能被1*2的骨牌覆盖!所以从起点开始,先手一定走的是骨牌的另一端,后手一定走的是骨牌的前一端,因此无论何时,先手总是可以走。因此先手必胜。

如果n是奇数,那么去掉一格后一定能被1*2的骨牌覆盖,但是先手从左上角走,就进入了这个S态(必胜态),那么和上边的分析一样了,因此先手必败。

 

 

 

.

bzoj 1874: [BeiJing2009 WinterCamp]取石子游戏 (sg函数,要求输出第一步具体方案)

 

1874: [BeiJing2009 WinterCamp]取石子游戏

Time Limit: 5 Sec  Memory Limit: 162 MB
Submit: 726  Solved: 296
[Submit][Status][Discuss]

Description

小H和小Z正在玩一个取石子游戏。 取石子游戏的规则是这样的,每个人每次可以从一堆石子中取出若干个石子,每次取石子的个数有限制,谁不能取石子时就会输掉游戏。 小H先进行操作,他想问你他是否有必胜策略,如果有,第一步如何取石子。

Input

输入文件的第一行为石子的堆数N 接下来N行,每行一个数Ai,表示每堆石子的个数 接下来一行为每次取石子个数的种类数M 接下来M行,每行一个数Bi,表示每次可以取的石子个数,输入保证这M个数按照递增顺序排列。

Output

输出文件第一行为“YES”或者“NO”,表示小H是否有必胜策略。 若结果为“YES”,则第二行包含两个数,第一个数表示从哪堆石子取,第二个数表示取多少个石子,若有多种答案,取第一个数最小的答案,若仍有多种答案,取第二个数最小的答案。

Sample Input

4
7
6
9
3
2
1
2
 

Sample Output

YES
1 1
Hint
样例中共有四堆石子,石子个数分别为7、6、9、3,每人每次可以从任何一堆石子中取出1个或者2个石子,小H有必胜策略,事实上只要从第一堆石子中取一个石子即可。

数据规模和约定
数据编号 N范围 Ai范围 数据编号 N范围 Ai范围
1 N=2 Ai≤10 6 N≤10 Ai≤10
2 N=2 Ai≤1000 7 N≤10 Ai≤100
3 N=3 Ai≤100 8 N≤10 Ai≤1000
4 N≤10 Ai≤4 9 N≤10 Ai≤1000
5 N≤10 Ai≤7 10 N≤10 Ai≤1000
对于全部数据,M≤10,Bi≤10

HINT

Source

 

思路:有没有解直接sg函数搞。关键在于输出具体方案。

如果存在某个i,在第i堆取走了ok[j]个石头后,恰好使得sum的值变成0(也就是使得从N态到P态的值)

取这样的i和ok[j]中最小的(i是第一关键字,ok[j]是第二关键字)

需要注意的是,在第i堆取走ok[j]之后的sg值 应该为 sum^sg[a[i]]^sg[a[i]-ok[j]],而不是直接sum^sg[a[i]-ok[j]]

可以理解成先撤销了之前计算的a[i]的操作,换成qu

 

hdu 3980 Paint Chain (sg函数,环形串取石子)

hdu 3980 题目链接
题意:一个有n个石子的环形串,初始没有被涂颜色,两个人轮流,涂连续m个没有被涂色的石子,不能操作的人为负。问先手是否有必赢策略。

思路:和hdu2999很像。。所不同的是。。。那道题是线型的珠子。。。这道题是环型的数字。。。

然而我们机智得发现。。。环形的任意涂一次。。就变成了线型的啊orz。。。

所以先随便取一次,然后剩下的n-m个按照线型串的方法搞,划分区间即可。

由于先随便取了一次,所以和线型的交换输赢的结论。。。

以及。。要特判一次都不能取的情况。。。2A

 

 

 

 

hdu 2999 Stone Game, Why are you always there? (sg函数,线性串取石子)

hdu2999题目链接

题意:有一串石子,给定一个集合S,每次只能拿连续x个石子,石子必须是在集合S中的数,问先手是否有必赢策略。需要注意石子的位置是不能变化的,也就是说如果一串连续的石子因为中间有石子被取走,那么这段石子就变成不连续的了,也就不能一次取走。

思路:一开始没有读懂题。需要特别强调的是。石子的位置是不能合并的。。

举个例子,如果我有5个石子,S={2},那么我取完一次剩下的情况是 {3,4,5}或者{1},{4,5}或者{1,2},{5}或者{1,2,3} 一共四种。

题意搞清楚以后就好做了。。类似于bomb game那道题。。我们仍然可以把取一次的操作拆分两个子过程,也就是两个区间。我们不关心区间具体的情况,只关心区间的长度。以及,取完只有一个区间的情况不需要特殊考虑,认为是长度为0就可以了,因为sg[0]为0,不影响答案。

 

 

 

 

hdu 2873 Bomb Game(Sg函数)

hdu 2873题目链接

题意:n*m个格子,有若干炸弹。对于在第一行或者第一列的炸弹,爆炸后会到那一行或者那一列的更前面(总的来说就是更靠近左上角)的位置。对于其他位置的炸弹,爆炸后会生成两个炸弹,分别到那一行的更前面或者那 一列的更前面。问先手是否有必赢策略。

 

思路: 不会做2333
参考了 参考博客1
参考博客2

大概明白了一点。整个游戏可以分为若干个炸弹的游戏的和,而实际上一个不在边界行或者列的炸弹,依然可以继续分,分成两个炸弹的和。而位于(i.j)的炸弹,分成两个炸弹的和,有(i-1)*(j-1)种方案(这个不重要2333)

处于边界行或者列的点的sg值我们是可以知道的。。因为规则单一。。和移动等价。。

然后根据边界来进一步处理一般的情况。。

有点类似dp的思想。。。?

 

 

hdu 2509 Be the Winner (anti-sg,sg函数,sj定理)

hdu2509题目链接
题意:???

思路:同1907

 

 

BZOJ 1022 ||hdu 1907 John (sg函数,sj定理,anti-sg)

hdu1907题目链接

题意:n堆石子,每次选一堆,最少拿一个,最多拿光那一堆,拿走最有一个的人输。  问是否有必胜策略。

思路:anti-nim问题。。。

要用到sj定理(是啥。。。?)

参考资料:参考博客

 

SJ定理

对于任意一个Anti-SG游戏,如果定义所有子游戏的SG值为0时游戏结束,先手必胜的条件:
1、游戏的SG值为0且所有子游戏SG值均不超过1。
2、游戏的SG值不为0且至少一个子游戏SG值超过1。

 

 

hdu 1730 Northcott Game (二维sg函数)

hdu 1730

题意:n行格子,每行m个,每行有一黑一白两个棋子,给定初始位置,先手执黑棋,后手执白棋,每次可以在同一行内向左移动,不能超过边界,且不能越过对方的棋子,同一个格子只能有一个棋子。问先手是否必赢。

 

思路:可以看成n个独立的游戏的 叠加。。。所以最后异或和一下就好。。

我们来求sg函数。。。一开始的是想把点对hash成一个数。。。然后发现其实没必要。。。直接二维就好了。。

由于初始化的时候要考虑最大。。。所以sg函数的值会有一个便宜。。。和设定N有关。。减去偏移就好了。。。(我的代码里这个偏移是11026)

1A蛤蛤蛤

 

 

 

 

 

 

 

 

hdu 1404 Digital Deletions (博弈论,根据定义)

hdu 1404题目链接

题意:一个数字串,每次可以选择一位减少任意大小到一个非负数,或者清除一个0以及该位右边的所有数字。问是否有必胜策略。。

思路:定义来搞。。所有能一步走到p点的都是n点,那么如果我们现在知道p点,就可以反过来推n点。。

看到一些人强行把变量名起成sg就说自己用了sg函数也是笑死我了呵呵呵呵

 

hdu 1536 S-Nim (sg函数)

hdu 1536题目链接

题意:还是若干堆石子,但是每次取的个数只能是集合S中有的数。。问是否必赢。。。

思路:sg函数。。。1A

 

 

 

hdu 1517 A Multiplication Game (博弈论,将点的局势对应到段)

hdu 1517 题目链接

题意:初始为1,每次可以乘2..9中的一个数,最先达到或者超过n的人胜利。问谁有必赢策略。。

思路:一开始想用sg函数。。然而n太大(4e10)。。。绝对会超时。。。

所以可以更朴素得,去画n点和p点。。。我们可以发现。。。连续一段的局势是相同的。。。所以不能,也没必要找到每一个点对应的局势。

[n,+oo]是p点,那么[n/9,n-1]是n点,那么[n/9/2,n/9)又是p点。。。以此类推。。

这道题同时也告诉我们。。。没有什么方法是万能的。。。就算sg函数很神。。也有不能用的时候。。。所以掌握最本质的东西还是很重要的。。。

 

转载一段题解:

这道题如果用sg函数,利用点的局势做一定会超时,因为相同的局势能够形成连续的段,所以我们可以将局势对应到段来达到一定的优化:

首先题目中能够了解到必败态[n,+oo),那么可以由此推出必胜态

必胜态就是[n/9,n-1],也就是有一定有策略达到必败态

另一个必败态就是[n/9/2,n/9),之后就是一直循环这样的局势,找到了循环,我们可以固定一个点,固定区间的左端点比较易操作,也就是我们通过固定左端点找到1在必胜态区间,还是必败态区间.

 

hdu 1848 Fibonacci again and again (sg函数)

hdu 1848题目链接

 

题意:三堆石头,每次任选一堆取,取的石子数目必须是斐波那契数列中的数(1,2,3,5,8….)问先手是否有必赢策略。

 

思路:sg函数即可。。。。这次sg函数的优越性终于体现出来了。。。其他方法估计很难写吧。。

以及,这道题不知道为什么让我联想到了生成函数。。。感觉生成函数和sg函数作为工具还是有不少共同点的。。。

 

 

hdu 1850 Being a Good Boy in Spring Festival (nim游戏问必胜方案数,sg函数)

hdu1850题目链接
题意:n堆石子。。每堆可以取任意多个。。。先取完的赢。。问先手能否赢。。能赢的话第一步有几种取法。。
思路:sg函数。。对于方案数,可以用nim游戏的结论。

未命名。设异或和为sum..那么统计满足 a[i]^sum<a[i]的个数就是第一步能走的方案数。

以及。。sg函数。。如果走的步数是任意的。。也就是没有限制。。。那么sg[i] = i…此时也就退化成了一般的nim游戏。。。

 

 

hdu 1847 Good Luck in CET-4 Everybody! (巴什博奕,找规律||sg函数)

hdu1847题目链接
题意:n个石子,每次只能取2的幂次个。。。问先手是否有必赢策略。。。
思路:画n点p点。。。发现n为3的倍数的时候先手必输。。。否则先手必赢。。。

也可以利用sg函数求解。。。
从这里我们可以看出,sg函数类似于母函数,本身并不是一类问题,而是一种求解问题的工具。

nim游戏以及证明过程

参考资料  (后面的证明写错了,差评,不要看,看图就好了)

 

  1. 题目1:今有若干堆火柴,两人依次从中拿取,规定每次只能从一堆中取若干根,

 

可将一堆全取走,但不可不取,最后取完者为胜,求必胜的方法。

 

题目2:今有若干堆火柴,两人依次从中拿取,规定每次只能从一堆中取若干根,

 

可将一堆全取走,但不可不取,最后取完者为负,求必胜的方法。

 

嘿嘿,这个游戏我早就见识过了。小时候用珠算玩这个游戏:第一档拨一个,第二档拨两个,依次直到第五档拨五个。然后两个人就轮流再把棋子拨下来,谁要是最后一个拨谁就赢。有一次暑假看见两个小孩子在玩这个游戏,我就在想有没有一个定论呢。下面就来试着证明一下吧

 

先解决第一个问题吧。

 

定义:若所有火柴数异或为0,则该状态被称为利他态,用字母T表示;否则,

 

为利己态,用S表示。

 

[定理1]:对于任何一个S态,总能从一堆火柴中取出若干个使之成为T态。

 

证明:

 

    若有n堆火柴,每堆火柴有A(i)根火柴数,那么既然现在处于S态,

 

      c = A(1) xor A(2) xor … xor A(n) > 0;

 

    把c表示成二进制,记它的二进制数的最高位为第p位,则必然存在一个A(t)(注:我觉得应该是必然存在奇数个),它二进制的第p位也是1。(否则,若所有的A(i)的第p位都是0,这与c的第p位就也为0矛盾)。

 

    那么我们把x = A(t) xor c,则得到x < A(t).这是因为既然A(t)的第p位与c的第p位同为1,那么x的第p位变为0,而高于p的位并没有改变。所以x < A(t).而

 

    A(1) xor A(2) xor … xor x xor … xor A(n) (需要注意的是,这里是没有A(t)这一项的,前面之所以要说明x<A(t),表达的意思是,之前是A(t),现在取了一个正数A(t)-x到x

 

  = A(1) xor A(2) xor … xor A(t) xor c xor … xor A(n)

 

  = A(1) xor A(2) xor… xor A(n) xor A(1) xor A(2) xor … xor A(n)

 

  = 0

这就是说从A(t)堆中取出 A(t) – x 根火柴后状态就会从S态变为T态。证毕

未命名