【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时,我们可以画出如下的博弈图。

【ACM博弈论】SG函数入门(2):博弈树SG函数的转移与子游戏的合并

我们可以发现,每一个点都有至多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函数。

【ACM博弈论】SG函数入门(2):博弈树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;
}

我们随机输入一些数据,打个表,得到如下结果:

【ACM博弈论】SG函数入门(2):博弈树SG函数的转移与子游戏的合并
我们发现这个在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技术站

(0)
上一篇 2023年4月17日
下一篇 2023年4月17日

相关文章

  • 动态开点线段树&线段树合并学习笔记

    动态开点线段树 使用场景 \(4 \times n\) 开不下。 值域需要平移(有负数)。 什么时候开点 显然,访问的节点不存在时(只会在修改递归时开点)。 trick 区间里面有负数时,\(mid = (l + R – 1) / 2\)。 防止越界。 例如区间 \([-1,0]\)。 开点上限 考虑到 update 一次最多开 \(\log V\) 个点(…

    算法与数据结构 2023年4月17日
    00
  • Java数据结构之线性表

    Java数据结构之线性表完整攻略 什么是线性表 线性表是n个数据元素的有限序列,其中数据元素的类型相同。线性表中含有首元素和末元素。若表中只有一个数据元素,则该数据元素既是首元素又是末元素,这个数据元素成为线性表的唯一元素。 线性表的基本操作 初始化操作 initList(List L):建立一个空的线性表L 插入操作 insert(List L, int …

    数据结构 2023年5月17日
    00
  • 【ACM组合数学 | 错排公式】写信

    题目链接:https://ac.nowcoder.com/acm/contest/54484/B 题意很简单,但是数据范围偏大。 错排公式 首先来推导一下错排公式: \[D(n) = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!} \] 设一个函数: \[S_i表示一个排列中p_i = i的方案数 \] 那么我们可以知道: \[D(n) …

    算法与数据结构 2023年4月17日
    00
  • python实现人工蜂群算法

    下面是详细讲解“python实现人工蜂群算法”的完整攻略,包含两个示例说明。 人工蜂群算法简介 人工蜂群算法(Artificial Bee Colony,ABC)是一种基于蜜蜂觅食行为的优化算法。在ABC算法中,蜜蜂分为三种角色:雇佣蜜蜂、侦查蜜蜂和观察蜜蜂。雇佣蜜蜂和侦查蜜蜂负责搜索解空间,观察蜜蜂负责评估解的质量。ABC算法的优点是易于实现,收敛速度快,…

    python 2023年5月14日
    00
  • Java数据结构二叉树难点解析

    Java数据结构二叉树难点解析 什么是二叉树 二叉树是一种非常常见的数据结构,它具有以下特点: 每个节点都最多有两个子节点。 左子节点的值小于等于父节点的值,右子节点的值大于等于父节点的值。 二叉树可以用递归的方式实现,如下所示: class TreeNode { int val; TreeNode left; TreeNode right; TreeNod…

    数据结构 2023年5月17日
    00
  • python实现全排列代码(回溯、深度优先搜索)

    下面是详细讲解“Python实现全排列代码(回溯、深度优先搜索)”的完整攻略,包含两个示例说明。 全排列算法简介 全排列是指将一组数按一定顺序进行排列,通常用于密码学、组合数学等领域。全排列算法有多种实现方式,其中回溯和深度优先搜索是两种常见的方法。 回溯法实现全排列 下面是Python实现回溯法全排列的代码: def backtrack_permute(n…

    python 2023年5月14日
    00
  • 数据结构与算法之手撕排序算法

    数据结构与算法之手撕排序算法 本篇攻略介绍如何手撕常见的排序算法。 冒泡排序 冒泡排序是一种通过不断交换相邻元素来排序的方法。它的时间复杂度为$O(n^2)$。 def bubble_sort(nums): for i in range(len(nums)): for j in range(len(nums)-i-1): if nums[j] > nu…

    数据结构 2023年5月17日
    00
  • C语言数据结构之学生信息管理系统课程设计

    C语言数据结构之学生信息管理系统课程设计 介绍 本文讲解学生信息管理系统的设计过程,包括需求分析、设计思路、实现步骤等。 需求分析 学生信息管理系统是一种常见的数据结构应用场景。通过该系统,可以实现对学生信息的有效管理和查询。在设计之前,我们需要明确系统的需求和功能,包括: 学生信息的录入、删除、修改和查询; 各类信息的统计和分析,如学生总数、男女比例等; …

    数据结构 2023年5月17日
    00
合作推广
合作推广
分享本页
返回顶部