【题目链接】
点击打开链接
【思路要点】
SJ定理：若把SG游戏中SG函数为0的状态定义为必胜状态，那么状态是先手必胜当且仅当下述条件同时成立或同时不成立：1、\(SG_{S}=0\)2、\(\forall x\in S\ SG_{x}≤1\)然后就做完了。时间复杂度\(O(TN)\)。
【代码】
#include<bits/stdc++.h>
using namespace std;
#define MAXN 5005
int main() {
int T; cin >> T;
while (T--) {
int n; cin >> n;
int ans = 0, cnt = 0;
for (int i = 1; i <= n; i++) {
int x; cin >> x;
ans ^= x;
if (x > 1) cnt++;
}
if ((ans == 0) ^ (cnt == 0)) printf("Brother\n");
else printf("John\n");
}
return 0;
}
