草庐IT

【ACM博弈论】SG函数入门（2）：博弈树SG函数的转移与子游戏的合并

Eriktse Runtime 2023-04-21 原文

上一篇文章我们讲了两种经典的博弈模型：《【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原创，创作不易，如果对您有帮助，欢迎小伙伴们点赞?、收藏⭐、留言?

入门ACMcodestrongint算法与数据结构

有关【ACM博弈论】SG函数入门（2）：博弈树SG函数的转移与子游戏的合并的更多相关文章

  1. ruby - 在没有 sass 引擎的情况下使用 sass 颜色函数 - 2

    我想在一个没有Sass引擎的类中使用Sass颜色函数。我已经在项目中使用了sassgem，所以我认为搭载会像以下一样简单:classRectangleincludeSass::Script::FunctionsdefcolorSass::Script::Color.new([0x82,0x39,0x06])enddefrender#hamlengineexecutedwithcontextofself#sothatwithintemlateicouldcall#%stop{offset:'0%',stop:{color:lighten(color)}}endend更新:参见上面的#re

  2. ruby - 如果指定键的值在数组中相同，如何合并哈希 - 2

    我有一个这样的哈希数组:[{:foo=>2,:date=>Sat,01Sep2014},{:foo2=>2,:date=>Sat,02Sep2014},{:foo3=>3,:date=>Sat,01Sep2014},{:foo4=>4,:date=>Sat,03Sep2014},{:foo5=>5,:date=>Sat,02Sep2014}]如果:date相同，我想合并哈希值。我对上面数组的期望是:[{:foo=>2,:foo3=>3,:date=>Sat,01Sep2014},{:foo2=>2,:foo5=>5:date=>Sat,02Sep2014},{:foo4=>4,:dat

  3. ruby-on-rails - 在 ruby​​ 中使用 gsub 函数替换单词 - 2

    我正在尝试用ruby​​中的gsub函数替换字符串中的某些单词，但有时效果很好，在某些情况下会出现此错误？这种格式有什么问题吗NoMethodError(undefinedmethod`gsub!'fornil:NilClass):模型.rbclassTest"replacethisID1",WAY=>"replacethisID2andID3",DELTA=>"replacethisID4"}end另一个模型.rbclassCheck 最佳答案 啊，我找到了!gsub!是一个非常奇怪的方法。首先，它替换了字符串，所以它实际上修改了

  4. ruby - 在 Ruby 中有条件地定义函数 - 2

    我有一些代码在几个不同的位置之一运行:作为具有调试输出的命令行工具，作为不接受任何输出的更大程序的一部分，以及在Rails环境中。有时我需要根据代码的位置对代码进行细微的更改，我意识到以下样式似乎可行:print"Testingnestedfunctionsdefined\n"CLI=trueifCLIdeftest_printprint"CommandLineVersion\n"endelsedeftest_printprint"ReleaseVersion\n"endendtest_print()这导致:TestingnestedfunctionsdefinedCommandLin

  5. ruby - 在 Ruby 中按名称传递函数 - 2

    如何在Ruby中按名称传递函数？(我使用Ruby才几个小时，所以我还在想办法。)nums=[1,2,3,4]#Thisworks,butismoreverbosethanI'dlikenums.eachdo|i|putsiend#InJS,Icouldjustdosomethinglike:#nums.forEach(console.log)#InF#,itwouldbesomethinglike:#List.iternums(printf"%A")#InRuby,IwishIcoulddosomethinglike:nums.eachputs在Ruby中能不能做到类似的简洁？我可以只

  6. C51单片机——实现用独立按键控制LED亮灭（调用函数篇） - 2

    说在前面这部分我本来是合为一篇来写的，因为目的是一样的，都是通过独立按键来控制LED闪灭本质上是起到开关的作用，即调用函数和中断函数。但是写一篇太累了，我还是决定分为两篇写，这篇是调用函数篇。在本篇中你主要看到这些东西！！！1.调用函数的方法（主要讲语法和格式）2.独立按键如何控制LED亮灭3.程序中的一些细节（软件消抖等）1.调用函数的方法思路还是比较清晰地，就是通过按下按键来控制LED闪灭，即每按下一次，LED取反一次。重要的是，把按键与LED联系在一起。我打算用K1来作为开关，看了一下开发板原理图，K1连接的是单片机的P31口，当按下K1时，P31是与GND相连的，也就是说，当我按下去时

  7. LC滤波器设计学习笔记（一）滤波电路入门 - 2

    目录前言滤波电路科普主要分类实际情况单位的概念常用评价参数函数型滤波器简单分析滤波电路构成低通滤波器RC低通滤波器RL低通滤波器高通滤波器RC高通滤波器RL高通滤波器部分摘自《LC滤波器设计与制作》，侵权删。前言最近需要学习放大电路和滤波电路，但是由于只在之前做音乐频谱分析仪的时候简单了解过一点点运放，所以也是相当从零开始学习了。滤波电路科普主要分类滤波器：主要是从不同频率的成分中提取出特定频率的信号。有源滤波器：由RC元件与运算放大器组成的滤波器。可滤除某一次或多次谐波，最普通易于采用的无源滤波器结构是将电感与电容串联，可对主要次谐波（3、5、7）构成低阻抗旁路。无源滤波器：无源滤波器，又称

  8. 微信小程序开发入门与实战（Behaviors使用） - 2

    @作者:SYFStrive @博客首页:HomePage📜：微信小程序📌：个人社区（欢迎大佬们加入）👉：社区链接🔗📌：觉得文章不错可以点点关注👉：专栏连接🔗💃：感谢支持,学累了可以先看小段由小胖给大家带来的街舞👉微信小程序（🔥）目录自定义组件-behaviors    1、什么是behaviors    2、behaviors的工作方式    3、创建behavior    4、导入并使用behavior    5、behavior中所有可用的节点    6、同名字段的覆盖和组合规则总结最后自定义组件-behaviors    1、什么是behaviorsbehaviors是小程序中，用于实现

  9. git使用常见问题（提交代码，合并冲突） - 2

    文章目录git常用命令（简介，详细参数往下看）Git提交代码步骤gitpullgitstatusgitaddgitcommitgitpushgit代码冲突合并问题方法一：放弃本地代码方法二：合并代码常用命令以及详细参数gitadd将文件添加到仓库：gitdiff比较文件异同gitlog查看历史记录gitreset代码回滚版本库相关操作远程仓库相关操作分支相关操作创建分支查看分支：gitbranch合并分支：gitmerge删除分支：gitbranch-ddev查看分支合并图：gitlog–graph–pretty=oneline–abbrev-commit撤消某次提交git用户名密码相关配置g

  10. 【Java入门】使用Java实现文件夹的遍历 - 2

    遍历文件夹我们通常是使用递归进行操作，这种方式比较简单，也比较容易理解。本文为大家介绍另一种不使用递归的方式，由于没有使用递归，只用到了循环和集合，所以效率更高一些！一、使用递归遍历文件夹整体思路1、使用File封装初始目录，2、打印这个目录3、获取这个目录下所有的子文件和子目录的数组。4、遍历这个数组，取出每个File对象4-1、如果File是否是一个文件，打印4-2、否则就是一个目录，递归调用代码实现publicclassSearchFile{publicstaticvoidmain(String[]args){//初始目录Filedir=newFile("d:/Dev");Datebeg

随机推荐