题解 P4279 【[SHOI2008]小约翰的游戏】
SuperJvRuo
2018-03-13 11:43:26
显然,奇数个1是必败态。我们应该想办法把局面转换成这种必败态。
当“超过1颗石子”的堆数大于1的时候,按照Nim的方法走。直到“超过1颗石子”的堆数等于1,这时将这堆石子全部取掉或剩1颗,保证非空(剩下1颗石子)的堆数为奇数即可胜利。
```
#include<cstdio>
int main()
{
int a,t,N;
scanf("%d",&t);
while(t--)
{
scanf("%d",&N);
int ans=0,sum=0;
for(int i=0;i<N;i++)
{
scanf("%d",&a);
ans^=a;
sum+=a;
}
if(sum==N)
{
printf("%s\n",sum&1?"Brother":"John");
}
else
{
if(ans)
printf("John\n");
else
printf("Brother\n");
}
}
return 0;
}
```