题目大意

有n堆石子，每次可以从一堆上取走任意个石子，最后取走石子的人失败，问谁有必胜策略（先手和后手）

数据范围

$t\leqslant 500$，表示有t组数据

题解

游戏结论

先手必胜当且仅当：

• 所有堆的石子数都为$1$且游戏的$SG$值为$0$

• 有些堆的石子数大于$1$且游戏的$SG$值不为$0$

证明

分成四种情况

1.所有堆的石子数都为$1$且游戏的$SG$值为$0$（必胜）

2.所有堆的石子数都为$1$且游戏的$SG$值不为$0$（必输）

3.有些堆的石子数大于$1$且游戏的SG值为$0$（必输）

4.有些堆的石子数大于$1$且游戏的SG值不为$0$（必胜）

前两种情况

如果SG值为0，则有偶数个石子数为$1$的堆，易证此时先手有必胜策略

反之，第二种情况下先手只能把局面转化为第一种情况（必胜局面），则后手有必胜策略

后两种情况

第三种情况下，易证肯定有$n$堆石子数大于$1$（$n\geqslant2$），那么每次操作只能够转移到第四种情况

第四种情况下，若有$n$堆石子数大于$1$。当$n\geqslant2$时，能够转移到第三种情况，当$n=1$时，能够转移到前两种情况

而当先手处于第四种情况下，如果能够转移到前两种情况，那么转移到第二种情况对自己是最有利的，然而如果转移到第三种情况，那么后手只能再转移回来，那么迟早是能够转移到第二种情况的

所以第四种情况是必胜局面，第三种情况是必输局面

组合游戏略述——浅谈SG游戏的若干拓展及变形

程序

#include<cstdio>
#define For(i,l,r) for(int i=l;i<=r;i++)
using namespace std;

int t,n,x,ans,flag;

int main(){
    scanf("%d",&t);
    while(t--){
        flag=0;ans=0;
        scanf("%d",&n);
        For(i,1,n){
            scanf("%d",&x);ans^=x;
            if (x>1) flag=1;
        }
        if ((ans==0)&&(flag==0)) {printf("John\n");continue;}
        if ((ans!=0)&&(flag==1)) {printf("John\n");continue;}
        printf("Brother\n");
    }
    return 0;
}