算法学习————SG函数和SG定理

本文主要是介绍算法学习————SG函数和SG定理，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

其实我自己也不是很明白吧

SG函数应用的场景

组合游戏

在竞赛中，组合游戏的题目一般有以下特点

1. 题目描述一般为A，B，2人做游戏

2. A，B交替进行某种游戏规定的操作，每操作一次，选手可以在有限的操作（操作必须合法）集合中任选一种。

3. 对于游戏的任何一种可能的局面，合法的操作集合只取决于这个局面本身，不取决于其它因素（跟选手，以前的所有操作无关）

4. 如果当前选手无法进行合法的操作，则为负

必胜点和必败点的概念

必败点(P点) 前一个(previous player)选手将取胜的点称为必败点

必胜点(N点) 下一个(next player)选手将取胜的点称为必胜点

SG函数

先定义mex(minimal excludant)运算，这是施加于一个集合的运算，表最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3

对于任意状态x，定义SG(x) = mex(S),其中S是x后继状态的SG函数值的集合。如x有三个后继状态a，b，c的SG值分别为SG(a)，SG(b)，SG(c)，那么SG(x)=mex{SG(a)，SG(b)，SG(c)}。 这样当我没有后继状态的时候集合S的终态必然是空集，所以SG函数的终态为SG(x)=0，当且仅当x为必败点P时。

虽然我也不知道为什么要这么求，但是数学就是这么神奇呀

SG定理

游戏和的SG函数等于各子游戏的SG函数的Nim和。

公式说明：\(SG(x_1,x_2,x_3\dots x_n) = SG(x_1)\bigoplus SG(x_2)\dots\bigoplus SG(x_n)\)

应用

具体怎么应用呢？我可以递归求出一部分情况的SG值，然后瞪眼发现规律

例题：[SDOI2009]E&D

`

这篇关于算法学习————SG函数和SG定理的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！