关于c++:ACM博弈论SG函数入门2博弈树SG函数的转移与子游戏的合并

1次阅读

共计 1949 个字符，预计需要花费 5 分钟才能阅读完成。

上一篇文章咱们讲了两种经典的博弈模型：《【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(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 long
using 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;
}