题意：n堆石子，两人轮流操作，每次操作只能选定其中一堆，并取走若干个（>=1个）。谁取走最后一个谁输。给定一个状态，问先取的赢还是后取的赢。
分析：看题目类似nim博弈问题。所以想到sg函数，nim的sg是把格堆石子数抑或起来，看是否为0。本题我们就自己写出一些能解决的状态（可以手动判断np状态），观察各堆总数抑或结果和必胜必败态的联系。发现一个规律，sg函数为0则必胜，否则必败。只有一种特殊情况不符合该规律，就是所有堆都为1。
在网上看到了一篇证明，在此复制过来，简单加工一下。
不管全0的最后必胜态（好像没影响）
于是规定的必胜态为：
1.所有的都是1，异或结果为0。。。。1状态
2.有大于1的，异或结果不为0。。。。2状态
必败态为：
1.所有的都是1，异或结果不为0。。。。3状态
2.有大于1的，异或结果为0。。。。。。4状态
根据定义，证明一种判断position的性质的方法的正确性，只需证明三个命题：
1、这个判断将所有terminal position判为P-position；
2、根据这个判断被判为N-position的局面一定可以移动到某个P-position；
3、根据这个判断被判为P-position的局面无法移动到某个P-position。 （有点归纳的意思）
最终必败态为只有1个，就是只有1个石子，符合。
对状态1和3，显然成立
状态之间的主要转化在于: 1状态和3状态相互转化。 2状态和4状态相互转化。
对于2状态：
假设异或结果为x。
当x=1时，肯定是最低位为1的堆有奇数个，只要在这些最低位为1的堆中选择一个取走1个石子，就可将最低位为1的堆数变为偶数，抑或结果变为0。其中一个最低位1的操作，并不会让任何一个大于1的堆消失。因此不会导致状态1。抑或结果为0，不会导致状态3，而会变为状态4。
当x>1时：
{
x与一个在x最高位是1且其余位均为0的数（设导致最高位为1的堆为a）异或后结果设为y，即y是将x的最高位由1改为0后得到的数字。
y=0时
{
其它的堆全为1个石子时，将a堆减为1，满足3状态。
如果其它堆中有大于石子数1的，将a堆取走若干，使得的a堆最高位变为0其他位不变，就满足4状态了。
}
y=1时
{
其它的堆全为1个石子时，将a堆取走若干，使得的a堆最高位变为0其他位不变，满足3状态。
如果其它堆中有石子数大于1的，将a堆取走若干，使得的a堆最高位变为0并使得最低位为1，其他位不变，就满足4状态了
}
y>1时，就将a堆的最高位减少使得其余位恰好与y相同（这是可以做到的，因为a堆最高位为1的数，大于y），使得抑或结果为0，满足4状态。
}
对于4状态，它不能变为另一个异或结果为0的（不能变为4状态）。而且异或结果为0就不可能只有一个大于1的堆，所以也不能变为3状态.所以只能变为必胜态。
所以它也满足。
综上，所以这个条件是符合的
View Code
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
usingnamespace std;
int main()
{
//freopen("t.txt", "r", stdin);
int t;
scanf("%d", &t);
while (t--)
{
int sg =0, n;
bool flag =false;
scanf("%d", &n);
for (int i =0; i < n; i++)
{
int a;
scanf("%d", &a);
sg ^= a;
if (a !=1)
flag =true;
}
if ((flag && sg) || (!flag &&!sg))
printf("John\n");
else
printf("Brother\n");
}
return0;
}