首页 > 代码库 > 【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规则尼姆游戏
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。