取石子游戏

有这样一种取石子游戏: 有若干堆石子，每堆石子的数量都是有限的，合法的操作是“选择一堆石子并拿走若干颗（不能不拿）”;

现在有两种判定胜负的方式:

　　1: 如果轮到某个人时所有的石子堆都已经被拿空了，则判负;

　　2: 如果轮到某个人时把所有的石子堆都拿空了, 使下一个人没石子可拿，则判负;

面对第一种判负规则时: 局面是必败态当且仅当所有堆硬币的数量都异或起来结果为0，即a1^a2^...^an=0; 下面是简单说明.

　　首先:最终局面只有一个，就是全0，异或仍然是0;

　　然后:对于某个局面(a1,a2,...,an)，若a1^a2^...^an!=0(不等号就用C++的习惯用!=来表示了)，一定存在某个合法的移动，将ai改变成ai'后满足a1^a2^...^ai'^...^an=0。不妨设a1^a2^...^an=k，则一定存在某个ai，它的二进制表示在k的最高位上是1（否则k的最高位那个1是怎么得到的）。这时ai^k<ai一定成立。则我们可以将ai改变成ai'=ai^k，此时a1^a2^...^ai'^...^an=a1^a2^...^an^k=0。

　　最后:对于某个局面(a1,a2,...,an)，若a1^a2^...^an=0，一定不存在某个合法的移动，将ai改变成ai'后满足a1^a2^...^ai'^...^an=0。因为异或运算满足消去率，由a1^a2^...^an=a1^a2^...^ai'^...^an可以得到ai=ai'。所以将ai改变成ai'不是一个合法的移动;

面对第二种判负规则时 :一种情况下是每堆都是1，那么奇数时先手败, 偶数时后手败,

如果有一堆不都是1,那么结果和前一种结果是一样的;

　　若只有一堆石子数大于1时，总可以对该堆石子操作，使操作后石子堆数为奇数且所有堆得石子数均为1　　
　　若有超过一堆石子数大于1时，先手将最后的异或值变为0即可，这时总还存在某堆石子数大于1

hdu 1849 Rabbit and Grass

链接:http://acm.hdu.edu.cn/showproblem.php?pid=1849

View Code

 1 #include <stdio.h>
 2 int main( )
 3 {
 4     int N;
 5     while( scanf( "%d", &N )==1, N ){
 6         int x, ans;
 7         for( int i=0; i<N; ++ i ){
 8             scanf( "%d", &x );
 9             if( i==0 )
10                 ans=x;
11             else
12                 ans^=x;
13         }
14         if( !ans)
15              puts( "Grass Win!" );
16         else
17              puts( "Rabbit Win!" );
18     }
19     return 0;
20 }

hdu 1907 John

链接:http://acm.hdu.edu.cn/showproblem.php?pid=1907

View Code

 1 #include <cstdio>
 2 
 3 int T, N, x;
 4 int main( )
 5 {
 6     scanf( "%d", &T );
 7     while( T-- ){
 8         scanf( "%d", &N );
 9         int ans=0, f=0;
10         for( int i=0; i<N; ++ i ){
11             scanf( "%d", &x);
12             if( x>1 )f=1;
13             ans^=x;
14         }
15         if(ans)ans=1;
16         if( f^ans )puts( "Brother" );
17         else puts("John" );
18     }
19     return 0;
20 }