Description
小约翰经常和他的哥哥玩一个非常有趣的游戏：桌子上有n堆石子，小约翰和他的哥哥轮流取石子，每个人取的时候，可以随意选择一堆石子，在这堆石子中取走任意多的石子，但不能一粒石子也不取，我们规定取到最后一粒石子的人算输。小约翰相当固执，他坚持认为先取的人有很大的优势，所以他总是先取石子，而他的哥哥就聪明多了，他从来没有在游戏中犯过错误。小约翰一怒之下请你来做他的参谋。自然，你应该先写一个程序，预测一下谁将获得游戏的胜利。
Input
本题的输入由多组数据组成，第一行包括一个整数T，表示输入总共有T组数据（T≤500）。每组数据的第一行包括一个整数N（N≤50），表示共有N堆石子，接下来有N个不超过5000的整数，分别表示每堆石子的数目。
Output
每组数据的输出占一行，每行输出一个单词。如果约翰能赢得比赛，则输出“John”，否则输出“Brother”，请注意单词的大小写。
Sample Input
Sample Output
HINT
【数据规模】
对于40%的数据，T ≤ 250。
对于100%的数据，T ≤ 500。
Source
分析
标准的博弈题的题面……
看起来似乎很像Nim!游戏，只是这里的获胜条件与Nim恰好相反：“取到最后一粒石子的人算输”。我们可以从边界状态考虑：当石子只剩一堆时，若石子总数为1则为必败状态，若石子总数不为1则为必胜状态；当石子有多堆而每堆只有一枚石子时，若各堆石子的异或值为1则为必败状态，否则为必胜状态。
类比Nim游戏的解法，我们发现每堆石子的SG值即为这堆石子的数量。那么我们就可以有这一结论：若各堆石子数量均为1，则SG值为0时是必胜状态。然而当各堆石子不全为1时情况却有所不同：首先，SG值为0时，若先手操作后将SG值变为了SG',根据SG定理中证明的结论，此时游戏中一定存在一个操作可以将SG值恢复为0；但如果先手操作后游戏中仅有一堆石子数量超过1，后手就拥有“将这堆石子取完”和“将这堆石子取到仅剩1个”这两种选择，而由前面的推论，这两种选择一定有一种会将先手送到必败状态中。亦即，状态为“游戏中各堆石子不全为1且SG值不为0”时，接下来要操作的一方占据主动地位。
综上，若各堆石子全为1，则SG值为0时先手必胜；若各堆石子不全为1，则SG值不为0时先手必胜。我们还可以构造出先手必胜时的操作策略：各堆石子不全为1，且SG值不为0时，先手只需判断游戏中石子数不为1的堆的数量是否为1.若只有一堆石子数大于1，则先手应选择“将这堆全部取完”和“将这堆取到只剩1”这两种操作中能够使SG值得到1的操作；若不止一堆石子数大于1，则先手只需将游戏的SG值取到0即可。至于这种操作的可行性，大概在关于SG定理的论文中都可以找到吧。
1 /* ************************************************************* 2 Problem: 1022 3 User: AsmDef 4 Language: C++ 5 Result: Accepted 6 Time:8 ms 7 Memory:804 kb 8 *************************************************************** */ 9 10 /* ********************************************************************* */ 11 /* *********************By Asm.Def-Wu Jiaxin**************************** */ 12 /* ********************************************************************* */ 13 #include <cstdio>
14 #include <cstring>
15 #include <cstdlib>
16 #include <ctime>
17 #include <cctype>
18 #include <algorithm>
19 using namespace std;
20 FILE *
in, *
out;
21 #define SetFile(x) ( in = fopen(#x".in", "r"), out = fopen(#x".out", "w") )
22 #define SetIO(i, o) ( in = i, out = o )
23 #define getc() fgetc(in)
24 template<
class T>inline
void getd(T &x){
25 char ch = getc();
bool neg =
false;
26 while(!isdigit(ch) && ch !=
' - ')ch = getc();
27 if(ch ==
' - ')ch = getc(), neg =
true;
28 x = ch -
' 0 ';
29 while(isdigit(ch = getc()))x = x *
10 -
' 0 ' + ch;
30 if(neg)x = -x;
31 }
32 /* ********************************************************************* */ 33 34 inline
void init(){
35 36 }
37 38 inline
void work(){
39 bool All1;
40 int SG, T, n, i, a;getd(T);
41 while(T--){
42 SG =
0, All1 =
true;
43 getd(n);
44 for(i =
0;i < n;++i){
45 getd(a);
46 if(a >
1)All1 =
false;
47 SG ^= a;
48 }
49 if(((All1) && !SG) || ((!All1) && SG))fprintf(
out,
" John\n ");
50 else fprintf(
out,
" Brother\n ");
51 }
52 }
53 54 int main(){
55 56 #ifdef DEBUG
57 SetIO(fopen(
" test.txt ",
" r "), stdout);
58 #elif !defined ONLINE_JUDGE
59 SetFile();
60 #else 61 SetIO(stdin, stdout);
62 #endif 63 init();
64 work();
65 66 #ifdef DEBUG
67 printf(
" \n%.2lf sec \n ", (
double)clock() / CLOCKS_PER_SEC);
68 #endif 69 return 0;
70 }
博弈论