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游戏。。。

 

 

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态。证毕

未命名

hdu 1849Rabbit and Grass(一维nim游戏,sg函数)

Rabbit and Grass

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3058    Accepted Submission(s): 2261

Problem Description

大学时光是浪漫的,女生是浪漫的,圣诞更是浪漫的,但是Rabbit和Grass这两个大学女生在今年的圣诞节却表现得一点都不浪漫:不去逛商场,不去逛公园,不去和AC男约会,两个人竟然猫在寝食下棋……
说是下棋,其实只是一个简单的小游戏而已,游戏的规则是这样的:
1、棋盘包含1*n个方格,方格从左到右分别编号为0,1,2,…,n-1;
2、m个棋子放在棋盘的方格上,方格可以为空,也可以放多于一个的棋子;
3、双方轮流走棋;
4、每一步可以选择任意一个棋子向左移动到任意的位置(可以多个棋子位于同一个方格),当然,任何棋子不能超出棋盘边界;
5、如果所有的棋子都位于最左边(即编号为0的位置),则游戏结束,并且规定最后走棋的一方为胜者。

对于本题,你不需要考虑n的大小(我们可以假设在初始状态,棋子总是位于棋盘的适当位置)。下面的示意图即为一个1*15的棋盘,共有6个棋子,其中,编号8的位置有两个棋子。

大家知道,虽然偶尔不够浪漫,但是Rabbit和Grass都是冰雪聪明的女生,如果每次都是Rabbit先走棋,请输出最后的结果。

 

Input
输入数据包含多组测试用例,每个测试用例占二行,首先一行包含一个整数m(0<=m<=1000),表示本测试用例的棋子数目,紧跟着的一行包含m个整数Ki(i=1…m; 0<=Ki<=1000),分别表示m个棋子初始的位置,m=0则结束输入。

 

Output
如果Rabbit能赢的话,请输出“Rabbit Win!”,否则请输出“Grass Win!”,每个实例的输出占一行。

 

Sample Input
2
3 5
3
3 5 6
0

 

Sample Output
Rabbit Win!
Grass Win!

 

Author
lcy

 

Source
是一个略有变形的nim游戏模型
如果在i位置上有 k个棋子
我们可以看做有k堆数量为i的堆
可以向左移动1~i步
就可以看做每次从数量为i的堆中拿走数量1~i
这样就是nim游戏.
而nim游戏的结论是..异或和为0必败.

同样,我们可以用sg函数来解决。
m个棋子可以认为是m个1个棋子的游戏的和。
而游戏的和的sg值就是所有子游戏的sg值的异或。

 

 

bestcoder #56 div 2 C Clarke and puzzle (nim游戏 树状数组)

比赛的时候没过.还以为是树状数组写残了.
但实际上是有自己不知道的东西.
这种博弈叫 nim游戏
所以这是一个二维的nim游戏.
nim游戏的性质是xor 和为0必败,否则必胜.
xor和也有前缀和性质,所以可以用树状数组维护.