题意
反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
#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");
}
}