【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日

相关文章

  • 贪心算法基础及leetcode例题

    理论 本质:找到每个阶段的局部最优,然后去推导得到全局最优两个极端:常识&&很难: 很多同学通过了贪心的题目,但都不知道自己用了贪心算法,因为贪心有时候就是常识性的推导,所以会认为本应该就这么做! 套路:贪心没有套路,说白了就是常识性推导加上举反例做题的时候,只要想清楚 局部最优 是什么,如果推导出全局最优,其实就够了。 贪心算法一般分为如下…

    算法与数据结构 2023年4月20日
    00
  • 【JavaScript快速排序算法】不同版本原理分析

    说明 快速排序(QuickSort),又称分区交换排序(partition-exchange sort),简称快排。快排是一种通过基准划分区块,再不断交换左右项的排序方式,其采用了分治法,减少了交换的次数。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速…

    算法与数据结构 2023年4月18日
    00
  • C语言数据结构之简易计算器

    C语言数据结构之简易计算器攻略 简介 这是一个基于C语言的简易计算器,可以实现加、减、乘、除四个基本运算。 实现步骤 首先,需要声明四个变量,分别表示运算符、被加数、被减数、被乘数和被除数。 char op; double n1, n2, result; 然后,需要通过scanf()函数获取用户输入的运算符和数字。 printf(“请输入运算符和数字:\n”…

    数据结构 2023年5月17日
    00
  • Python利用三层神经网络实现手写数字分类详解

    以下是关于“Python利用三层神经网络实现手写数字分类详解”的完整攻略: 简介 神经网络是一种模拟人脑神经元工作方式的计算模型,它可以用于分类、回归、聚类等任务。在本教程中,我们将介绍如何使用Python实现一个三层神经网络,并使用MNIST数据集进行手写数字分类。 神经网络基本概念 神经网络由多个神经元组成,每个神经元接收多个输入,经过加权和和激活函数处…

    python 2023年5月14日
    00
  • Lua学习笔记之数据结构

    下面开始对”Lua学习笔记之数据结构”的完整攻略进行详细说明。 一、前言 在学习Lua时,数据结构是非常重要的一个方面,掌握了数据结构,就可以更好地编写Lua程序,提高程序的性能和可读性。本篇攻略主要介绍四种Lua数据结构:数组、表、字符串和函数,分别介绍其含义、特点、创建方法以及基本操作。 二、数组 2.1 数组的定义和创建 Lua中的数组是一种类似于C语…

    数据结构 2023年5月17日
    00
  • python机器学习朴素贝叶斯算法及模型的选择和调优详解

    以下是关于“Python机器学习朴素贝叶斯算法及模型的选择和调优详解”的完整攻略: 简介 朴素贝叶斯算法是一种常见的分类算法,它基于贝叶斯定理和特征条件独立假设。本教程将介绍如何使用Python实现朴素贝叶斯算法,并讨论如何选择和调优模型。 步骤 1. 导入库和数据 首先,我们需要导入必要的库,包括numpy、pandas和sklearn。在Python中,…

    python 2023年5月14日
    00
  • C语言数据结构 双向链表的建立与基本操作

    C语言数据结构 双向链表的建立与基本操作 双向链表的定义 双向链表是一种常见的线性数据结构,它由多个结点组成,每个结点有两个指针,一个指向前一个结点,一个指向后一个结点。对于一个双向链表,我们可以获得其第一个结点和最后一个结点的指针,也可以沿着链表从前往后或从后往前遍历链表的每个结点。 双向链表的建立 我们首先需要定义一个双向链表的结点类型,包括两个指针,一…

    数据结构 2023年5月17日
    00
  • python搜索算法原理及实例讲解

    Python搜索算法原理及实例讲解 搜索算法是计算机科学中的基本问题之一,它的目的是在一个数据集合中查找特定的元素。在Python中,可以使用多种搜索算法来查找数据。本文将介绍Python的搜索算法原理及实例讲解。 搜索算法原理 1. 线性搜索 线性搜索是一种简单的搜索算法,它的基本思想是从数据集合的第一个元素开始,逐个比较每个元素,直到找到目标元素或遍历完…

    python 2023年5月13日
    00
合作推广
合作推广
分享本页
返回顶部