0. 前言

对于在信息学竞赛中的博弈论，我们研究的是组合博弈问题。在实际考察中会结合其他知识点考察，例如动态规划或者贪心等，建立模型来解决问题。

本文建议读者看到模型后可以停下来思考思考，让后再看证明。

说半家桶是因为内容还不全，不能作为 OI 中的全家桶，但是足以应付一部分问题了。

~~有谁注意到标题其实有一个回文串了。~~

1. 组合博弈与博弈基础

对于组合博弈，我们用两种类型：公平组合游戏和非公平组合游戏来区别，定义如下：

1.1 公平组合与非公平组合

公平组合游戏：

由两名玩家交替行动；
任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关，而与游戏者无关；
游戏中的同一个状态不可能多次抵达，游戏以玩家无法行动为结束，且游戏一定会在有限步后以非平局结束。

例如取数游戏，Nim 游戏等，是公平组合游戏，我们下文会提到。

而非公平组合游戏，即在某一确定状态下作出的决策集合与游戏者有关。例如国际象棋，五子棋等是非公平组合游戏，因为双方不能使用对方的棋子。

以上是 Oi-Wiki 的内容，可能很抽象，但是提取重点的来说：

公平组合游戏：可允许的操作和当前局面状态有关，而不和玩家有关（这样就很公平，因为和玩家无关啦）。
非公平组合游戏：可允许的操作与当前操作的玩家有关（因为和玩家有关，我不能动你的棋子，这显然很不公平 www）。

1.2 先手，后手，必胜必输局面

~~本手，妙手，俗手。~~

接下来我们定义几个名词：

局面：我们把游戏过程中面临的状态我们称作为 “局面”。
先手：整局游戏第一个行动的。
后手：整局游戏第二个行动的。

这几个名词还是比较简单的。

必败局面：即无论采取任何行动都无法胜利，都会输掉游戏。
必胜局面：即在某一局面下存在某种行动，使得后手行动陷入必败局面。

注意其中名词加粗的部分。

1.3 先手必胜与先手必败

先手必胜状态： 先手行动以后，可以让剩余的状态变成必败状态 留给对手。(即可以走到某一个必败状态)
先手必败状态： 不管怎么操作，都达不到必败状态，换句话说，如果无论怎么行动都只能达到一个先手必胜状态留给对手，那么对手（后手）必胜，先手必败。（即走不到任何一个必败状态）

有如下定理：

没有后继状态的状态是必败状态。
一个状态是必胜状态当且仅当存在至少一个必败状态为它的后继状态。
一个状态是必败状态当且仅当它的所有后继状态均为必胜状态。

1.4 必胜点与必败点

必败点，又称 P 点，表示前一个选手将取胜的点称作必败点。
必胜点，又称 N 点，表示下一个选手将取胜的点称作必胜点。

所有终结点都是必败点。
从任何必胜点操作，至少存在一种方案可以进入必败点。
无论如何操作，必败点只能进入必胜点（不然先手怎么赢）。

2. 基本公平组合游戏

接下来我们看见一堆取东西的游戏 www。

2.1 Nim 游戏

给定 n 堆物品，第 i 堆物品有 a_{i} 个。两名玩家分别行动，每次可以任选一堆，取出任意多个物品，可以一把取光但是不能不取。取走最后一个物品的人胜利。

~~Vim 游戏？~~

Nim 游戏没用平局，只有先手必胜和先手必败两种情况。我们有如下的判定定理来判定：

Nim 博弈先手必胜，当且仅当 a_{1} \operatorname{xor} a_{2} \operatorname{xor} \dots \operatorname{xor} a_{n} \neq 0。

其中 \operatorname{xor} 代表异或操作。

证明如下：

我们考虑，所有物品都被取光当然是一个必败局面（对手取走最后一件物品，已经取得胜利），此时 a_{1} \operatorname{xor} a_{2} \operatorname{xor} \dots \operatorname{xor} a_{n} = 0。

对于一个局面如果 a_{1} \operatorname{xor} a_{2} \operatorname{xor} \dots \operatorname{xor} a_{n} \neq 0，那么设 x 二进制表示下最高位的 1 在第 k 位，那么至少存在一堆物品使得它的第 k 位为 1。显然 a_{i} \operatorname{xor} x < a_{i}，我们就从 a_{i} 堆中取走若干物品，使其变为 a_{i} \operatorname{xor} x，这个操作我们就是尝试将局面变为 a_{1} \operatorname{xor} a_{2} \operatorname{xor} \dots \operatorname{xor} a_{n} = 0，容易证明这是最优策略。

对于任意一个局面，若 a_{1} \operatorname{xor} a_{2} \operatorname{xor} \dots \operatorname{xor} a_{n} = 0，容易证明无论如何取物品，最后的局面异或起来都无法不等于 0，那么综上所述 a_{1} \operatorname{xor} a_{2} \operatorname{xor} \dots \operatorname{xor} a_{n} \neq 0，一定是必胜局面，一定存在一个情况让对手面临各堆物品异或起来为 0 的局面，证毕。

P2197 NIM游戏

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=1e5+15;
int T,n;

int main(){
    cin>>T;
    while(T--){
        cin>>n;
        int ans=0;
        for(int i=1;i<=n;i++){
            int x;
            cin>>x;
            ans^=x;
        }
        if(ans) cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}

2.2 Nim升级版——NimK

n 堆石子，每次从不超过 k 堆中取任意多个石子，取走最后一个物品的人胜利。

结论如下：

把 n 堆石子用二进制数表示，统计二进制数上 1 的个数，若每一位上 1 的个数 num_{1} \bmod (k+1) 全部为 0，则先手必胜，否则先手必败。

证明还是类似于 Nim 游戏：

所有物品都被取光当然是一个必败局面，即全为 0。
任意一个先手必败状态，一次操作后必然会到达必胜状态（因为游戏是交替进行的。）在某一次移动中，至少有一堆被改变，也就是说至少有一个二进制位被改变。因为最多动 k 堆，所以对于任意一个二进制位，1 的个数最多改变 k。而由于原先的总数为 k+1 的整数倍，那么改变后必然不可能是 k+1 的整数倍。所以在必败状态下必然能转移到必胜状态。
而对于先手必胜，总有一种操作使其走到必败状态，即证明有一种方法让第 i 位回到 k+1 的整数倍。有一个比较显然的性质，对于那些已经改变的 m 堆，当前位可以自由选择 1 或 0。我们设除去已经更改的 m 堆，剩下堆 i 位上 1 的总和为 sum。考虑分类讨论：
- sum\le k-m，此时我们可以将堆上的 1 全部拿掉，让后让拿 m 堆得 i 位全部为 0。
- sum>k-m，此时我们在之前改变的 m 堆中选择 k+1-sum 堆，将他们的第 i 位设置成 1。剩下的设置成 0。由于 k+1-sum<k+1-(k-m)<m+1,也就是说 k+1-sum\le m，故这是可以达到的。

故存在，证毕。

例题：SDOI2011黑白棋

2.3 阶梯 Nim 游戏

n 堆石子，编号 1 到 n。初始第 n 堆石子数为 a_{i}，保证单调不降。轮流取石子，每次从任意一堆拿走任意个，要求取完后每一堆剩余石子个数单调不降（没有石子的记为 0 个），先不能行动者败。

或者换一种表述：

有 n 堆石子。除了第一堆外，每堆石子个数都不少于前一堆的石子个数。两人轮流操作。每次操作可以从一堆石子中移走任意多颗石子，但是要保证操作后仍然满足初始时的条件。没有石子可移动的人就输掉了游戏。

因为堆数是单调递增的，像一个阶梯，我们在阶梯取石子。所以叫阶梯 Nim 游戏。

结论：

阶梯 nim 的游戏结果与只看奇数堆的石子数的普通 nim 结果一致。

考虑证明：

首先末态一定是 a_{1} \operatorname{xor} a_{3} \operatorname{xor} a_{5}\dots=0，那么如果初态 a_{1} \operatorname{xor} a_{3} \operatorname{xor} a_{5}\dots=0，就一定存在一种方式将某奇数台阶的石子移动到偶数台阶上使得异或和为 0 。这样，不管后手的人是把奇数台阶的移动到偶数台阶还是相反，先手都一定存在一种方案使得异或和为 0 ,这样就一定能转移到末态，先手就赢了！

板题：

P3480

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=1520;
int T,n,a[MN],b[MN];

void solve(){
    cin>>n;
    int x=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i]-a[i-1];
    }
    for(int i=n;i>=1;i-=2) x^=b[i];
    if(x) cout<<"TAK\n";
    else cout<<"NIE\n";
}

int main(){
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

2.4 巴什博弈 Bash Game

~~Bash 命令行？~~

只有一堆石子，个数为 n 个，两名玩家轮流在石子堆中拿石子，每次至少取 1 个，至多取 m 个，最后一个取走石子的玩家为胜者。

结论如下：

若 (m+1)|n，则先手必败，否则先手必胜。

证明如下：

当 n\le m 时，显然先手必胜。
当 n=m+1 时，先手最多取走 m 个，无论取走多少个后手必胜。
若 (m+1)|n，假设先手拿走 x 个，那么后手一定可以拿走 (m+1)-x 个，这样无论怎么拿剩下的石头个数都是 (m+1) 的倍数，那么最后一次取的石头一定还剩下 m+1 个，显然必败。否则，先手取走模 (m+1) 的手头，此时转化为 (m+1)|n，那么后手必败。

得证。

有板题：HDU4764

2.5 威佐夫博弈

有两堆石子，石子数可以不同。两人轮流取石子，每次可以在一堆中取，或者从两堆中取走相同个数的石子，数量不限，取走最后一个石头的人获胜。判定先手是否必胜。

威佐夫博弈不同于Nim游戏与巴什博奕，它的特殊之处在于不能将两堆石子分开分析。

证明可以不看的 www。

因为只有两堆石子，先进行一步转化给他丢到二维坐标系上，那么坐标 (x,y) 就表示两堆的石子数量。

我们定义，先手必输的局势为奇异局势。不妨设 (x,y) 为第 k 个奇异局势，那么有如下性质：

x 为前 k 个奇异局势中最小没有出现过的正整数，y=x+k。
任何一个自然数都包含在有且仅有一个奇异局势中。
任何操作都会将奇异局势变成非奇异举止。
可以采取适当的方法让非奇异局势变成奇异局势。

~~第一个打表找规律~~。

第二个个证明考虑反证法，我们需要证明两点：

任意自然数都出现过。
任意自然数只出现一次。

证明如下：

反证法，如果 v 没有出现过，那么 v 显然可以做一个新奇异局势的 x。
反证法，假设 v 出现了两次，那么 v 一定不是所在奇异局势的 x，那么 v 只能同时是两个奇异局势的 y，但因为任意一个奇异局势的差值不相同，所以 v 不可能存在。

第三个，我们考虑若取走一堆中的石子，那么两对石子的差值会改变，必将成为非奇异局势。若同时取走，因为同一个差值只会对应一种奇异局势，必将成为非奇异局势。

第四个是显然的，不证明。

有了上面四个定理，同时结合 Betty 定理，给出了重要结论。

假设两堆石子为 (x,y),x<y。

那么先手必败，当且仅当：

(y-x) \times \frac{\sqrt{5}+1}{2}=x

其中，\dfrac{\sqrt{5}+1}{2} 就是黄金分割数，很神奇的。

题目：P2252

#include<bits/stdc++.h>
#define double long long
using namespace std;
const double hjfg=((1.0+sqrt(5.0))/2.0);
double a,b;

int main(){
    cin>>a>>b;
    if(a>b) swap(a,b);
    double ans=(b-a)*((1.0+sqrtl(5.0))/2.0);
    if(ans==a) cout<<0;
    else cout<<1;
    return 0;
}

2.6 斐波那契博弈

有一堆个数为 n,(n\ge 2) 的石子，游戏双方轮流取石子，规则如下：

先手不能第一次全取完，至少取 1 颗。
之后每次取的石子个数至少为 1，至多为对手所取的石子数的 2 倍。

还是最后一个取走石子的为赢家。

先手必败，当且仅当石子数为斐波那契数

先证明必要性，斐波那契数一定先手必败，可以用数学归纳法，大致思路就是一定能拆成两堆斐波那契数，不论先手怎样取，后手总能取到最后一颗

然后证明充分性，由齐肯多夫定理定理：

任何正整数可以表示为若干个不连续的斐波那契数之和

那么这样就回到了斐波那契数列里，可以证明。

考虑最优决策：

若正整数 n 不为斐波那契数，那么用上述定理表示后，最小的那一堆个数即为答案。

证明因为不存在相邻的斐波那契数，那么显然有 f_{j}>2 \times f_{i}，只要我取第一个，那么对手一定取不完下一个，让后我捡漏，以此类推，一定能取道最后一个石子。

板题：P6847

#include<bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
    int n;
    cin>>n;
    while(n){
        if(n==1){
            cout<<1;
            break;
        }
        if(n==2){
            cout<<2;
            break;
        }
        int a=1,b=2,c=3;
        while(c<n) a=b,b=c,c=a+b;
        if(c==n){
            cout<<n;
            break;
        }
        n-=b;
    }
    return 0;
}

2.7 总结

有一张来自HansLimon的好图：

以上都是一些基本公平组合游戏，我们通过分析必胜状态与必败状态的位置来计算。接下来我们会介绍公平组合游戏的万能工具，SG 函数。

3. SG与有向图游戏

3.1 有向图游戏

给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。

任何一个公平组合游戏都可以转化为有向图游戏。具体方法是，把每个局面看成图中的一个节点，并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。转化为有向图游戏，也称绘制了它的博弈状态图（简称博弈图或游戏图）。

3.2 Mex 运算

设 S 表示一个非负整数集合。定义 \operatorname{mex}(S) 为求出不属于集合S的最小非负整数的运算，即：

\operatorname{mex}(S)=\min \left\{ x \right\},x\in \mathbb{N}^{+},x\notin S

\operatorname{mex}(S) 的求法可以考虑用 set 来实现，把 S 中的数都放入 set 中，维护两个操作：

加入 x 操作：在 set 删除 x，前提是 x 这个数出现第一次。
删除 x 操作：在 set 加入 x，前提是 x 是剩下的唯一一个 x。
查询操作：查询 set 里的第一个数。

例题：abc330e

3.3 SG 函数

在有向图游戏中，对于每个节点 x，设从 x 除法共有 k 条有向边，分别到达节点 y_{1},y_{2},\dots ,y_{k}，定义 \operatorname{SG}(x) 表示为 x 的后继节点 y_{1},y_{2},\dots ,y_{k} 的 \operatorname{SG} 函数值所构成的集合再执行 \operatorname{mex} 运算的结果，即：

\operatorname{SG}(x)=\operatorname{mex}(\left\{ \operatorname{SG}(y_{1}),\operatorname{SG}(y_{2}),\dots,\operatorname{SG}(y_{k}) \right\})

特别的，整个有向图游戏 G 的 \operatorname{SG} 函数值定义为有向图起点 s 的 \operatorname{SG} 函数值，即 \operatorname{SG}(G)=\operatorname{SG}(s)。

3.4 必胜与必败判定,SG 定理

判定法则（同时也是定义）如下：

有向图某个局面必胜，当且仅当该局面对应节点的 \operatorname{SG} 函数值大于 0。
有向图某个局面必胜，当且仅当该局面对应节点的 \operatorname{SG} 函数值等于 0。

有向图游戏的和，即 SG 定理，我们这么定义：

设 G_{1},G_{2},\dots,G_{m} 是 m 个有向图游戏。定义有向图游戏 G，它的行动规则是任选某个有向图游戏 G_{i}，并在 G_{i} 上行动一步。G 被称为有向图游戏 G_{1},G_{2},\dots,G_{m} 的和。

有向图游戏的和的 \operatorname{SG} 函数值等于它包含的各个子游戏 \operatorname{SG} 函数值的异或和，即：

\operatorname{SG}(G)= \operatorname{SG} (G_{1}) \operatorname{xor} \operatorname{SG} (G_{2})\operatorname{xor} \dots \operatorname{SG} (G_{m})

3.5 NIM 游戏与 SG 函数的结合

对于单堆的 Nim 游戏，我们很容易计算它的 \operatorname{SG} 值，设 \operatorname{SG}(m) 表示剩余 m 个式子状态的函数值，显然 \operatorname{SG}(0)=0，那么以此类推，\operatorname{SG}(1)=1,\operatorname{SG}(2)=2,\dots,\operatorname{SG}(n)=n。因此，当石子数不为 0 时为必胜态。

而对于更多的，它们所有的堆都可以划分为一个单独的有向图游戏，而每一个有向图游戏的 \operatorname{SG} 函数值就是上面所以到的。那么，我们可以根据 \operatorname{SG} 定理，将它们给和起来，那么答案就是：

\begin{aligned} \operatorname{SG}(G) & =\operatorname{SG}(G_{1}) \operatorname{xor} \operatorname{SG}(G_{2)} \operatorname{xor} \dots \operatorname{xor} \operatorname{SG}(G_{n}) \\ & = a_{1} \operatorname{xor} a_{2} \operatorname{xor} \dots \operatorname{xor} a_{n} \end{aligned}

那么，我们就得到的 Nim 游戏的经典结论，是不是很神奇。

对于博弈的大部分问题，只要SG值相同，就可以互相转化

3.6 实际应用

P1290

显然是公平组合游戏。

我们考虑最终情况：一个数是 x，而另一个是 0，那么先手必败（因为游戏已经结束了）。

剩下的情况就是握着两个数，不妨设为 x,y，其中 x>y。

那么根据题意有：

\operatorname{SG}(n,m)=\operatorname{mex}(\left\{ \operatorname{SG}(n-m,m),\operatorname{SG}(n-2m,m),\dots,\operatorname{SG}(m,n \bmod m) \right\})

考虑里面怎么求，注意到：

\operatorname{SG}(n-m,m)=\operatorname{mex}(\left\{ \operatorname{SG}(n-2m,m),\operatorname{SG}(n-3m,m),\dots,\operatorname{SG}(m,n \bmod m) \right\})

同理可以迭代下去，所以除了 \operatorname{SG}(m,n \bmod m) 以外其他都可以由他迭代出来，考虑如何求出来：

假设 \operatorname{SG}(m,n \bmod m)=0，设 k=\dfrac{n}{m}，那么有 \operatorname{SG}(n-(k-1)\times m,m)=\operatorname{mex}\left\{ \operatorname{SG}(m,n \bmod m) \right\} 成立。

假设 \operatorname{SG}(m,n \bmod m)=1，那么 \operatorname{SG}(n-(k-1)\times m,m)=\operatorname{mex}\left\{ \operatorname{SG}(m,n \bmod m) \right\} 不成立。

由此可以看出，若 k=1,\operatorname{SG}(n,m)=[\operatorname{SG}(m,n \bmod m)=0]，否则是 1。

这是标准的辗转相除的递推式子，用 \gcd 的写法即可实现：

#include<bits/stdc++.h>
using namespace std;
int T;

int dfs(int x,int y,int p){
    if(x==y) return p;
    if(y/x>=2) return p;
    return dfs(y-x,x,p^1);
}

void solve(){
    int m,n;
    cin>>m>>n;
    if(m>n) swap(m,n);
    if(dfs(m,n,0)==0) cout<<"Stan wins\n";
    else cout<<"Ollie wins\n";
}

int main(){
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

一般来说，我们对于 SG 函数的求解，最常规的套路就是：暴力，找规律。或者打表。大部分题都可以这么进行操作，有的时候需要进一步转化模型，当然那就是后面再说了。

4. 反常游戏与反SG游戏

4.1 Anti-Nim游戏

是这样的：

有 n 堆石子，两个人可以从任意一堆石子中拿任意多个石子(不能不拿)，拿走最后一个石子的人失败`。

不难发现和 Nim 游戏不同的一点就是胜利条件变了，不过条件还是可以推的。

先手必胜有两种情况：

对于所有石子都只有一个，且游戏的 \operatorname{SG} 值为 0。
至少一堆石子多于一个，且游戏的 \operatorname{SG} 不为 0。

游戏分为三种情况：

当每堆只有一个石子
异或值为 0 时，先手必胜。
异或值不为 0 时，先手必败。
只有一堆石子数大于 1，先手必胜。

先手我们可以考虑对数量大于 1 的那对堆石子下手脚，从而构造出后手必败的状态：

存在至少两堆石子数大于1
当异或和为0时，先手必败
当异或和不为0时，先手必败

证明和 Nim 游戏是相似的，可以自行证明或网上搜索，这里就不给出了。

例题：SHOI2008 小约翰的游戏

#include<bits/stdc++.h>
using namespace std;
int T,n;

void solve(){
    cin>>n;
    int ans=0;
    bool flag=0;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        ans^=x;
        if(x>1) flag=1;
    }
    if(!flag&&!ans) cout<<"John\n";
    else if(flag&&ans) cout<<"John\n";
    else cout<<"Brother\n";
}

int main(){
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

4.2 反 SG 游戏

我们根据 Anti-Nim 游戏能否推广到一般性情况呢？有的兄弟有的，反 SG 游戏就是。

我们定义：

Anti-SG游戏：决策集合为空的游戏者赢，剩下规则与 SG 游戏相同。

那么，如何判断能否赢呢？

对于 Anti-SG 游戏，如果我们规定当局面单一游戏的 \operatorname{SG} 值为 0 时，游戏结束，则先手必胜当且仅当：

游戏的 \operatorname{SG} 函数不为0且游戏中某个单一游戏的 \operatorname{SG} 函数值大于 1。
游戏的 \operatorname{SG} 函数为0且游戏中没有某个单一游戏的 \operatorname{SG} 函数值大于 1。
证明和 \operatorname{SG} 函数类似。

5. 博弈论及与其他知识结合

5.0 操作手册

博弈论确实可以和其他芝士一起结合起来一块考。

一般我们拿到一个看起来像是博弈论的题，我们需要确定题目的类型，可以通过几个操作手册来：

确定博弈：大部分的博弈论题都是假博弈论，有可能是贪心什么的。需要自行观察以下，尤其警惕标题带博弈论的 www。
思考模型：大部分博弈都有基础模型，我们通过基础模型来构建起问题的 “整体”，这也是为什么我们上面给出那么多的组合游戏模型。
落实限制：我们找到模型后，题目一般都会给予你几个限制。现在就是发挥你实力的时候了，通过知识点的综合运用，将模型转化到一些知识点上去。
分类讨论：这个时候就是通过限制来进行分类讨论，不做过多介绍，可以做题体会。
写代码

5.1 例题

这里举几个比较简单的例题。DP 与博弈论的考察一般考察方案数的选取，或带有特殊限制的博弈问题。或者通过 DP 来求解博弈论所需要的信息。

GZOI2017 取石子游戏

不难发现这是一个带特殊限制的 NIM 游戏。

让 Alice 必败就是让其选择的石子堆中的数量异或为 0，要么无法在这一堆中足够的石子使得剩下的异或为 0，所以给定 Alice 选择的石子数量一定要大于等于其他选择的堆的数异或值。

考虑枚举 Alice 选哪一堆，让后对于其他石子堆用 DP 求出前 i 堆中任意选择一些使得异或值为 j 的方案数，直接统计即可，时间复杂度 O(n^2 \times 256)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=520,MOD=1e9+7;
int f[MN][MN],ans,n,a[MN];

void solvedp(int x){
    memset(f,0,sizeof(f));
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<256;j++){
            if(i==x) f[i][j]=f[i-1][j];
            else f[i][j]=(f[i-1][j]+f[i-1][j^a[i]])%MOD;
        }
    }
}

signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        solvedp(i);
        for(int j=a[i];j<256;j++){
            (ans+=f[n][j])%=MOD;
        }
    }
    cout<<ans;
    return 0;
}

USACO09NOV A Coin Game S

注意到是题目中的关键信息，取的硬币数和上一步取的操作有关，这个直接思考不太好，我们考虑进行 DP 求解。

设 f(i,j) 表示取到第 i 个金币，取金币的上限为 j 先手取的最大价值，转移是显然的，考虑记忆化搜索实现比较好些，但是转移是 O(n^3) 的。

考虑优化，注意到我们 f(i,j) 在记忆化搜索是 1 \rightarrow n 取搜索的，那么我们 f(i,j) 的答案其实包含了 f(i,j-1)，那么我们可以直接搜 f(i,j-1) 没有的部分，即 (x+lim,lim\times 2)，其中 lim 为金币上限，那么这样搜索复杂度就是 O(n^2) 的了。

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=2e3+15;
int f[MN][MN],n,s[MN],c[MN];

int dfs(int x,int y){
    y=min(y,n-x+1);
    if(~f[x][y]) return f[x][y];
    if(x+y>n) return s[x];
    if(!y) return 0;
    int ans=dfs(x,y-1);
    ans=max(ans,s[x]-dfs(x+y,y<<1));
    return f[x][y]=ans;
}

signed main(){
    cin>>n;
    memset(f,-1,sizeof(f));
    for(int i=1;i<=n;i++){
        cin>>c[i];
    }
    for(int i=n;i>=1;i--) s[i]=s[i+1]+c[i];
    cout<<dfs(1,2);
    return 0;
}

ZJOI2009 取石子游戏

神题：

再次复读：

神仙题.jpg。ZJOI 是真的神仙。
发现 SG 函数等东西完全找不到规律，无奈只能翻题解。

看 wsyhb的题解吧，他说的肯定比我好 www。

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=1520;
int L[MN][MN],R[MN][MN],n,a[MN];

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        L[i][i]=R[i][i]=a[i];
    }
    for(int len=2;len<=n;len++){
        for(int l=1;l+len-1<=n;l++){
            int r=l+len-1;
            int x=a[r],xl=L[l][r-1],xr=R[l][r-1];
            if(x==xr) L[l][r]=0;
            else if(x>=xl&&x<xr) L[l][r]=x+1;
            else if(x>xr&&x<=xl) L[l][r]=x-1;
            else L[l][r]=x;
            x=a[l],xl=L[l+1][r],xr=R[l+1][r];
            if(x==xl) R[l][r]=0;
            else if(x>=xr&&x<xl) R[l][r]=x+1;
            else if(x>xl&&x<=xr) R[l][r]=x-1;
            else R[l][r]=x;
        }
    }
    if(L[2][n]==a[1]) cout<<0<<'\n';
    else cout<<1<<'\n';
}

int main(){
    int T;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

P4363

对于这种博弈论的题，基本上理解就能想到了把状态压出来，然后做记忆化搜索。

对于落子的限制条件是，上方和左方的格子要么是棋子要么是边界。

我们可以考虑直接状压落子的状态，存每一行铺到了哪个位置，这个方法的复杂度显然为 O(n^m) 的。

我们发现，一个棋子想要存在的条件是上方和左方的所有格子全部被棋子填满。

那么，对于任意时刻，棋盘上的棋子构成一个锯齿形。

那有用的情况有多少种呢，我们考虑从锯齿状的起点开始走，我们最多往右走 n 步，往下走 m 步，路径数论是多少？显然为 \dbinom{n+m}{n} 种。

算出来就是 184756 中，考虑暴力 11 进制状压，让后用 map 存就可以了。

注意开 long long。

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=15,INF=1e18;
int a[MN][MN],b[MN][MN],ed,n,m;
map<int,int> ans,vis;

int dfs(int x,int y){
    if(x==ed) return 0;
    if(vis[x]==1) return ans[x];
    vis[x]=1;
    int p=1,sum=y?INF:-INF,tmp=x;
    int c[MN]{};
    c[0]=INF;
    for(int i=1;i<=n;i++) c[i]=tmp%11,tmp/=11;
    if(y){
        for(int i=1;i<=n;i++){
            if(c[i]<min(c[i-1],m)) sum=min(sum,dfs(x+p,y^1)-b[i][c[i]+1]);
            p*=11;
        }
    }
    else {
        for(int i=1;i<=n;i++){
            if(c[i]<min(c[i-1],m)) sum=max(sum,dfs(x+p,y^1)+a[i][c[i]+1]);
            p*=11;
        }
    }
    ans[x]=sum;
    return ans[x];
}

signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>b[i][j];
        }
    }
    for(int i=1;i<=n;i++) ed=ed*11+m;
    cout<<dfs(0,0);
    return 0;
}

HNOI2010 取石头游戏

这种题的模型就是：“我可以死，但你要死的更惨！”。

由于得分之和是定值，且双方都想让自己分数最大，我们不妨令 val 表示先手得分与后手得分的差，类似于对抗搜索，那么先手要让 val 尽可能大，而后手尽量让 val 小。

而取石子，可以转化为两端分别有一个栈，可以从栈顶取石子，中间有若干个双端队列，可以从其两端取石子。

让后我们对连续的三个元素进行分类讨论，分别有：

递增
递减
先增后减
先减后增

因为我们取的方向是从外到内的，我们接下来分类讨论。

递增：我们肯定要放到后面选择，因为一旦先手选择，后手一定能够选择比他大的数的。
递减：优先选择递减里面最大的。
先增后减与先减后增：到了这个情况的化，后手肯定选择中间的情况，先手肯定会选择左后两个。考虑证明：
- 如果先手发现选取最优的话，他会选走这个。由于先增加后减少，所以当前对于后手而言，选取比上一次最优还优秀的点肯定是最佳的，随意肯定会选中间那个。
- 若不一定最优秀，那么可能会选取其他更优的决策点。但是最终还是要选择这个剩下的点。我们直接把这个情况压成一个点的情况，这样所有的双段队列和栈就不会出现任何线增加后减少的情况了。

贪心即可：

#include<bits/stdc++.h>

#define maxn 2000010
using namespace std;
typedef long long ll;
template < typename T > inline void read(T & x) {
    x = 0;
    char c = getchar();
    bool flag = false;
    while (!isdigit(c)) {
        if (c == '-') flag = true;
        c = getchar();
    }
    while (isdigit(c)) {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    if (flag) x = -x;
}
ll n, sum, val, s, L, R, tot;
ll l[maxn], r[maxn], v[maxn];
bool tag[maxn];
bool cmp(const ll & a,
    const ll & b) {
    return a > b;
}
int main() {
    read(n), r[0] = 1, l[n + 1] = n;
    for (int i = 1; i <= n; ++i)
        read(v[i]), sum += v[i], l[i] = i - 1, r[i] = i + 1, tag[i] = (v[i] != 0);
    for (int i = 3; i <= n; i = r[i])
        while (tag[l[l[i]]] && tag[l[i]] && tag[i] && v[l[i]] >= v[l[l[i]]] && v[l[i]] >= v[i])
            v[i] = v[l[l[i]]] + v[i] - v[l[i]], r[l[l[l[i]]]] = i, l[i] = l[l[l[i]]];
    L = r[0], R = l[n + 1];
    while (v[L] >= v[r[L]] && tag[L] && tag[r[L]]) s += v[r[L]] - v[L], L = r[r[L]];
    while (v[R] >= v[l[R]] && tag[R] && tag[l[R]]) s += v[l[R]] - v[R], R = l[l[R]];
    for (int i = L; i <= R; i = r[i])
        if (tag[i])
            v[++tot] = v[i];
    sort(v + 1, v + tot + 1, cmp), v[++tot] = s;
    for (int i = 1; i <= tot; ++i) {
        if (i & 1) val += v[i];
        else val -= v[i];
    }
    printf("%lld %lld", (sum + val) / 2, (sum - val) / 2);
    return 0;
}

6. 后言

蒟蒻博弈论就学到这里了，如果还有后面的进一步学习，还是会更新内容了。

这篇文章，我感觉还是欠缺一部分 SG 解题的部分。见的题还是不太多，坑还是要补的 www。

看在这么用心的份上，不要脸的求赞 www。

分享

0. 前言

1. 组合博弈与博弈基础

1.1 公平组合与非公平组合

1.2 先手，后手，必胜必输局面

1.3 先手必胜与先手必败

1.4 必胜点与必败点

2. 基本公平组合游戏

2.1 Nim 游戏

2.2 Nim升级版——NimK

2.3 阶梯 Nim 游戏

2.4 巴什博弈 Bash Game

2.5 威佐夫博弈

2.6 斐波那契博弈

2.7 总结

3. SG与有向图游戏

3.1 有向图游戏

3.2 Mex 运算

3.3 SG 函数

3.4 必胜与必败判定,SG 定理

3.5 NIM 游戏与 SG 函数的结合

3.6 实际应用

4. 反常游戏与反SG游戏

4.1 Anti-Nim游戏

4.2 反 SG 游戏

5. 博弈论及与其他知识结合

5.0 操作手册

5.1 例题

6. 后言

参考

评论