乐趣区

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

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

🎈 本文由 eriktse 原创,创作不易,如果对您有帮忙,欢送小伙伴们点赞👍、珍藏⭐、留言💬

退出移动版