博弈论，NIM游戏，台阶型，集合型，SG函数，详解

文章目录

• • 一、Nim游戏
  • • 1.1问题描述
    • 1.2定理
    • • 1.2.1定理内容
      • 1.2.2定理证明
      • 1.3OJ练习
      • • 1.3.1模板OJ
        • 1.3.2P1247 取火柴游戏
        • 二、台阶型Nim游戏
        • • 2.1问题描述
          • 2.2结论及证明
          • • 2.2.1结论
            • 2.2.2结论证明
            • 2.3OJ练习
            • • 2.3.1Georgia and Bob
              • 三、有向图游戏，SG函数
              • • 3.1定义
                • • 3.1.1有向图游戏
                  • 3.1.2Mex运算
                  • 3.1.3SG函数
                  • 3.1.4有向图游戏的和
                  • 3.2定理及证明
                  • • 3.2.1定理内容
                    • 3.2.1定理证明
                    • 3.3有向无环图上的棋子游戏
                    • • 3.3.1问题描述
                      • 3.3.2思路分析
                      • 3.3.3原题链接
                      • 3.3.4AC代码
                      • 3.4 集合型NIM游戏
                      • • 3.4.1问题描述
                        • 3.4.2思路分析
                        • 3.4.3原题链接
                        • 3.4.4AC代码
                        • 3.5普通NIM游戏与有向图游戏的关系
                        • 3.6OJ练习-POJCutting Game
                        • • 3.6.1原题链接
                          • 3.6.2思路分析
                          • 3.6.3AC代码

                            ---

                            一、Nim游戏

                            1.1问题描述

                            甲，乙两个人玩 nim 取石子游戏。

                            nim 游戏的规则是这样的：地上有 n 堆石子（每堆石子数量小于 10^4），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手，且告诉你这 n 堆石子的数量，他想知道是否存在先手必胜的策略。

                            上面这种游戏被称为NIM博弈。对于游戏过程中面临的状态，如果玩家在这种状态下无论进行任何行动，都会输掉游戏，我们称该状态为必败态。同样的，如果玩家在这种状态下无论进行任何行动，都会赢得游戏，我们称该状态为必胜态。

                            1.2定理

                            1.2.1定理内容

                            NIM博弈先手必胜，当且仅当 A1 ^ A2 ^ …… ^ An ≠ 0

                            1.2.2定理证明

                            下面采用的证明方法是NIM博弈问题常用证明方法：

                            • 证明：必胜态的后继状态至少存在一个必败态
                              • 若A1 ^ A2 ^ …… ^ An = s，设s最高位是第k位，则A1~An中有奇数个第k位为1，不妨从中取出Ai，那么Ai ^ s > n, res = 0; for (int i = 0, a; i > a, res ^= a; res ? cout _; while (_--) solve(); return 0;}

                                1.3.2P1247 取火柴游戏

                                原题链接

                                P1247 取火柴游戏 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

                                AC代码

                                #include #include using namespace std;#define int long longconst int N = 5e5 + 10, mod = 1e9 + 7;int n, res, a[N];void solve(){    cin >> n, res = 0;    for (int i = 0; i > a[i], res ^= a[i];    if (!res)    {        cout = a[i])            continue;        cout > 1;    if (c > n;    for (int i = 0; i > datas[i].i >> datas[i].x >> datas[i].y;        if (datas[i].i == 1)            id[++tot] = datas[i].x;    }    sort(id + 1, id + tot + 1);    tot = unique(id + 1, id + tot + 1) - id - 1;    build(1, 1, tot);    for (int i = 0, a, b; i  m >> k;    for (int i = 0, a, b; i > a >> b, addedge(a, b);    for (int i = 0, x; i > x, res ^= sg(x);    res ? cout  _;    while (_--)        solve();    return 0;}

                                3.4 集合型NIM游戏

                                3.4.1问题描述

                                给定m个整数组成的集合ai，给定n堆石子的数量bi。

                                两名玩家轮流操作，每次操作可以从任意一堆石子中拿取石子，每次拿取的石子数目必须是集合a中的整数，最后无法进行操作的人视为失败。

                                如果两人都采用最优策略，问先手是否必胜。

                                3.4.2思路分析

                                每堆石子都是孤立的，把n堆石子看做n个有向图游戏。然后利用SG定理即可。

                                对于子节点的寻找直接根据集合a内元素进行判断即可，省去了建图。

                                3.4.3原题链接

                                Problem - 1536 (hdu.edu.cn)

                                3.4.4AC代码

                                #include #include #include using namespace std;#define int long longconst int N = 10005, M = 105, mod = 1e9 + 7;int a[M], f[N], k, m, n;int sg(int x){    if (~f[x])        return f[x];    bool vis[M]{0};    for (int i = 0; i = a[i]; i++)        vis[sg(x - a[i])] = 1;    for (int i = 0;; i++)        if (!vis[i])            return f[x] = i;    return -1;}void solve(){    while (cin >> k, k)    {        memset(f, -1, sizeof f);        for (int i = 0; i > a[i];        sort(a, a + k), cin >> m;        while (m--)        {            cin >> n;            int res = 0;            for (int i = 0, x; i > x, res ^= sg(x);            res ? cout