题解 P4279 【[SHOI2008]小约翰的游戏】
DQYdqy
2019-01-03 21:06:00
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;
}
```