SG函数和SG定理(Sprague_Grundy)

 

一、必胜点和必败点的概念

       P点：必败点，换而言之，就是谁处于此位置，则在双方操作正确的情况下必败。
       N点：必胜点，处于此情况下，双方操作均正确的情况下必胜。
必胜点和必败点的性质：
        1、所有终结点是 必败点 P 。（我们以此为基本前提进行推理，换句话说，我们以此为假设）
        2、从任何必胜点N 操作，至少有一种方式可以进入必败点 P。
        3、无论如何操作，必败点P 都只能进入 必胜点 N。
我们研究必胜点和必败点的目的时间为题进行简化，有助于我们的分析。通常我们分析必胜点和必败点都是以终结点进行逆序分析。我们以hdu 1847 Good Luck in CET-4 Everybody!为例：
当 n = 0 时，显然为必败点，因为此时你已经无法进行操作了
当 n = 1 时，因为你一次就可以拿完所有牌，故此时为必胜点
当 n = 2 时，也是一次就可以拿完，故此时为必胜点
当 n = 3 时，要么就是剩一张要么剩两张，无论怎么取对方都将面对必胜点，故这一点为必败点。
以此类推，最后你就可以得到；
      n    ：   0    1    2    3    4   5    6 ...
position：  P    N   N    P   N   N   P ...
你发现了什么没有，对，他们就是成有规律，使用了 P/N来分析，有没有觉得问题变简单了。

二、Sprague-Grundy定理（SG定理）

        游戏和的SG函数等于各个游戏SG函数的Nim和。这样就可以将每一个子游戏分而治之，从而简化了问题。而Bouton定理就是Sprague-Grundy定理在Nim游戏中的直接应用，因为单堆的Nim游戏 SG函数满足 SG(x) = x。

（NIM游戏：https://blog.csdn.net/luomingjun12315/article/details/45479073）

三、Sprague-Grundy函数（SG函数）

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

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

四、例题

http://poj.org/problem?id=2975

http://poj.org/problem?id=2960

https://ac.nowcoder.com/acm/contest/338/I

五、参考文章

https://blog.csdn.net/luomingjun12315/article/details/45555495

https://www.cnblogs.com/ECJTUACM-873284962/p/6921829.html

https://blog.csdn.net/kamisama123/article/details/77649118

 

本文地址：https://blog.csdn.net/weixin_43272781/article/details/85956967