Description

小約翰經(jīng)常和他的哥哥玩一個非常有趣的游戲：桌子上有n堆石子，小約翰和他的哥哥輪流取石子，每個人取的時候，可以隨意選擇一堆石子，在這堆石子中取走任意多的石子，但不能一粒石子也不取，我們規(guī)定取到最后一粒石子的人算輸。小約翰相當(dāng)固執(zhí)，他堅持認(rèn)為先取的人有很大的優(yōu)勢，所以他總是先取石子，而他的哥哥就聰明多了，他從來沒有在游戲中犯過錯誤。小約翰一怒之前請你來做他的參謀。自然，你應(yīng)該先寫一個程序，預(yù)測一下誰將獲得游戲的勝利。

Input

本題的輸入由多組數(shù)據(jù)組成，第一行包括一個整數(shù)T，表示輸入總共有T組數(shù)據(jù)（T小于等于500）。
每組數(shù)據(jù)的第一行包括一個整數(shù)N（N小于等于50），表示共有N堆石子
接下來有N個不超過5000的整數(shù)，分別表示每堆石子的數(shù)目。

Output

每組數(shù)據(jù)的輸出占一行，每行輸出一個單詞。
如果約翰能贏得比賽，則輸出“John”，否則輸出“Brother”，請注意單詞的大小寫。

Solution:

在普通的Nim游戲當(dāng)中，若各堆石子數(shù)異或和不為0，則先手必勝
然而在本題中，取走最后的那顆石子人輸
我們來分情況討論
1.若當(dāng)前每堆石子數(shù)都為1,且石子堆數(shù)為奇數(shù),則先手必敗,為偶數(shù),先手必勝
2.若某一堆石子數(shù)>1且各堆石子異或和不為0,則先手必勝
為什么呢？(~不知道......) 我們來推導(dǎo)一下
結(jié)論1是很顯然的,我們就不再做出贅述，如何來證明結(jié)論2呢
根據(jù)普通的Nim游戲可以知道,在先手必勝的情況下,總是有某種策略可以讓局勢重新轉(zhuǎn)換為先手必勝的局勢(先后手在不斷變換),而先手必敗的局勢是只能通向先手必勝的。
又由于我是先手,則在雙方都采取先手必勝->先手必勝的策略的情況下，最后輸?shù)目偸俏摇?br /> 那么轉(zhuǎn)換到本題，在滿足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; }

轉(zhuǎn)載于:https://www.cnblogs.com/NLDQY/p/10216881.html

總結(jié)

以上是生活随笔為你收集整理的[SHOI2008]小约翰的游戏的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。