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

这是一道经典的 $\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{S}2\to\text{T}0$ 为非法，因为不能同时取两堆，但 $\text{S}2\to\text{T}2$ 是合法的。 - $\text{T}2\to\text{S}0$ 为非法，原因同上，但 $\text{T}2\to\text{S}2/1$ 为合法。 - $\text{S}2$ 时先手必胜。先手直接 $\text{S}2\to\text{T}2$，此时若后手 $\text{T}2\to\text{S}2$ 则重复上面的操作，最终后手必然 $\text{T}2\to\text{S}1$，此时先手必胜。 最终得出结论：$\text{T0,S1,S2}$ 时先手必胜，$\text{S0,T2}$ 时先手必败，也就是最上面的结论。 大概就是这个亚子。  ```cpp #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; } ```