bzoj1022:[SHOI2008]小约翰的游戏John(Anti-SG游戏)

Author Avatar
Sakits 3月 08, 2018

题解

  这题是一个Anti-SG游戏,顾名思义,它的游戏规则与SG游戏正好相反,即决策集合为空的操作者胜。
  Anti-SG游戏一般使用SJ定理解决

SJ定理

  对于任意一个Anti-SG游戏,如果定义所有子游戏的SG值为00时游戏结束,先手必胜的条件:
  1、游戏的SG值为00且所有子游戏SG值均不超过11
  2、游戏的SG值不为00且至少一个子游戏SG值超过11
  证明见:https://www.cnblogs.com/y-clever/p/6667592.html

  这题每个子游戏的SG值显然就是石子个数,然后用SJ定理解决就行了。

代码

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=500010, inf=1e9;
int T, x, n;
inline void read(int &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;	
} 
int main()
{
	read(T);
	while(T--)
	{
		read(n); int sg=0, flag=0;
		for(int i=1;i<=n;i++) read(x), sg^=x, flag|=(x>1);
		printf("%s\n", sg?(flag?"John":"Brother"):(flag?"Brother":"John"));
	}
}