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

VenusM1nT · 2020-10-27 22:15:43 · 题解

这是一道经典的 \textbf{Anti - Nim} 问题。

先说结论：当每堆石子都只有 1 个的时候分奇偶讨论，否则求异或和，若异或和 >0 则先手必胜。
再来尝试口胡一下正确性。

定义“孤单堆”为只有一颗石子的堆，“充裕堆”为石子数 >1 的堆，下面定义若干状态：\text{S/T} 分别代表异或和 \not=0 与 =0 的状态，\text{S}/0/1/2 代表在 \text{S} 状态下充裕堆的数量 =0/=1/\ge2，\text{T}/0/2 代表在 \text{T} 状态下充裕堆的数量 =0/\ge2，没有 \text{T}1 是因为如果充裕堆的数量 =1 则异或和不可能为 0。下有若干推论。

• 显然 \text{S}0 时必败，\text{T}0 时必胜，因为此时是若干孤单堆，\text{S/T} 分别代表奇偶状态。
• \text{S}1 时先手必胜。 若孤单堆为奇数则取走整堆，否则取成孤单堆。

最终得出结论：\text{T0,S1,S2} 时先手必胜，\text{S0,T2} 时先手必败，也就是最上面的结论。
大概就是这个亚子。

#include<bits/stdc++.h>
#define N 50
#define reg register
#define inl inline
using namespace std;
int n,a[N+5];
int main()
{
    reg int Time;
    scanf("%d",&Time);
    while(Time--)
    {
        reg int ans=0;
        reg bool fg=1;
        scanf("%d",&n);
        for(reg int i=1;i<=n;i++)
        {
            reg int x;
            scanf("%d",&x);
            ans^=x;
            fg&=(x==1);
        }
        if(fg) puts(ans?"Brother":"John");
        else puts(ans?"John":"Brother");
    }
    return 0;
}