上一篇文章咱们讲了两种经典的博弈模型：《【ACM博弈论】SG函数入门（1）：从巴什博奕到尼姆游戏》，这一节咱们开始解说SG函数。

作者：Eriktse
简介：19岁，211计算机在读，现役ACM银牌选手力争以通俗易懂的形式解说算法！❤️欢送关注我，一起交换C++/Python算法。（优质好文继续更新中……）
浏览原文取得更好浏览体验：https://www.eriktse.com/algorithm/1111.html

在理解SG函数之前，咱们须要晓得博弈图。

博弈图

就比方Bash博弈，当n=7,m=3时，咱们能够画出如下的博弈图。

咱们能够发现，每一个点都有至少2个后继状态（即出点），这个是能够通过Bash推出来的。

其余博弈题大多也能够相似的推出一个这样的图。

SG函数

SG函数能够了解为一个用于示意博弈图中节点状态的一个函数。同时sg(x) = n还示意节点x的出点形成一个汇合{y | 0 <= sg(y) <= n - 1}，也就是说x能够达到所有sg小于它本人的sg的点。

就比方上图，咱们规定必败态的sg = 0，必胜态的sg != 0。于是咱们能够晓得sg(0) = 0，而后往回推。

sg函数转移方程

$$sg(x) = mex({y | y \in out[x]})$$

说人话就是x的sg是其所有出点的sg形成的汇合做mex运算，mex示意汇合中最小的没呈现过的自然数。

代码个别为：

int mex(set<int>& st){    for(int i = 0;; ++ i)        if(st.find(i) == st.end())//如果找不到i            return i;}

于是咱们能够推出下面这个博弈图的所有点的sg函数。

留神是依据所有出点推出以后点，只有所有出点都确定了，以后点的sg能力确定，有点像建反图而后topo，然而个别咱们会间接写一个记忆化搜寻而后打表找法则。在解决带环的图时须要具体情况具体分析。

下面这张图咱们很容易找出法则，就是0 1 2 0 1 2....

子游戏的合并

Nim定理：全局后果等于子游戏SG的异或和。

咱们昨天学过Nim博弈，他是有n堆石子，每次能够选一堆拿走若干个。那么咱们能够将子游戏看做是一堆石子，每堆石子的个数是 (sg) 个，而后取走若干个石子类比为将sg转移到更小的sg。

当初咱们就能够解决一些形象的博弈问题了。

做题个别思路

个别是三步：找出SG转移方程，打表找法则，子游戏合并。

为什么须要打表找法则呢，因为个别题目给的数据会很大，且个别会有较强的规律性，打表找到法则就行无需证实，证实对于比赛来说太侈靡了，而且没太大意义。

例题：AtCoder Beginner Contest 297 - Constrained Nim 2

先写一个_sg()函数用于打表：

int _sg(int x){    if(x == 0)return 0;    set<int> st;    for(int i = max(0ll, x - r);i <= x - l; ++ i)st.insert(_sg(i));    for(int i = 0; ; ++ i )if(st.find(i) == st.end())return i;}

咱们随机输出一些数据，打个表，失去如下后果：


咱们发现这个在l，r给定的状况下，sg(x)的值十分有法则，能够用上面这个表达式间接表白：

int sg(int x){    return x % (l + r) / l;}

最初把所有子游戏的sg异或起来就是最终答案。

AC代码：

#include <bits/stdc++.h>#define int long longusing namespace std;const int N = 2e5 + 9;int a[N], l, r;int sgk(int x){    if(x == 0)return 0;    set<int> st;    for(int i = max(0ll, x - r);i <= x - l; ++ i)st.insert(sgk(i));    for(int i = 0; ; ++ i )if(st.find(i) == st.end())return i;}int sg(int x){    return x % (l + r) / l;}signed main(){    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);        int n;cin >> n >> l >> r;    for(int i = 1;i <= n; ++ i)cin >> a[i];    // for(int i = 0;i <= 20; ++ i)        // cout << "sg(" << i << ") = " << sgk(i) << " = " << sg(i) << '\n';    int ans = 0;    for(int i = 1;i <= n; ++ i)ans ^= sg(a[i]);    if(ans)cout << "First" << '\n';    else cout << "Second" << '\n';        return 0;}
本文由eriktse原创，创作不易，如果对您有帮忙，欢送小伙伴们点赞、珍藏⭐、留言