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

dalao们讲的都太数学了，蒟蒻表示自己真的是太弱了 安利一发博客:[ヾ(≧∇≦*)ゝ](https://www.cnblogs.com/NLDQY/p/10216881.html) **Solution** 在普通的Nim游戏当中，若各堆石子数异或和不为0，则**先手必胜** 然而在本题中，取走最后的那颗石子人输 我们来分情况讨论 1.若当前每堆石子数都为1,且石子堆数为奇数,则先手必败,为偶数,先手必胜 2.若某一堆石子数>1且各堆石子异或和不为0,则先手必胜 为什么呢？(~不知道......) 我们来推导一下 结论1是很显然的,我们就不再做出赘述，如何来证明结论2呢 根据普通的Nim游戏可以知道，在**先手必胜**的情况下，总是有某种策略可以让**局势**重新转换为**先手必胜**的局势(先后手在不断变换)，而**先手必败**的局势是只能通向先手必胜的。 又由于我是先手,则在双方都采取**先手必胜->先手必胜**的策略的情况下，最后输的总是我。 那么转换到本题，在满足2条件的情况下，最后赢得肯定是我。 得证。 **Code:** ``` #include<bits/stdc++.h> #define N 101 using namespace std; int n,a[N]; int read(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();} while(isdigit(ch)){x=x*10+ch-48;ch=getchar();} return x*f; } int main(){ int Case=read(); begin:Case--; if(Case<0)return 0; n=read();memset(a,0,sizeof(a)); for(int i=1;i<=n;i++){ a[i]=read(); a[0]^=a[i]; } sort(a+1,a+n+1); if((a[n]==1&&!a[0])||(a[0]&&a[n]>1))puts("John"); else puts("Brother"); goto begin; } ```