前置知识
- \(\operatorname {mex}\)：没有出现过的最小天然数，如 \(\operatorname {mex} \{0,2,3\}=1\)。
- \(\oplus\)：按位异或。
前言
博弈类问题大致分为，公平组合游戏、非公平组合游戏（绝大多数的棋类游戏）、反常游戏。
只需要关注公平组合游戏 \(\texttt{(ICG)}\)，反常游戏是公平组合游戏的变形，经济类博弈也不是博客所讨论的范围
- 两个玩家轮流行动且游戏方式一致。
- 两个玩家对状况完全相识。
- 游戏肯定会在有限步数内分出胜败。
- 游戏以玩家无法行动竣事。
博弈的双方都被以为是神之个体，因为所有玩家对状况完全相识，且充分为自己打算，绝对理性。
当局面确定，效果肯定注定，并且没有任何随机的身分。
游戏中的每一个状态，终极导致的效果也肯定注定，只有必胜态、必败态，两种状态。
这一类博弈问题的效果没有任何意外，一方可以通过积极去改变效果是不大概的，这一点是反直觉的。
- 常用对数器打表来找规律。
- 博弈论的标题就是 要干去干，去找规律，不要怕。
巴什博弈 \(\texttt{(Bash)}\)
\(n\) 个的石头，每次操作可以拿走 \([1,m]\) 个石头。拿到末了 \(1\) 个石头的人获胜（也就是不能拿石头的人输）。
这个问题特别简单，就是显然答案是如果 \(n\) 为 \(m+1\) 的倍数那么先手输，否则先手赢。
\(\texttt{sg}\) 函数
接下来引入 \(\texttt{sg}\) 函数。
\(\texttt{sg}\) 体现当前状态的胜败情况。
有如下公式 \(sg(A)=\operatorname {mex} (sg(B)|A\to B)\)。
式子中的 \(A\) 和 \(B\) 体现状态，\(A\to B\) 体现 \(A\) 状态可以到达 \(B\)状态。也就是说我们可以通过 \(A\) 能到达的状态的SG函数值推算出 \(A\) 的 \(SG\) 值。
如果 \(\texttt{sg}\) 值为 \(0\) 则体现先手输，否则先手赢。
数学归纳法证实：
- 终极状态 \(SG=0\)。
- 对于任意一个必胜态 \(SG\not=0\)，存在一个后继态 \(SG=0\)
- 对于任意一个必败态 \(SG=0\)，不存在一个后继态 \(SG=0\)。
\(\texttt{e.g.}\)：在巴什博奕中：当 \(m = 2\) 时，\(\texttt{sg[0]=0,sg[1]=1,sg[2], sg[3]=0,}\cdots\)。
\(\texttt{FAQ}\):
- Q: 不就是判断一个输赢吗？为什么要用一个 \(\texttt {int}\)，我 \(\texttt{bool}\) 也可以啊。
- A: 是的，确实可以只有 \(\texttt{bool}\)，用 \(\texttt{int}\) 另有用途，我们下面会讲。
P2197 【模板】\(\texttt{(Nim)}\) 游戏——\(\texttt{sg}\) 多个独立的子问题的归并
标题描述
甲，乙两个人玩 \(\texttt{nim}\) 取石子游戏。
\(\texttt{nim}\) 游戏的规则是这样的：地上有 \(n\) 堆石子（每堆石子数量小于 \(10^4\)），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。末了没石子可取的人就输了。假如甲是先手，且告诉你这 \(n\) 堆石子的数量，他想知道是否存在先手必胜的策略。
公式引入
若局面X由若干个子游戏 \(X1,X2...Xn\) 构成，则
\(SG(x)=SG(X_1)\oplus SG(X_2) \oplus \cdots\oplus SG(X_n)\)
数学归纳法证实：
- 终极局面成立
- \(\forall X\)，所有后继局面可以取到 \(G(X_1)\oplus SG(X_2) \oplus \cdots\oplus SG(X_n)-1\)，取不到\(SG(X_1)\oplus SG(X_2) \oplus \cdots \oplus SG(X_n)\)
同样看做 \(\texttt{Nim}\) 游戏
设 \(S \rightarrow S_1\)
\(S \oplus (S \oplus S_1) =S_1\)
设 \((S \oplus S_1)\) 最高位为 \(k\)，存在 \(A\) 使得 \(k\) 位为 \(1\)。
那么\(A \oplus (S \oplus S_1) < A\)，所以让 \(A\) 变成\(A \oplus (S \oplus S_1)\)就行了。
这就是 \(\texttt{SG}\) 定理( \(\texttt{Bouton}\) 定理)。
问题解答
显然对于每一个子问题，对于石头个数为 \(n\)， \(\texttt {sg(n)=n}\)。
所以 \(SG=\oplus_{i=1}^{n}a_i\)。判断 \(\oplus_{i=1}^{n}a_i 是否为零即可\)
代码
- #include<bits/stdc++.h>
- using namespace std;
- int t, n, a;
- signed main(){
- scanf("%d", &t);
- while (t--) {
- scanf ("%d", &n); int ans = 0;
- while (n--) scanf("%d", &a), ans ^= a;
- if (ans == 0) puts("No"); else puts("Yes");
- }
- return 0;
- }
标题描述
甲，乙两个人玩 取石子游戏。
游戏的规则是这样的：地上有 \(n\) 堆石子（每堆石子数量小于 \(5000\)），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。末了没石子可取的人就赢了。假如甲是先手，且告诉你这 \(n\) 堆石子的数量，他想知道是否存在先手必胜的策略。
这一题唯一的区别是 末了没石子可取的人就赢了。
标题剖析
首先，如果 \(\forall i\) 有 \(a_i=1\)，那么就是看 \(n\) 的奇偶性了。
其次，如果只有一个 \(a_i\not=1\)，那么先手必赢 [1]
末了，因为要的是“只有一个 \(a_i\not=1\)”，异或和不为 \(0\), 所以只要抓住异或和不为 \(0\) 即可获胜，那么就转化为 \(\texttt{(Nim)}\) 游戏了。
示例代码
- #include<bits/stdc++.h>
- using namespace std;
- int main() {
- int t, n, x, ans, sum;
- scanf("%d", &t);
- while (t--) {
- cin >> n, ans = sum = 0;
- for(int i = 1; i <= n; ++ i) scanf("%d", &x), ans ^= x, sum += x;
- if(sum == n) puts(n & 1 ? "Brother" : "John");
- else puts(ans ? "John" : "Brother");
- }
- return 0;
- }
标题描述
有三堆石头，数量分别为 \(a,b,c(a,b,c\le 10^5)\)。
两个人轮流拿，每次可以选择此中一堆石头，拿取斐波那契数的石头
拿到末了一颗石子的人获胜，根据 \(a,b,c\) 返回谁赢。
直接分别计算 \(\texttt{sg}\) 值即可。因为 \(\texttt{sg}\) 值都只会从最多 \(25\) 个后继推出，所以 \(\forall i, \texttt{sg}\le30\)。时间复杂度为 \(O(nm)\)。 此中 \(m\) 为 \([1,n]\) 中斐波那契数的个数。
例三：P2148 [SDOI2009] E&D
标题描述
桌子上有 \(2n\) 堆石子，编号为 \(1,2,3\cdots,2n\)。
此中 \(1,2\) 为一组；\(3, 4\) 为一组； \(5, 6\) 为一组 \(,\cdots, 2n-1,2n\) 为一组。
每组可以进行分割操作：
- 任取一堆石子，将其移走，然后分割同一组的另一堆石子
- 从中取出若干个石子放在被移走的位置，组成新的一堆
- 操作完成后，组内每堆的石子数必须保证大于 \(0\)
- 显然，被分割的一堆的石子数至少要为 \(2\)
两个人轮流进行分割操作，如果轮到某人进行操作时，所有堆的石子数均为 \(1\)，判此人输掉角逐。
返回先手能不能获胜。
标题剖析
首先 \(\texttt{sg(x,y)}\) 体现当前一组内石子数分别为 \(x,y\) 的胜败情况。
直接暴力算出 \(20\times20\) 的 \(\texttt{sg}\) 表。
找规律。
发现 \(sg(x, y)=f((x-1)|(y-1))\)。
此中 \(f(x)\) 体现 \(x\) 最低 \(0\) 的位置如 \(8=(1000)_2,f(8)=0;7=(0111)_2,f(7)=3\)。
具体证实见 题解 P2148 【[SDOI2009]E&D】。
代码易得，略。
例四：CF87C Interesting Game
标题简述
每次可以把一堆石子分成若干堆，使得分裂的石子是公差为 \(1\) 的等差数列。不能分的人输。
标题分析
直接算 \(\texttt{sg}\) 值。详见代码。
代码
[code]#include using namespace std;const int N = 1e5 + 10;int n, sg[N], mex[N];int main() { scanf("%d", &n); int ans = -1, cnt = 1; for (int i = 3; i b;}int main() { cin >> n; while (n--) { cin >> k; for (int i = 1; i > x, aa += x; if (k & 1) cin >> x, m.push_back(x); for (int i = 1; i > x, ab += x; } sort (m.begin(), m.end(), cmp); for (int i = 0; i < m.size(); i++) { if (i % 2 == 0) aa += m; else ab += m; } cout l >> r; for (int i = 1; i > x; SG ^= sg(x); } cout >= 1, t++; // 最高位（因为要保证有一个数能被除） for (int i = 1; i > i) | // 前半部分是被除以的，所以左移； (x & ((1 > n; for (int i = 1; i > x; for (int j = 2; j * j |
