首页 > 代码库 > 【POJ3480】John 博弈 Anti-SG misère规则尼姆游戏

【POJ3480】John 博弈 Anti-SG misère规则尼姆游戏

转载请注明出处:http://blog.csdn.net/vmurder/article/details/42671843
其实我就是觉得原创的访问量比未授权盗版多有点不爽233。。。

题意:跟NIM游戏差不多,不过是谁不能操作了,谁赢。


定理:

NIM游戏规则取最后一个石子输
适用范围:对于任意一个Anti-SG
游戏,当局面中所有的单一游戏
的SG值为0时,游戏结束。
(1)SG==0,有某单一游戏的SG>1。(败)
(2)SG!=0,有某单一游戏的SG>1。(胜)
(3)SG==0,无某单一游戏的SG>1。(胜)
(4)SG!=0,无某单一游戏的SG>1。(败)


代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int T,n,sg,x,k;
for(scanf("%d",&T);T--;)
{
scanf("%d",&n);
for(k=sg=0;n--;)
{
scanf("%d",&x);
k^=x,sg=max(sg,x);
}
if(k){
if(sg>1)puts("John");
else puts("Brother");
}
else {
if(sg<2)puts("John");
else puts("Brother");
}
}
return 0;
}

【POJ3480】John 博弈 Anti-SG misère规则尼姆游戏