有这样一种取石子游戏: 有若干堆石子,每堆石子的数量都是有限的,合法的操作是“选择一堆石子并拿走若干颗(不能不拿)”;
现在有两种判定胜负的方式:
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 1849Rabbit 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 }
原文链接: https://www.cnblogs.com/jian1573/archive/2013/04/30/3051871.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/86617
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!