题解 P4279 【[SHOI2008]小约翰的游戏】
GNAQ
2018-12-12 21:03:59
本文首发于 [随便搞搞 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");
}
}
}
```