转载请注明出处,谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents
by---cxlove
在贾志豪的论文中有提到这种游戏:组合游戏略述——浅谈SG游戏的若干拓展及变形
以下直接引用定理及证明
[定理](SJ定理) 对于任意一个Anti-SG游戏,如果我们规定当局面中所有的单一游戏的SG值为0时,游戏结束,则先手必胜当且仅当:(1)游戏的SG函数不为0且游戏中某个单一游戏的SG函数大于1;(2)游戏的SG函数为0且游戏中没有单一游戏的SG函数大于1。
[证明] 我们只需要证明:
(1) 所有的终止局面为先手必胜局。(这一点显然,证明中略去)
(2) 游戏中的任何一个先手必败局一定只能够转移到先手必胜局;
(3) 游戏中的任何一个先手必胜局一定能够转移到至少一个先手必败局。
情况一:局面的SG函数为0且游戏中某个单一游戏的SG函数大于1。 ∵当前局面的SG函数值为0 又∵SG函数性质(1) ∴它所能转移到的任何一个局面的SG函数值不为0 ① ∵当前局面的SG函数值为0且游戏中某个单一游戏的SG函数大于1。
∴当前局面中必定至少有2个单一游戏的SG函数大于1。 又∵每次至多只能更改一个单一游戏的SG值 ∴它所能转移到的任何一个局面都至少有一个单一游戏的SG值大于1。 ② 由①②得,情况一所能转移到的任何一个局面都为先手必胜局。
情况二:局面的SG函数不为0且游戏中没有单一游戏的SG函数大于1。 显然,当前局面一定有奇数个游戏的SG函数值为1,其余游戏的SG函数值为0。
(1) 将某个单一游戏的SG值更改为大于1的数。
∵转移前没有单一游戏的SG值大与1,转移将某个单一游戏的SG值更改为大于1的数。 ∴转移后的局面一定有且只有一个单一游戏的SG值大于1。 ③ ∴后继局面的SG值一定不为0。 ④ 由③④得,后继局面一定为先手必胜局。
(2) 将某个单一游戏的SG值更改为0或1。
∵转移是将某个SG值为0的单一游戏改成SG值为1的单一游戏,或将某个SG值为1的单一游戏改成SG值为0的单一游戏。 ∴转移后的局面一定有偶数个SG值为1的单一局面且不含有SG值大于1的局面。
∴后继局面一定为先手必胜局。 情况三:局面的SG函数不为0且游戏中某个单一游戏的SG函数大于1。 (1)局面中只有1个单一游戏的SG值大于1。 我们选择更改SG值最大的单一游戏,我们可以选择将其更改成0或1来保证转移后的局面有且只有奇数个SG值为1的单一游戏。
则通过这种方式转以后的局面为先手必败局。 (2)局面中有至少两个单一游戏的SG值大于1。 根据SG函数性质(2),总存在一种决策可以将后继局面的SG函数值变为0 ⑤ ∵局面中有至少两个单一游戏的SG值大于1 又∵每次最多只能更改一个单一游戏的SG值 ∴后继局面中至少有一个游戏的SG值大于1 ⑥ 由⑤⑥得,后继局面为先手必败局。 情况四:局面的SG函数为0且游戏中没有单一游戏的SG函数大于1。
当局面中所有单一游戏的SG值为0时,游戏结束,先手必胜。 否则,局面有且仅有偶数个SG值为1的单一游戏,其余游戏的SG值为0。 我们只需将其中的某一个SG值为1的单一游戏的SG值变为0,游戏中即可出现奇数个SG值为1的单一游戏,到达先手必败局。 综上,证明完毕!
拷贝过来有点乱,直接去看原文吧
总之就是结论(1)游戏的SG函数不为0且游戏中某个单一游戏的SG函数大于1;(2)游戏的SG函数为0且游戏中没有单一游戏的SG函数大于1。
在这个NIM游戏中,SG值便是石子数量
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 10005
#define LL long long
#define inf 1<<29
#define eps 1e-7
using namespace std;
int main(){
int t,n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
int k,cnt=0,ans=0;
while(n--){
scanf("%d",&k);
if(k>1)
cnt++;
ans^=k;
}
if(cnt){
if(ans==0)
puts("Brother");
else
puts("John");
}
else{
if(ans==0)
puts("John");
else
puts("Brother");
}
}
return 0;
}
分享到:
相关推荐
教程来自HDU 的ACM教案,非常好的一个资料
教程来自HDU 的ACM教案,非常好的一个资料
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
可拆卸核心板滤波电容电源指示灯排针复位F103--R10不焊F207--R9不焊第19引脚F103--C4焊0欧姆,C3不焊Tuesday, August 31
排母,核心板接口ADC 电位器扩展接口,预留模拟量Tuesday, August 31, 2021Tuesday, August 31, 2021Tuesday
ACM题库,一些题目和答案,以及解题报告,传上来共享
第一章 功能简介本章介绍HDU-EID-V2开发板的功能,使大家对该开发板的功能及特点有个基本了解。1. 处理器( MCU)HDU-EID-V2 开发板的处理器
基础算法类 ACM 入门 杭电OJ 11页题目题解,算法入门的时候刷题可以参考 搜集整理起来了比单个去搜题解方便快捷
HDU 里面的2000~2099道题目的源码。谢谢支持
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电OnlineJudge 200-2099的解题报告
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
很多经典的杭电oj与poj习题的ac代码与详解!全部ac,决对没有错误的代码!
杭电ACM2000-2099题的解题报告
HDU 1010-2500解题报告,ACMer可以借鉴一下
hdu2000-2014ac代码,虽然只有几道,但都是简单的
杭州电子科技大学ACM Steps中Chapter One-Section One的答案集。不要直接抄哦~~ 如需题解请上我的博客~ 博客地址呈上:http://blog.csdn.net/xu_zh