Bzoj1022 [shoi2008]小约翰的游戏john

BZOJ水题

Posted by yjjr's blog on February 15, 2018

标签:博弈论

题目

题目传送门

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

Source

Seerc2007

分析

sg函数

百度上有详细的证明

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int T,n;
int main()
{
	T=read();
	while(T--){
		n=read();
		int sg=0,pd=0;
		rep(i,1,n){
			int x=read();
			sg^=x;
			if(x!=1)pd=1;
		}
		if((sg&&pd)||(!sg&&!pd))puts("John");else puts("Brother");
	}
	return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr