「BZOJ1022」[SHOI2008]小约翰的游戏

Description

小约翰经常和他的哥哥玩一个非常有趣的游戏:桌子上有n堆石子,小约翰和他的哥哥轮流取石子,每个人取的时候,可以随意选择一堆石子,在这堆石子中取走任意多的石子,但不能一粒石子也不取,我们规定取到最后一粒石子的人算输。小约翰相当固执,他坚持认为先取的人有很大的优势,所以他总是先取石子,而他的哥哥就聪明多了,他从来没有在游戏中犯过错误。小约翰一怒之前请你来做他的参谋。自然,你应该先写一个程序,预测一下谁将获得游戏的胜利。

Input

本题的输入由多组数据组成第一行包括一个整数TT,表示输入总共有TT组数据(T500)(T≤500)。每组数据的第一行包括一个整数N(N50)N(N\leq 50),表示共有NN堆石子,接下来有NN个不超过50005000的整数,分别表示每堆石子的数目。

Output

每组数据的输出占一行,每行输出一个单词。如果约翰能赢得比赛,则输出John,否则输出Brother,请注意单词的大小写。

Sample Input

1
2
3
4
5
2 
3
3 5 1
1
1

Sample Output

1
2
John
Brother

Solution

Orz(yy1695651)
这个问题有一个结论,先手必胜当且仅当:

所有堆的石子数都为11且游戏的SG值为00
有些堆的石子数大于11且游戏的SG值不为00
下面给出证明。 游戏分三种情况:

每个堆只有一个石子

如果异或值=0=0,即有偶数个堆,则先手必胜(A)(A)

如果异或值0\neq 0,即有奇数个堆,则先手必败(B)(B)

只存在一堆石子数>1>1,则先手必胜(C)(C)

可以发现在这种情况下,异或值一定0\neq 0。并且可以发现,在这种情况下先手一定有一种方法使得剩下奇数个石子个数都为1的堆,即转化为BB状态。所以先手必胜。

存在至少22堆石子数>1>1

当异或值=0=0时,先手必败(D)(D)

当异或值0\neq 0时,先手必胜(E)(E)

关于这一步的证明应该把这两个状态结合来看。

首先,参考Nim游戏的证明,当异或值=0=0时,无论进行怎样的操作都会使异或值0\neq 0;而当异或值0\neq 0时,一定存在一种移动方案,使得异或值=0=0,这个性质符合NN,PP状态的转换。

而不断地进行这种转换,总会有一个时刻局面变成了CC状态,而CC状态一定是从DD状态转移过来的。所以可以证明DD状态总会在一个时刻必须转移到先手必胜态,即DD状态是先手必败态。相应地,我们就可以证明EE状态是先手必胜态。

证明结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}



int main() {
int T = read();
while(T--) {
int n = read();
int ans = 0, ct = 0;
for(int i = 1; i <= n; ++i) {
int x = read();
if(x == 1) ++ct;
ans ^= x;
}
if(ct == n) {
if(n & 1) puts("Brother");
else puts("John");
} else {
if(ans) puts("John");
else puts("Brother");
}
}
return 0;
}