首页 > 代码库 > HDU-1907-John

HDU-1907-John

题目链接

point this

这一题有点类似于NIM游戏,当符合一定条件的时候,先手可必胜。

这里用到了一个规律。把每一堆的数目进行异或运算(每一堆的数目都是1除外),

最后的结果有两种,为0或不为0,若为0则各堆的二进制位相加不进位以后所得到

的数的各位数一定是一个偶数。我们称结果为0的情况为平衡状态,如果刚开始局

面是一个不平衡状态,即各堆的各位二进制数的和不全为偶数,可判定为先手的必胜残局。

 

举个例子:

下面应用此获胜策略来考虑4-堆的Nim取子游戏。其中各堆的大小分别

为7,9,12,15枚硬币。用二进制表示各数分别为:0111,1001,1100和1111。

于是可得到如下一表:

大小为7的堆  0 1 1 1

大小为9的堆  1 0 0 1

大小为12的堆 1 1 0 0

大小为15的堆 1 1 1 1

 

由Nim取子游戏的平衡条件可知,此游戏是一个非平衡状态的取子游戏,因此,

游戏人I在按获胜策略进行取子游戏下将一定能够取得最终的胜利。具体做法

有多种,游戏人I可以从大小为12的堆中取走11枚硬币,使得游戏达到平衡(如下表),

 

大小为7的堆  0 1 1 1

大小为9的堆  1 0 0 1

大小为12的堆 0 0 0 1

大小为15的堆 1 1 1 1

 

之后,无论游戏人II如何取子,游戏人I在取子后仍使得游戏达到平衡。

同样的道理,游戏人I也可以选择大小为9的堆并取走5枚硬币而剩下4枚,

或者,游戏人I从大小为15的堆中取走13枚而留下2枚。

归根结底,Nim取子游戏的关键在于游戏开始时游戏处于何种状

态(平衡或非平衡)和第一个游戏人是否能够按照取子游戏的获胜策略来进行游戏。

 

做这题很容易被英文描述给弄晕,说白了就是这你懂不懂这个游戏,可是

文章却描述的很烂不知道在说什么,做了好些英文题感觉这种题目挺多的,

这种题目指定要靠你什么知识定理什么的,要是之前做过,那么就会容易理解

题意,那么完成这题也就是不需要理会它题目是怎么描述的了……

 

我的代码

#include<stdio.h>

int main(void)
{
int t,n,a[50],s,f,i;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
s=0;
f=0;
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
s=s+a[i];
}
if(s==n)
{
if(s%2)
printf("Brother\n");
else
printf("John\n");
}
else
{
for(i=0;i<n;i++)
f=f^a[i];
if(f)
printf("John\n");
else
printf("Brother\n");
}
}
return 0;
}

HDU-1907-John