题解 UVA1566 John

题目描述

两个人轮流取石子，每人每次可以 \([1,a_i]\) 个石子，最后取完石子的人为负。问最终谁会赢。

具体思路

• 若堆数为 \(1\) 且该堆数量为 \(1\)，先手必败。

• 若堆数不为 \(1\) 且每堆数量都为 \(1\)，若有奇数堆，先手比败，否则，先手必胜。

• 若堆数不为 \(1\)，转换为 \(Nim\) 游戏，判胜负条件反过来即可。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=51;
int a[N];
int main(){
    int t;scanf("%d",&t);
    while(t--){
        int n,ans=0,sum=0;scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            ans=ans^a[i];
            sum=sum+a[i];
        }
        if(sum==n){
            if(n&1)puts("Brother");
            else puts("John");
        }
        else{
            if(ans)puts("John");
            else puts("Brother");
        }
    }
    return 0;
}