前置知识
- mex \operatorname {mex} mex：没有出现过的最小自然数，如 mex { 0 , 2 , 3 } = 1 \operatorname {mex} \{0,2,3\}=1 mex{0,2,3}=1。
- ⊕ \oplus ⊕：按位异或。
前言
博弈类问题大致分为，公平组合游戏、非公平组合游戏（绝大多数的棋类游戏）、反常游戏。
只需要关注公平组合游戏
(ICG)
\texttt{(ICG)}
(ICG)，反常游戏是公平组合游戏的变形，经济类博弈也不是博客所讨论的范围
- 两个玩家轮流行动且游戏方式一致。
- 两个玩家对状况完全了解。
- 游戏一定会在有限步数内分出胜负。
- 游戏以玩家无法行动结束。
博弈的双方都被认为是神之个体，因为所有玩家对状况完全了解，且充分为自己打算，绝对理性
当局面确定，结果必然注定，并且没有任何随机的成分
游戏中的每一个状态，最终导致的结果也必然注定，只有必胜态、必败态，两种状态
这一类博弈问题的结果没有任何意外，一方可以通过努力去改变结果是不可能的，这一点是反直觉的。
- 常用对数器打表来找规律。
- 博弈论的题目就是 要干去干，去找规律，不要怕。
巴什博弈 (Bash) \texttt{(Bash)} (Bash)
n n n 个的石头，每次操作可以拿走 [ 1 , m ] [1,m] [1,m] 个石头。拿到最后 1 1 1 个石头的人获胜（也就是不能拿石头的人输）。
这个问题特别简单，就是显然答案是如果 n n n 为 m + 1 m+1 m+1 的倍数那么先手输，否则先手赢。
sg \texttt{sg} sg 函数
接下来引入 sg \texttt{sg} sg 函数。
sg \texttt{sg} sg 表示当前状态的胜负情况。
有如下公式 s g ( A ) = mex ( s g ( B ) ∣ A → B ) sg(A)=\operatorname {mex} (sg(B)|A\to B) sg(A)=mex(sg(B)∣A→B)。
式子中的 A A A 和 B B B 表示状态， A → B A\to B A→B 表示 A A A 状态可以达到 B B B状态。也就是说我们可以通过 A A A 能达到的状态的SG函数值推算出 A A A 的 S G SG SG 值。
如果 sg \texttt{sg} sg 值为 0 0 0 则表示先手输，否则先手赢。
数学归纳法证明：
- 最终状态 S G = 0 SG=0 SG=0。
- 对于任意一个必胜态 S G ≠ 0 SG\not=0 SG=0，存在一个后继态 S G = 0 SG=0 SG=0
- 对于任意一个必败态 S G = 0 SG=0 SG=0，不存在一个后继态 S G = 0 SG=0 SG=0。
e.g. \texttt{e.g.} e.g.：在巴什博奕中：当 m = 2 m = 2 m=2 时， sg[0]=0,sg[1]=1,sg[2], sg[3]=0, ⋯ \texttt{sg[0]=0,sg[1]=1,sg[2], sg[3]=0,}\cdots sg[0]=0,sg[1]=1,sg[2], sg[3]=0,⋯。
FAQ \texttt{FAQ} FAQ:
- Q: 不就是判断一个输赢吗？为什么要用一个 int \texttt {int} int，我 bool \texttt{bool} bool 也可以啊。
- A: 是的，确实可以只有 bool \texttt{bool} bool，用 int \texttt{int} int 另有用途，我们下面会讲。
P2197 【模板】 (Nim) \texttt{(Nim)} (Nim) 游戏—— sg \texttt{sg} sg 多个独立的子问题的合并
题目描述
甲，乙两个人玩 nim \texttt{nim} nim 取石子游戏。
nim \texttt{nim} nim 游戏的规则是这样的：地上有 n n n 堆石子（每堆石子数量小于 1 0 4 10^4 104），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手，且告诉你这 n n n 堆石子的数量，他想知道是否存在先手必胜的策略。
公式引入
若局面X由若干个子游戏
X
1
,
X
2...
X
n
X1,X2...Xn
X1,X2...Xn 构成，则
S
G
(
x
)
=
S
G
(
X
1
)
⊕
S
G
(
X
2
)
⊕
⋯
⊕
S
G
(
X
n
)
SG(x)=SG(X_1)\oplus SG(X_2) \oplus \cdots\oplus SG(X_n)
SG(x)=SG(X1)⊕SG(X2)⊕⋯⊕SG(Xn)
数学归纳法证明：
- 最终局面成立
- ∀ X \forall X ∀X，所有后继局面可以取到 G ( X 1 ) ⊕ S G ( X 2 ) ⊕ ⋯ ⊕ S G ( X n ) − 1 G(X_1)\oplus SG(X_2) \oplus \cdots\oplus SG(X_n)-1 G(X1)⊕SG(X2)⊕⋯⊕SG(Xn)−1，取不到 S G ( X 1 ) ⊕ S G ( X 2 ) ⊕ ⋯ ⊕ S G ( X n ) SG(X_1)\oplus SG(X_2) \oplus \cdots \oplus SG(X_n) SG(X1)⊕SG(X2)⊕⋯⊕SG(Xn)
同样看做 Nim \texttt{Nim} Nim 游戏
设 S → S 1 S \rightarrow S_1 S→S1
S ⊕ ( S ⊕ S 1 ) = S 1 S \oplus (S \oplus S_1) =S_1 S⊕(S⊕S1)=S1
设 ( S ⊕ S 1 ) (S \oplus S_1) (S⊕S1) 最高位为 k k k，存在 A A A 使得 k k k 位为 1 1 1。那么 A ⊕ ( S ⊕ S 1 ) < A A \oplus (S \oplus S_1) < A A⊕(S⊕S1)<A，所以让 A A A 变成 A ⊕ ( S ⊕ S 1 ) A \oplus (S \oplus S_1) A⊕(S⊕S1)就行了。
问题解答
显然对于每一个子问题，对于石头个数为 n n n， sg(n)=n \texttt {sg(n)=n} sg(n)=n。
所以 S G = ⊕ i = 1 n a i SG=\oplus_{i=1}^{n}a_i SG=⊕i=1nai。判断 ⊕ i = 1 n a i 是否为零即可 \oplus_{i=1}^{n}a_i 是否为零即可 ⊕i=1nai是否为零即可
代码
#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;
}
P4279 [SHOI2008] 小约翰的游戏
题目描述
甲，乙两个人玩 取石子游戏。
游戏的规则是这样的：地上有 n n n 堆石子（每堆石子数量小于 5000 5000 5000），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就==赢==了。假如甲是先手，且告诉你这 n n n 堆石子的数量，他想知道是否存在先手必胜的策略。
这一题唯一的区别是 最后没石子可取的人就赢了。
题目解析
首先，如果
∀
i
\forall i
∀i 有
a
i
=
1
a_i=1
ai=1，那么就是看
n
n
n 的奇偶性了。
其次，如果只有一个
a
i
≠
1
a_i\not=1
ai=1，那么先手必赢 为什么
最后，因为要的是“只有一个
a
i
≠
1
a_i\not=1
ai=1”，异或和不为
0
0
0, 所以只要抓住异或和不为
0
0
0 即可获胜，那么就转化为
(Nim)
\texttt{(Nim)}
(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;
}
P6487 [COCI2010-2011#4] HRPA ——斐波那契博弈
前置知识
- 斐波拉契数列：
F = { 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , . . . . . } F ( n ) = { 0 if n = 0 1 if n = 1 F ( n − 1 ) + F ( n − 2 ) if n > 1 F = \{1,1,2,3,5,8,13,21,34,.....\}\\ F(n) = \begin{cases} 0 & \text{if } n = 0 \\ 1 & \text{if } n = 1 \\ F(n-1) + F(n-2) & \text{if } n > 1 \end{cases} F={1,1,2,3,5,8,13,21,34,.....}F(n)=⎩ ⎨ ⎧01F(n−1)+F(n−2)if n=0if n=1if n>1 - 齐肯多夫（Zeckendorf）定理：任何正整数都可以表示成若干个不连续的斐波那契数之和。如 4 = 1 + 3 ( 1 4=1+3(1 4=1+3(1 和 3 ) 3) 3) 不相邻。
证明：
- 若正整数 n n n 为斐波那契数，得证。
- 否则，先取 $ F_{t_1} $，其中 $ t_1 $ 满足 $ F_{t_1} < n < F_{t_1 + 1} $。
- 令 $ n’ = n - F_{t_1} $，同上一步取出一个 $ F_{t_2} $ 满足 $ F_{t_2} < n’ < F_{t_2 + 1} $。
- 只要证明 $ t_1 \neq t_2 + 1 $。考虑反证法：
- 假设 $ t_1 = t_2 + 1 $，则第一步取出的应当是 $ t_1 + 1 $ 而不是 $ t_1 $。原因是 $ F_{t_1 + 1} = F_{t_1} + F_{t_1 - 1} $。
题目分析
如果 t t t 为斐波拉契数，那么必须全部取完。
设 $ n = F_{i b_t} $，我们把 $ n $ 看成 $ F_{i b_{t-1}} $ 和 $ F_{i b_{t-2}} $ 两堆。
- 若第一步取的个数超过 $ F_{i b_{t-2}} $，则后手可以直接取完剩余石子。
- 否则，该问题变成了一个规模更小的同样的问题。
考虑 $ n = 2 $ 的情况（即规模最小的情况），先手只能取 1，于是后手取 1获胜。
可以结合下面理解一下
比如 43 = 34 + 8 + 1 43=34+8+1 43=34+8+1 那么答案为 1 1 1。
首先取走 1 1 1，然后如果对方选择的数只能选择 [ 1 , 2 ] [1,2] [1,2]
假如对方取的是 2 2 2，那么 8 = 3 + 5 8=3+5 8=3+5，我选择把 3 3 3 消掉，我就选择 1 1 1。
这时数字变成了 34 + 5 34+5 34+5
对方又只能选择 [ 1 , 2 ] [1,2] [1,2], 假如他选择 1 1 1,那么 5 = 2 + 3 5=2+3 5=2+3,我就把 2 2 2消掉，选择 1 1 1
这时数字变成 34 + 3 34+3 34+3
对方又只能选择 [ 1 , 2 ] [1,2] [1,2], 假如他选择 2 2 2,那么我就把 3 3 3消掉，选择 1 1 1
这时数字变成 34 34 34
对方又只能选择 [ 1 , 2 ] [1,2] [1,2], 假如他选择 2 2 2,那么 34 = 21 + 8 + 5 34=21+8+5 34=21+8+5消掉，我就把 5 5 5 消掉，选择 3 3 3
这时数字变成 21 + 8 21+8 21+8
对方又只能选择 [ 1 , 6 ] [1,6] [1,6], 假如他选择 6 6 6,那么 29 = 21 + 8 29=21+8 29=21+8消掉，我就把 8 8 8 消掉，选择 2 2 2
这时数字变成 21 21 21
对方又只能选择 [ 1 , 6 ] [1,6] [1,6], 假如他选择 6 6 6,那么 29 = 21 + 8 29=21+8 29=21+8消掉，我就把 8 8 8 消掉，选择 2 2 2
这时数字变成 21 21 21
对方又只能选择 [ 1 , 4 ] [1,4] [1,4], 假如他选择 4 4 4,那么 21 = 13 + 8 21=13+8 21=13+8消掉，我就把 8 8 8 消掉，选择 4 4 4
这时数字变成 13 13 13
对方又只能选择 [ 1 , 8 ] [1,8] [1,8], 假如他选择 8 8 8,那么 13 = 8 + 5 13=8+5 13=8+5消掉，我就把 5 5 5 直接消掉，获得胜利。
参考资料
- 博弈类问题必备内容详解-上
- 博弈类问题必备内容详解-下
- SG 函数 & 博弈论
- OI-WiKi
- 博弈论 | 详解搞定组合博弈问题的SG函数
- [组合游戏与博弈论]【学习笔记】
- [COCI2010-2011#4] HRPA
施工进度
- 前置知识
- 前言
- SG \texttt{SG} SG 函数
- 巴什博弈 (Bash) \texttt{(Bash)} (Bash)
- 尼姆博弈 (Nim) \texttt{(Nim)} (Nim)
- 反尼姆博弈
- 斐波那契博弈 (Fibonacci) \texttt{(Fibonacci)} (Fibonacci)
- 威佐夫博弈 (Wythoff) \texttt{(Wythoff)} (Wythoff)