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

GNAQ

2018-12-12 21:03:59

Solution

本文首发于 [随便搞搞 ICG (公平组合游戏) 和其余的博弈](https://fancydreams.ink/2018/11/06/%E9%9A%8F%E4%BE%BF%E6%90%9E%E6%90%9E-icg-%E5%85%AC%E5%B9%B3%E7%BB%84%E5%90%88%E6%B8%B8%E6%88%8F/) (第五页) 欢迎围观 ## 扩展 SG 博弈 - Anti-SG ### 简单的 Anti-Nim 游戏 我们定义 Anti-Nim 游戏: 有 $n$ 堆石子,双方轮流取石子。 - 每次能从其中一堆取出任意数目的石子,不能不取。 - 取走最后一颗石子者败。 不管别的我们先定义: > 如果某堆中只有 $1$ 个石子,则称为孤单堆,否则称为充裕堆。 直接给出结论:先手必胜当且仅当 - 只有偶数个孤单堆; - 存在充裕堆且游戏的 $\mathrm{SG}$ 值不为 $0$ 。 那么接下来要证明结论: 首先第一种情况比较显然,每人每次能做的操作只有拿走一堆石子。 第二种情况呢? 首先考虑当存在多于一个充裕堆时的情况,设当前的局面为 $\mathrm{S}$ ,这时从结论可知 $\mathrm{SG} \ne 0$ ,那么根据 $\mathrm{SG}$ 函数的定义, $ \exists \mathrm{T} \text{ s.t. } \mathrm{S} \rightarrow \mathrm{T} \,,\, \mathrm{SG(T)} \ne 0 $ 。 那么先手让 $\mathrm{S}$ 变为 $\mathrm{T}$ 即可。( 又因为每次只能操作一堆,比较显然地, $\mathrm{T}$ 中一定存在充裕堆。 ) 如果当前局面里只有一堆充裕堆,首先根据 Nim 的异或判定方法,显然此时的 $\mathrm{SG}$ 值不会为 $0$ ,其次,先手总可以把状态变为只有奇数个孤单堆,所以先手必胜。 另外我们还必须说明当存在充裕堆且 $\mathrm{SG}$ 为 $0$ 的时候是先手必败的,那么: 首先至少存在两堆充裕堆。因为按照 Nim 的异或判定方法,充裕堆会影响异或和的高位。所以必然有两堆以上的充裕堆使得高位异或和为 $0$ 。 那么无论先手如何决策, $\mathrm{T}$ 中必然存在一堆以上的充裕堆,根据上文可知此时另一位玩家必胜。 ## 更加复杂的结论 - Anti-SG 给出 Anti-SG 游戏的定义: - Anti-SG 游戏规定,决策集合为 $\oslash$ 的游戏者赢。 - Anti-SG 游戏其他规则与 SG 游戏相同。 对于 Anti-SG 游戏,我们也是先给出定理,再尝试证明。那么这次的定理名字叫做 Sprague Grundy - Jia Zhihao 定理,简称 SJ 定理,它说的是: 对于任意一个 Anti-SG 游戏,如果规定当局面中所有单一游戏的 $\mathrm{SG}$ 值都为 $0$ 时游戏结束,那么先手必胜当且仅当: 1. 游戏的 $\mathrm{SG}$ 不为 $0$ 且 $\exists G_i \in \mathbb{G} \text{ s.t. } \mathrm{SG}(G_i) > 1 $ 。 2. 游戏的 $\mathrm{SG} = 0 $ 且 $\forall G_i \in \mathbb{G} \,,\, \mathrm{SG}(G_i) \leqslant 1 $ 。 证明: 我们还是只需要证明以下三点: Anti-SG 的结束局面为 P-position ; 能转移到 P-position 的局面是 N-position ; 所有合法转移都是 N-position 的局面是 P-position 。 那么我们设当前的局面为 $\mathrm{S}$ ,证明如下: [1] 局面的 $\mathrm{SG} = 0 $ 且 $\exists G_i \in \mathbb{G} \text{ s.t. } \mathrm{SG}(G_i) > 1 $ 。 首先由 SG 定理我们可以知道的是此时存在至少两个单一游戏,他们的 $\mathrm{SG} > 1$ ; 又因为每次只能对一个单一游戏操作,那么$\forall \mathrm{T} \in N(\mathrm{S}) $ , $\mathrm{T} $ 中存在至少一个单一游戏其 $\mathrm{SG} > 1 $ 。 然后根据 SG 函数的性质, $\forall \mathrm{T} \in N(\mathrm{S}) \,,\, \mathrm{SG(T)} \ne 0 $ 。 所以我们证明了在先手的任意操作之后,局面都转移至 SJ 定理中的 $(1)$ ,先手必败。 [2] 局面的 $\mathrm{SG} \ne 0 $ 且 $\forall G_i \in \mathbb{G} \text{ s.t. } \mathrm{SG}(G_i) \leqslant 1$ 。 根据 SG 定理,显然只有奇数个单一游戏其 $\mathrm{SG} =1 $ 且其余单一游戏的 $\mathrm{SG} =0 $ 。 首先,如果将某个单一游戏的 $\mathrm{SG}$ 值改为大于 $1$ 的数,我们可知 游戏的 $\mathrm{SG} \ne 0$ 。 有且仅有一个单一游戏其 $\mathrm{SG} > 1$ 在先手操作之后,游戏转移至 SJ 定理中的 $(1)$ ,先手必败。 其次,将某个单一游戏的 $\mathrm{SG}$ 值改为 $0$ 或 $1$ : 仅有偶数个单一游戏其 $\mathrm{SG} = 1$ ,且其余的单一游戏其 $\mathrm{SG} =0$ ,既局面的 $\mathrm{SG} = 0$ ; 对于所有的单一游戏其 $\mathrm{SG} \leqslant 1$ 。 在先手的任意操作操作之后,局面都转移至 SJ 定理中的 $(2)$ ,先手必败。 [3] 局面的 $\mathrm{SG} \ne 0 $ 且 $\exists G_i \in \mathbb{G} \text{ s.t. } \mathrm{SG}(G_i) > 1 $ 。  首先,如果只有一个单一游戏其 $\mathrm{SG} > 1$ : 先手选择更改此单一游戏,选择将其更改为 $\mathrm{SG} = 0$ 或 $\mathrm{SG} = 1 $ 的单一游戏,使得局面中有只有奇数个 $\mathrm{SG} = 1$ 的单一游戏。 此时 (操作完成后) 根据 SG 函数的定义,为 P-position 。所以先手必胜。 其次,如果有超过一个单一游戏其 $\mathrm{SG} > 1$ : 根据 SG 函数的性质, $\exists \mathrm{T} \in N(\mathrm{S}) \text{ s.t. } \mathrm{SG(T)} = 0$ ; 因为每次最多对一个单一游戏操作,所以 $\exists G_i \in \mathbb{G} \text{ s.t. } \mathrm{SG}(G_i) > 1 $ 。 此时 (操作完成后) 情况到了刚刚讨论过的 [1] , 所以先手必胜。 [4] 局面的 $\mathrm{SG} = 0 $ 且 $\forall G_i \in \mathbb{G} \text{ s.t. } \mathrm{SG}(G_i) \leqslant 1$ 。 首先如果 $\forall G_i \in \mathbb{G} \,,\, \mathrm{SG}(G_i) = 0 $ ,那么游戏结束了,先手必胜。 其次显然局面中有偶数个 $\mathrm{SG} = 0 $ 的单一游戏。先手选择任一将其 $\mathrm{SG}$ 变为 $0$ ,那么游戏出现奇数个 $\mathrm{SG} = 1 $ 的单一游戏,为 P-positon , 先手必胜。 综上, SJ 定理证毕。 ---------------- **于是这题目就是板题了** ```cpp #include<cstdio> #include<iostream> #include<cstring> #include<cmath> #include<cstdlib> #include<algorithm> #define ll long long using namespace std; int T,n,seq[5010],ans; template<typename int_t> void readx(int_t& x) { x=0; int_t k=1; char ch=0; while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; } while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); } x*=k; } int main() { readx(T); while (T--) { readx(n); for (int i=1;i<=n;i++) readx(seq[i]); int lonely=0,full=0; ans=0; for (int i=1;i<=n;i++) { if (seq[i]==1) lonely++; else full++; ans^=seq[i]; } if (!full) { if (lonely%2) printf("Brother\n"); else printf("John\n"); } else { if (!ans) printf("Brother\n"); else printf("John\n"); } } } ```