上一篇文章我们讲了两种经典的博弈模型:《【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函数转移方程
\]
说人话就是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原创,创作不易,如果对您有帮助,欢迎小伙伴们点赞?、收藏⭐、留言?
原文链接:https://www.cnblogs.com/eriktse/p/17306278.html
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:【ACM博弈论】SG函数入门(2):博弈树SG函数的转移与子游戏的合并 - Python技术站