题解：CF2234G Stripe, Token and Two Players

Emertyst · 2026-06-10 17:23:51 · 题解

CF2234G(Codeforces Round 1102 (Div. 2) G) 题解

中文题意

有一个包含 n + 1 个格子的长条，编号从 1 到 n + 1。初始时，编号为 1 的格子上有一个力量值为 1 的棋子，且格子 1, 2, \ldots, n 上分别写有数字 a_1, a_2, \ldots, a_n。

两名玩家进行游戏。在每一步中，玩家依次执行以下操作：

1. 假设棋子当前位于编号为 i 的格子上。
2. 玩家可以将棋子的力量值增加 0 到 a_i 之间的任意整数（包含 0 和 a_i）。
3. 然后，玩家将棋子向前移动一个不超过棋子当前力量值的正整数步，且移动后棋子不能移出该长条（即不能越过编号 n + 1 的格子）。

在移动后使棋子恰好落在编号为 n + 1 的格子上的玩家获胜。

在双方都采取最优策略的情况下，谁将获胜？

思路

首先，可以发现力量值超过 n 完全可以当做 n，因为这时先手可以直接跳到 n + 1 号格，直接赢。因此，我们可以想到一个 DP 解法。设 f(i, x) 表示『当前棋子在 i 号格子，棋子的力量值为 x 时，先手是否必胜（1 表示必胜，0 表示必败）』，可以写出转移方程：

这是正解的基础。

使用瞪眼法可以注意到，必败态的数量不会很多。可以发现，f(i, x) 是必败态的必要条件是 \forall j \in [i + 1, i + x], f(j, x) 都是必胜态。也就是说，对于固定的力量值 x，f(i, x) 为必败态的 i 的个数是 O \left(\dfrac{n}{x} \right) 数量级的。对于所有的 x，其之和为调和级数，数量级在 O(n \log n)。因此，遍历所有必败态是可行的。

接下来思考如何判断一个状态是否是必败态。如果根据上面的 DP 方程，我们实际需要实现一个『单点修改，对一个梯形的范围内取与』的数据结构，难以实现。因此考虑将查询的复杂度分摊给修改。我们将『离开第 i 号格时的力量值』这一状态拎出来，求出一个必败态 f(i, x) 后，给 i - x \leq j \leq i - 1 的所有 (j, x) 位置更新，表示『从 j 离开时的力量值为 x』的状态是必胜态；在计算 f(i, x) 时，查询 x \leq y \leq x + a_i 的所有 (i, y) 的位置，表示枚举『从 i 离开时所有可能的力量值』来计算 (i, x) 是否必胜。

虽然此时我们需要的数据结构仍然是二维的，但是我们能发现，查询只是一维的查询，而且我们枚举 i 是从大到小的顺序枚举，因此可以用时间戳来表示第一维，用一个一维的数据结构表示第二维。具体来说，我们把 f(i, x) 的更新拆解成两部分，在第 i - 1 时刻，x 的位置增加标记，在第 i - x - 1 时刻清除 x 位置的标记；查询时只需查询第 i 时刻的 [x, x + a_i] 位置有无标记即可。

我们可以维护一个集合，初始拥有 [1, n] 中的所有数；将『在 x 的位置增加标记』实现为在集合中删除 x；将『清除 x 位置的标记』实现为在集合中加入 x；将『查询第 i 时刻的所有必败态』实现为查询集合中长度为 a_i 的连续段，该连续段的左端点即为必败态的 x。

具体实现中，我们可以使用两个 set，其中第一个维护所有的连续段，第二个维护所有连续段的长度。查询时只需要不断查询第二个集合中的最大长度，直到最大长度小于等于 a_i。对于每个长度大于 a_i 的连续段 [l, r]，可以发现 j \in [l, r - a_i] 的所有 j 都是满足必败态条件的 j，将这些 j 全部删掉即可（由于删掉后不影响第 i 时刻的其他答案，所以在第 i 时刻就删除也是可以的），并将清除标记的修改暂存在一个优先队列中。

由于必败态数量只有 O(n \log n) 个，求出每个必败态的时间复杂度为 O(\log n)，每个必败态产生的更新复杂度为 O(\log n)，因此总的复杂度为 O(n \log^2 n)。

此外，也可以使用线段树维护『最长连续段的长度及其左端点』，也能通过本题，时间复杂度也是 O(n \log^2 n)。

代码

::::info[代码]

#include <iostream>
#include <queue>
#include <set>
using namespace std;
typedef pair<int, int> pii;
const int N = 1e5 + 5;
int t, n, ans, a[N];
priority_queue<pii> pq;
set<pii> st1, st2;
void insert(int l, int r) { st1.emplace(l, r), st2.emplace(r - l + 1, l); }
void erase(int l, int r) { st1.erase(st1.find(pii(l, r))), st2.erase(st2.find(pii(r - l + 1, l))); }
void insert(int x) {
    set<pii>::iterator nxt = st1.lower_bound(pii(x, x)), pre = (nxt == st1.begin() ? nxt : prev(nxt));
    int l, r;
    if (nxt != st1.end() && nxt != st1.begin() && nxt->first == x + 1 && pre->second == x - 1) {
        l = pre->first, r = nxt->second;
        erase(pre->first, pre->second), erase(nxt->first, nxt->second);
    } else if (nxt != st1.end() && nxt->first == x + 1) {
        l = x, r = nxt->second;
        erase(nxt->first, nxt->second);
    } else if (nxt != st1.begin() && pre->second == x - 1) {
        l = pre->first, r = x;
        erase(pre->first, pre->second);
    } else
        l = r = x;
    insert(l, r);
}
void fail(int i, int k) {
    if (i == 1 && k == 1)
        ans = 2;
    pq.emplace(i - k - 1, k);
}
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    for (cin >> t; t; --t) {
        cin >> n;
        for (int i = 1; i <= n; ++i)
            cin >> a[i];
        ans = 1, st1.clear(), st2.clear();
        while (!pq.empty())
            pq.pop();
        for (int i = 1; i <= n; ++i)
            fail(n + 1, i);
        for (int i = n; i; --i) {
            for (; !pq.empty() && pq.top().first >= i; pq.pop())
                insert(pq.top().second);
            while (!st2.empty() && st2.rbegin()->first > a[i]) {
                int l = st2.rbegin()->second, r = st1.lower_bound(pii(l, l))->second;
                erase(l, r);
                for (int j = l; r - j >= a[i]; ++j)
                    fail(i, j);
                insert(r - a[i] + 1, r);
            }
        }
        cout << ans << "\n";
    }
}

::::