博弈论
一看题,哇这不是Nim游戏么= =直接异或起来……啊咧怎么不对?
这道题是【Anti-Nim】,普通的Nim是取走最后一个就赢,这题是取走最后一个输……
做法参见 2009年贾志豪论文《组合游戏略述——浅谈SG游戏的若干拓展及变形》
/**************************************************************
Problem: 1022
User: Tunix
Language: C++
Result: Accepted
Time:16 ms
Memory:1272 kb
****************************************************************/ //BZOJ 1022
#include<cstdio>
#include<iostream>
#define F(i,j,n) for(int i=j;i<=n;++i)
using namespace std; int getint(){
int v=,r=; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-;
for(;isdigit(ch);ch=getchar()) v=v*+ch-'';
return v*r;
}
/*******************template********************/ int main(){
int T=getint();
while(T--){
int n=getint(),x=,y=;
bool sign=;
F(i,,n){
y=getint();
x^=y;
if (y>) sign=;
}
if ((sign && !x) || (!sign && x)) puts("John");
else puts("Brother");
}
return ;
}