题解 P4279 【[SHOI2008]小约翰的游戏】

SuperJvRuo

2018-03-13 11:43:26

Solution

显然,奇数个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; } ```