洛谷P4279 [SHOI2008]小约翰的游戏（Anti-Nim）

题目描述

小约翰经常和他的哥哥玩一个非常有趣的游戏：桌子上有 n 堆石子，小约翰和他的哥哥轮流取石子，每个人取的时候，可以随意选择一堆石子，在这堆石子中取走任意多的石子，但不能一粒石子也不取，我们规定取到最后一粒石子的人算输。

小约翰相当固执，他坚持认为先取的人有很大的优势，所以他总是先取石子，而他的哥哥就聪明多了，他从来没有在游戏中犯过错误。小约翰一怒之前请你来做他的参谋。自然，你应该先写一个程序，预测一下谁将获得游戏的胜利。

输入格式

本题的输入由多组数据组成，第一行包括一个整数 T（1≤T≤500），表示输入总共有 TT 组数据。

每组数据的第一行包括一个整数 N（1≤N≤50），表示共有 NN 堆石子，接下来有 N个不超过 5000 的整数，分别表示每堆石子的数目。

输出格式

对于每组数据，如果约翰能赢得比赛，则输出 John，否则输出 Brother，请注意单词的大小写。

输入输出样例

输入 #1复制

2
3
3 5 1
1
1

输出 #1复制

John
Brother

Anti-Nim游戏。考虑如下的情况：

1. 所有石子均为1，此时n为奇数先手必败，反之必胜。

2. 仅有一堆石子大于1，此时若n - 1为奇数，则先手可以直接将这堆石子取完；若n - 1为偶数，则先手可以将这堆石子取至仅剩一颗，变成第一种情况。此时先手必胜。

3. 两堆及以上石子数大于1，由于石子数单调递减，因此总会在某个时刻转换为第二种情况（注意没有为1的石子堆也算在第二种情况里），此时面临这种情况的玩家必胜。因为第二种情况的异或值必然不为0，如果我们将第三种情况的所有石子堆异或起来得到的值不为0，说明先手可以取某一堆的石子将异或值变为0（类似普通nim），此时后手面临的就是异或值为0的情况，后手不管怎么取都会将异或值变为非0值（见普通nim的证明，利用异或的消去律），又因为总会在某个时刻转换为第二种情况，故面临第二种情况的必为先手。因此可以知道当为第三种情况时，所有石子异或值不为0则先手必胜，反之先手必败。

   #include <bits/stdc++.h>
   using namespace std;
   int n, a[5005];
   int main() {
   	int t;
   	cin >> t;
   	while(t--) {
   		cin >> n;
   		int cnt = 0;
   		int x = 0;
   		for(int i = 1; i <= n; i++) {
   			cin >> a[i];
   			if(a[i] == 1) cnt++;
   			x ^= a[i];
   		}
   		if(cnt == n) {
   			if(cnt & 1) {
   				cout << "Brother" << endl;
   			} else {
   				cout << "John" << endl;
   			}
   		} else if(cnt == n - 1) {
   			cout << "John" << endl;
   		} else {
   			if(x == 0) {
   				cout << "Brother" << endl;
   			} else {
   				cout << "John" << endl;
   			}
   		}
   	}
   	return 0;
   }