集合NIM游戏——有向图游戏与SG函数

file

SG函数是解决博弈论问题的利器

在正式解题之前首先需要了解以下知识:

有向图游戏

给定一个有向无环图,图中有一个唯一的起点,在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动,每次可以移动一步,无法移动者判负。该游戏被称为有向图游戏。

任何一个公平组合游戏(ICG)都可以转化为有向图游戏。具体方法是,把每个局面看成图中的一个节点,并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。

介绍上述的有向图游戏是为了引入下面两条概念

mex运算

mex运算是对一个自然数集的运算,返回不属于该集合的最小自然数

例如对于集合G={0,1,2,4}$$mex$$(G)的结果是3

SG函数

SG函数是一个自变量为游戏状态(在有向无环图中是一个节点),返回值为自然数的特殊函数

对于一个公平组合游戏对应的有向无环图,我们规定游戏终点的SG值为0,并且对于其中任何一个非终点的节点x有

sg(x) = mex\{sg(y_1), sg(y_2),sg(y_3), \cdot \cdot \cdot ,sg(y_n)\}

其中y是x的所有后继节点

可以举一个例子,图中黑色数字是点的编号,蓝色数字是SG值:

file

首先4,8, 9号点作为终点SG值是0,而5, 7号点只有通向终点的一个后继,SG值为1 6号点只能通向SG值为1的7号点,所以SG(6) = 0 三点可以通向SG值分别为0,1的6,7号点,SG(3)=2

以此类推可以写出所有点的SG值

定理:有向图游戏的某个局面必胜,当且仅当该局面对应节点的SG函数值大于0。

证明方法和经典NIM游戏一样,可以证明:

  1. 游戏终点(必败局面)的SG值为0
  2. 任何一个SG值不为0的点,我们都可以通过一次操作使其走到一个SG值为0的点
  3. 当处在一个SG为0的点时,无论如何操作都不能走到下一个SG值为0的点

而对于多个有向图的游戏(在本例中具体为多堆石子),有定理:

由n个有向图组成的游戏的某个局面必胜,当且仅当该游戏所有起点的SG值异或和不为0

这一定理被称作Sprague-Grundy定理

这里有一篇CSDN的证明,思路和上述证明方法相似 file

讲完这些终于可以看本题了

本题可以抽象为有向图游戏,将每堆石子抽象为一个图,状态就是石子存量

因为可以选取的方法固定, 所以对于每个状态的SG值都是固定的(这一步有些难想:为什么状态信息只需要石子存量?)

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 10100, K = 200;

int s[K], f[N];
// s是所有可供选择的取法集合, f是对一个状态的sg值, 这里的一个状态具体来讲是石子的余量
// 需要注意的是,石子余量和操作次数,轮到谁操作都没有关系,和状态的出现位置等等也没有关系
// 将本例抽象成有向无环图之后, 状态信息只有石子存量, 每堆石子都是一个独立的图
// sg(x)中的x就是石子存量
int n, k;

// 本例中求取sg值的方法是记忆化搜索
int sg(int x)
{
    if(f[x] != -1)
        return f[x];

    unordered_set<int> T; // T是x点后继点的sg值集合
    for(int i = 1; i <= k; i++)
    {
        int d = s[i]; // 可选集合的第i个选项:拿d个
        if(x >= d)
        {
            // 如果可以拿就把后继节点的sg值加入集合
            // 这样看来应该是后序遍历
            T.insert(sg(x - d));
        }
    }

    // 求sg值的部分
    // 一个点的SG值是最小不属于后继点SG值的自然数
    // 如果他本身是终点,SG值就是0
    for(int i = 0; ; i++)
        if(!T.count(i))
            return f[x] = i; // 记忆化不能忘了,直接return i就飞了
}

int main()
{
    // ios::sync_with_stdio(false);
    cin >> k;

    for(int i = 1; i <= k; i++)
        cin >> s[i];

    int res = 0;
    cin >> n;
    memset(f, -1, sizeof f);
    for(int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        res ^= sg(x); // 多个有向图游戏必胜当且仅当所有起点SG值异或和不为0
    }

    if(res)
        puts("Yes");
    else
        puts("No");

    return 0;
}

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注