阶梯博弈学习笔记

Leasier · 2022-11-25 22:14:46 · 个人记录

众所周知我不会博弈论。

首先给出阶梯博弈的一个基本模型：

• 你有一个 n 层的阶梯，其中第 i 层有 a_i 个石子，第 0 层没有石子。
• 每次先后手轮流选取任意一个阶梯 1 \leq i \leq n 上的任意 1 \leq j \leq a_i 颗石子并将其一道任意第 0 \leq k < i 层上。若轮到某人时已经没有选择，此人失败。
• 博弈双方足够聪明。

现在我们给出结论：

• 将所有奇数层上的石子抓出来视为 Nim 游戏中的石子堆，则原游戏获胜情况与新游戏相同。

接下来考虑如何感性理解这个结论。

这里要用到博弈题中的一个常用套路——后手模仿先手操作。

在这个模型中：

• 考虑其中一方在某一次操作中操作了偶数层上的石子，则另一方一定可以再模仿先手将这些石子移到另一个偶数层上。反复下去，最终这些石子就会在不改变先后手的前提下原封不动地移到 0。
• 考虑其中一方在某一次操作中操作了偶数层上的石子，则这些石子就会按上述在偶数层上的操作进行下去，最终无影响——即我们可以视作它们消失了。

于是我们可以将原问题等效为奇数层上石子的 Nim 游戏。

• [例 1] HDU4315 Climbing the Hill

现在我们先将 a 排序，然后来考虑一些特殊情况。

• k = 1

此时先手必胜。

• k = n

此时问题变为——先后手轮流操作，不能操作者失败。

我们将棋子右移视为中间的空格左移，并将这个问题转化一下：

• 有一个 n 层的阶梯，其中从上到下第 i 层的棋子数量为 a_i - a_{i - 1} - 1（这里我们钦定 a_0 = -1）。
• 每次我们可以将第 i 层的任意非零数量石子向下移动至第 i - 1 层。
• 先后手轮流操作，不能操作者失败。

然后你发现这就是一个阶梯博弈的模型！然后这种情况就解决了。

• 一般情况

我们来思考一下到底什么时候我们会关心第 k 个棋子。

当 k = 2，先后手都一定不会主动将第一个棋子移动到 0，此时我们可以认为 a_1 减去了 1。

你发现在其他情况下跟 k = n 是一致的。

然后这道题就做完了。

代码：

#include <iostream>
#include <algorithm>

using namespace std;

int a[1007];

int main(){
    int n, k;
    a[0] = -1;
    while (cin >> n >> k){
        for (int i = 1; i <= n; i++){
            cin >> a[i];
        }
        sort(a + 1, a + n + 1);
        if (k == 1){
            cout << "Nod" << endl;
        } else {
            int sg = 0;
            if (n % 2 == 1 && k == 2) a[1]--;
            for (int i = (n - 1) % 2 + 1; i <= n; i += 2){
                sg ^= a[i] - a[i - 1] - 1;
            }
            if (sg != 0){
                cout << "Nod" << endl;
            } else {
                cout << "Nic" << endl;
            }
        }
    }
    return 0;
}