LibreOJ – 10248 / P2599

原题来自：ZJOI 2009

题意

在研究过 Nim 游戏及各种变种之后，Orez 又发现了一种全新的取石子游戏，这个游戏是这样的：

有 \(n\) 堆石子，将这 \(n\) 堆石子摆成一排。游戏由两个人进行，两人轮流操作，每次操作者都可以从最左或最右的一堆中取出若干颗石子，可以将那一堆全部取掉，但不能不取，不能操作的人就输了。

Orez 问：对于任意给出一个初始一个局面，是否存在先手必胜策略。

数据范围 \(1 \leq n \leq 1e3\).

题解

进行一个区间dp:

令 \(left_{i,j}\) 为区间 \(i \sim j\), \(a_i\) 为第 \(i\) 堆石子的数量, 左侧加一个为 \(left_{i,j}\) 的数会变成必败态. \(right_{i,j}\) 为区间 \(i \sim j\), 右侧加一个为 \(right_{i,j}\) 的数会变成必败态.

这里证明为啥有且仅有一个 \(left_{i,j}\) 满足情况:

• 为啥最多只有一个: 若有两个必败态, 则必然可以从一个转移到另一个, 就与必败矛盾, 故最多只能有一个.
• 为啥有: 若没有, 则一定为必胜态, 那应该存在一个操作转移到必败态, 左边无论为啥都是必胜的, 所以先手应该取右边的石子, 得到一个必败态, 那么这个必败态改变左侧石子个数还是必败的, 则一个区间对应无限个 \(left\), 与上面矛盾.

那么如何dp转移呢:

• 首先对于 \(left_{i,j}\), 显然多一个同为 \(a_i\) 的石子堆是必败的.
• 对于 \(left_{i,j}\), 我们记 \(l = left_{i,j – 1}, r = right_{i,j – 1}, x = a_i\):
  • 若 \(x = r\), 则区间 \(i \sim j\) 就是必败态, \(left_{i,j} = 0\).
  • 若 \(x < l\) 且 \(x < r\), 我们令 \(left_{i,j} = x\): 先手选择任一侧, 后手在另一侧进行同样操作, 则先手会先将一侧的石子取完, 这时候变成了必胜态, 故为先手必败.
  • 若 \(x \leq l\) 且 \(x > r\), 我们令 \(left_{i,j} = x – 1\): 若先手选左侧让左侧变为 \(y\), \(y < r\) 则后手让右侧变为 \(y\), 转换为第二种情况; \(y \geq r\) 则后手让右侧变为 \(y + 1\), 还是这种情况. 若先手选右侧让右侧变为 \(y\), \(y < r\) 则后手让左侧变为 \(y\), 转换为第二种情况; \(y = r\) 则后手让左侧变为 \(0\), 为先手必败; \(y > r\) 则后手让左侧变为 \(y – 1\), 还是这种情况.
  • 若 \(x \geq l\) 且 \(x < r\), 我们令 \(left_{i,j} = x + 1\): 若先手选左侧让左侧变为 \(y\), \(y < l\) 则后手让右侧变为 \(y\), 转换为第二种情况; \(y = l\) 则后手让右侧变为 \(0\), 为先手必败; \(y \geq l\) 则后手让右侧变为 \(y – 1\), 还是这种情况. 若先手选右侧让右侧变为 \(y\), \(y < l\) 后手让左侧变为 \(y\), 转化为第二种情况; \(y \geq l\) 后手让左侧变为 \(y + 1\), 还是这种情况.
  • 若 \(x > l\) 且 \(x > r\), 令 \(left_{i,j} = x\): 先手操作后后手可以转化为当前情况或者上面几种情况, 故还是先手必败.
• 对于 \(right_{i,j}\), 则与求 \(left_{i,j}\) 对称即可.

最后判断 \(a_1\) 与 \(left_{2,n}\) 是否相等即可.

时间复杂度 \(O(n ^ 2)\).

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> left(n + 1, vector<int>(n + 1)), right(n + 1, vector<int>(n + 1));
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i + 1 < n; i++) {
        if (i == 0)
            for (int j = 2; j <= n; j++) left[j][j] = right[j][j] = a[j];
        else {
            for (int j = 2; j + i <= n; j++) {
                int l = left[j][j + i - 1], r = right[j][j + i - 1];
                int x = a[j + i];
                if (x == r)
                    left[j][j + i] = 0;
                else if (x < l && x < r)
                    left[j][j + i] = x;
                else if (x < l && x > r)
                    left[j][j + i] = x - 1;
                else if (x >= l && x < r)
                    left[j][j + i] = x + 1;
                else if (x > l && x > r)
                    left[j][j + i] = x;
                l = right[j + 1][j + i], r = right[j + 1][j + i];
                x = a[j];
                swap(l, r);
                if (x == r)
                    right[j][j + i] = 0;
                else if (x < l && x < r)
                    right[j][j + i] = x;
                else if (x < l && x > r)
                    right[j][j + i] = x - 1;
                else if (x >= l && x < r)
                    right[j][j + i] = x + 1;
                else if (x > l && x > r)
                    right[j][j + i] = x;
            }
        }
    }
    if (a[1] == left[2][n]) {
        cout << 0 << '\n';
    } else {
        cout << 1 << '\n';
    }
}

参考: 题解 P2599 【[ZJOI2009]取石子游戏】, 作者 Jason_Yvan.