【BZOJ】1022: [SHOI2008]小约翰的游戏John（博弈论）

http://www.lydsy.com/JudgeOnline/problem.php?id=1022

好神的博弈论。

题解见dzy的blog：http://dzy493941464.is-programmer.com/posts/39629.html

orz

题目1：有n堆石子，第i堆有A(i)颗石子。两人依次从中拿取，规定每次只能从一堆中取若干根，可将一堆全取走，但不可不取，最后取完者为胜，求必胜的方法。

令C=A(1) xor A(2) xor A(3) xor ... xor A(n)，若C>0，则记为利己态，用S表示，若C=0，则记为利他态，用T表示。

【定理1】对于一个S态，一定能从一堆石子中取出若干个，使其成为T态。

【证明】既然是S态，则此时C>0，我们要使得C变为0。

设C转化为二进制后，最高位的1是第p位。那么一定存在一个A(t)的二进制最高位的1是第p位。（显然，不然C的第p位不可能是1）

然后，把第t堆石子的个数变为x=A(t) xor C。因为A(t)和C的二进制最高位的1是同一位。那么异或之后这一位就变成了0。那么x一定小于A(t)。

此时的C'=A(1) xor A(2) xor ... xor A(t) xor C xor A(t+1) xor ... xor A(n)。把C带进去，得到

C'=A(1) xor A(2) xor ... xor A(n) xor A(1) xor A(2) xor ... xor A(n)。显然C'=0。

所以，只要在第t堆石子中取出A(t)-x颗石子，就把S态变为了T态。

【定理2】对于一个T态，从任意一堆取任意个石子出来，都会变为S态。

【证明】用反证法。设此时第i堆的石子数变成了A(i')。此时C=0。如果C'>0，那么命题就成立了。

假设C'=0。则C'=A(1) xor A(2) xor ... xor A(i') xor... xor A(n)=0。

因为C=0。所以C xor C'=0。则A(1) xor A(2) xor ... xor A(i) xor... xor A(n) xor A(1) xor A(2) xor ... xor A(i') xor... xor A(n)=0。

A(i) xor A(i')=0。A(i)=A(i')明显不对了。所以命题得证。

得到了这两个定理之后，我们可以发现，任何一个S态，我们都可以通过自己的控制将它转化成T态。而对方怎么做都是将T态再转回S态，很被动。所以只要先手是S态，总是可以根据定理1得到的策略获胜。

题目2：有n堆石子，第i堆有A(i)颗石子。两人依次从中拿取，规定每次只能从一堆中取若干根，可将一堆全取走，但不可不取，最后取完者为负，求必胜的方法。

再来定义几个状态。一堆石子里只有一个石子，记为孤单堆。否则记为充裕堆。

在T态中，如果充裕堆的个数大于等于2，记为T2态，1个充裕堆，记为T1态，没有充裕堆，记为T0态。S0、S1、S2同理。

【定理3】在S0态中，若孤单堆的个数为奇数。那必输。T0态必赢。

【证明】也就是奇数个石子，每次取一个。很明显先去的人必输。

【定理4】在S1态中，方法正确就必胜。

【证明】如果孤单堆的个数是奇数，那么就把充裕堆取完；如果是偶数，就把充裕堆取的只剩1根。这样留下的就是奇数个孤单堆，对方先手。由定理3得，对方必输，己方必胜。

【定理5】S2态不可一次变为T0态。

【证明】显然，充裕堆不可能一次从2堆以上变为0。

【定理6】S2态可一次变为T2态。

【证明】由定理1得S态可以一次变为T态，而且不会一次取完整堆，那么充裕堆的个数是不会变的，由定理5得S2态不能一次变为T0态，那么转化的T态是T2态。

【定理7】T2态只能转变为S1或S2态。

【证明】由定理2得，T态一次只能变为S态。由于充裕堆数不会变为0。所以是S1或S2态。

【定理8】在S2态中，只要方法正确，就必胜。

【证明】由定理6得，先转化为T2态。由定理7，对方只能再转化回S1或S2态。由定理4，己方必胜。

【定理9】T2态必输。

【证明】同证明8。

我们得到了几个必胜态：S2，S1，T0。必输态：T2，T1，S0。

比较一下两题：

第一题的过程：S2-T2-S2-T2-.....-T2-S1-T0-S0-T0-...-S0-T0（全0）

第二题的过程：S2-T2-S2-T2-.....-T2-S1-S0-T0-S0-...-S0-T0（全0）

我们可以发现前面的过程是一样的。关键在于得到了S1态之后，怎样抉择使自己获胜。而这个是自己可以掌握的。

因此，我们只需要把T2态留给对方，迟早他会转化成S1态。己方就必胜。

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

#include <queue>

#include <set>

#include <map>

using namespace std;

typedef long long ll;

#define pii pair<int, int>

#define mkpii make_pair<int, int>

#define pdi pair<double, int>

#define mkpdi make_pair<double, int>

#define pli pair<ll, int>

#define mkpli make_pair<ll, int>

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define read(a) a=getint()

#define print(a) printf("%d", a)

#define dbg(x) cout << (#x) << " = " << (x) << endl

#define error(x) (!(x)?puts("error"):0)

#define printarr2(a, b, c) for1(_, 1, b) { for1(__, 1, c) cout << a[_][__]; cout << endl; }

#define printarr1(a, b) for1(_, 1, b) cout << a[_] << '\t'; cout << endl

inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }

inline const int max(const int &a, const int &b) { return a>b?a:b; }

inline const int min(const int &a, const int &b) { return a<b?a:b; }

int main() {

	int T=getint();

	while(T--) {

		int n;

		read(n);

		int t, x=0, k=0;

		for1(i, 1, n) t=getint(), x^=t, k+=t>1;

		int flag=0;

		if((x&&k)||(!x&&!k)) flag=1;

		flag?puts("John"):puts("Brother");

	}

	return 0;

}

Description

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

Input

本题的输入由多组数据组成，第一行包括一个整数T，表示输入总共有T组数据（T≤500）。每组数据的第一行包括一个整数N（N≤50），表示共有N堆石子，接下来有N个不超过5000的整数，分别表示每堆石子的数目。

Output

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

Sample Input

2
3
3 5 1
1
1

Sample Output

John
Brother

HINT

【数据规模】

对于40%的数据，T ≤ 250。

对于100%的数据，T ≤ 500。

Source

Seerc2007

巴特西