题解 P4279 【[SHOI2008]小约翰的游戏】

Ark_

2019-03-18 12:00:12

Solution

# 题意 反Nim游戏,两人轮流选一堆石子拿,拿到最后一个的输.问先手是否必胜. # 分析 怎么说,分类讨论? - 情形1:首先考虑最简单的情况,所有石子数都为1.那么奇数堆石子为必败,偶数为必胜 - 情形2:然后考虑只有一堆石子>1.那么先手一定可以通过**拿完这一堆石子**或者是**留下一个石子**,使得剩下的全部是1.而这两种操作后的局面一种是奇数个1,一种是偶数个1.所以先手一定可以留给后手奇数个1的局面,从而让后手必败,先手必胜. - 情形3:那么如果有多堆石子>1呢?可以发现,不管怎么拿,因为石子数在减少,一定会有某个人在某个时刻面临情况2(只有一堆石子大于1),那么他就必胜了.那我们来看看这种情况有什么特征. 于是这就是常见的Nim游戏套路,将所有石子数异或起来后,情形2得到的值一定>0.因为>1的那一堆石子在二进制中除去末位一定还至少有一个1.所以说这时只要异或和>0就表示必胜. 由于异或和为0的情况任意取都会变成异或和>0的情况,而异或和>0的情况一定有一种取石子方案使得异或和为0.那么异或和为0就表示了必败状态,而>0就表示必胜状态. 所以这道题首先特判一下情形1,然后只用异或起来看等不等于0就行了. (我在想Anti-SG是不是可以看作两个人都希望对方赢而斗智斗勇的普通SG...) # CODE ```cpp #include<cstdio> #include<cstring> #include<algorithm> using namespace std; template<typename T>void read(T &num) { char ch; int flg=1; while((ch=getchar())<'0'||ch>'9')if(ch=='-')flg=-flg; for(num=0;ch>='0'&&ch<='9';num=num*10+ch-'0',ch=getchar()); num*=flg; } int n, x; int main() { int T; read(T); while(T--) { read(n); int ans = 0, sum = 0; for(int i = 1; i <= n; ++i) { read(x), ans ^= x; sum += (x==1); } if(sum == n) puts((n&1) ? "Brother" : "John"); else puts(ans ? "John" : "Brother"); } } ```