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

Ark_ · 2019-03-18 12:00:12 · 题解

题意

反Nim游戏,两人轮流选一堆石子拿,拿到最后一个的输.问先手是否必胜.

分析

怎么说,分类讨论?

• 情形1:首先考虑最简单的情况,所有石子数都为1.那么奇数堆石子为必败,偶数为必胜

• 情形2:然后考虑只有一堆石子>1.那么先手一定可以通过拿完这一堆石子或者是留下一个石子,使得剩下的全部是1.而这两种操作后的局面一种是奇数个1,一种是偶数个1.所以先手一定可以留给后手奇数个1的局面,从而让后手必败,先手必胜.

• 情形3:那么如果有多堆石子>1呢?可以发现,不管怎么拿,因为石子数在减少,一定会有某个人在某个时刻面临情况2(只有一堆石子大于1),那么他就必胜了.那我们来看看这种情况有什么特征.

  于是这就是常见的Nim游戏套路,将所有石子数异或起来后,情形2得到的值一定>0.因为>1的那一堆石子在二进制中除去末位一定还至少有一个1.所以说这时只要异或和>0就表示必胜.

  由于异或和为0的情况任意取都会变成异或和>0的情况,而异或和>0的情况一定有一种取石子方案使得异或和为0.那么异或和为0就表示了必败状态,而>0就表示必胜状态.

所以这道题首先特判一下情形1,然后只用异或起来看等不等于0就行了.

(我在想Anti-SG是不是可以看作两个人都希望对方赢而斗智斗勇的普通SG...)

CODE

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
template<typename T>void read(T &num) {
    char ch; int flg=1;
    while((ch=getchar())<'0'||ch>'9')if(ch=='-')flg=-flg;
    for(num=0;ch>='0'&&ch<='9';num=num*10+ch-'0',ch=getchar());
    num*=flg;
}
int n, x;
int main() {
    int T; read(T);
    while(T--) {
        read(n);
        int ans = 0, sum = 0;
        for(int i = 1; i <= n; ++i) {
            read(x), ans ^= x;
            sum += (x==1);
        }
        if(sum == n) puts((n&1) ? "Brother" : "John");
        else puts(ans ? "John" : "Brother");
    }
}