CF2234G Stripe, Token and Two Players 题解

▶

INFO 题意简述

有 个格子，每个格子有一个参数 。有一枚棋子初始在第 个格子，力量值为 。有两名玩家轮流操作这个棋子，假设当前棋子在第 个格子，当前玩家可以选择增加最多 的力量值，然后将棋子移动不超过当前力量值的距离（不能原地不动）。先到 的玩家获胜。

首先我们考虑如何计算答案。不难想到一个十分暴力的 DP。那就是 表示当前玩家在格子 ，力量值为 的方案数。每次枚举将力量值增加多少，走到哪个格子进行转移，如果可以走到一个必败状态则当前状态必胜，如果走到的都是必胜状态则当前状态必败。

这个复杂度是 。你注意到 如果大于 就没什么意义了，可以直接增加满然后移动到最后直接赢。因此你考虑把 和 取个 ，这样就是 。

然后你发现要直接优化到可以通过的复杂度比较困难，因为你总共的状态数就是 的。我们考虑能不能缩减一下状态数。

考虑必败情况的转移。必败状态要求所有可达点都是必胜点。

也就是，所有满足 的 必然是必胜点。这些点构成了一个梯形，如下图所示。

可以看到，可以到达的点并不是很少，“所有可达点都是必胜状态”看上去是一个很难满足的条件。因此必败状态可能非常少。

我们来具体分析一下必败点的量级。考虑 到 这些点。这些点必然是必胜状态。

换句话说，假设第 行有一个必败状态，那么右侧的 个点一定是必胜状态（换言之，这些点的状态也已经确定，并且不能是必败状态）。

相当于我们可以花费 个点来换取一个必败状态，第 行一共 个点，最多能换取 个必败状态。

考虑对所有行求和，最多有 个必败状态。根据调和级数的结论，这个东西是 量级。也就是说，我们只有 个必败状态，我们只需要想办法维护这些状态即可。

对于每个位置维护最靠近的一个必败状态。也就是最小的 满足 为必败状态，记作 。那么 是必败状态当且仅当满足 。这部分可以维护 ，这样就可以转化成一个区间最小值的问题了。不过其实没啥用，没有利用上我们刚刚的观察进一步优化的空间。我们需要保证每一次更新都恰好对应一个必败状态才能保证复杂度是 乘上单次更新的复杂度的。

我们发现所有状态对第 行的要求都是 。而对于这个条件只会在 这个位置改变一次（从不满足变成满足）。我们只需要维护当前有哪些行满足了这个条件，如果满足条件则 ，否则 。我们需要找到往后有至少连续 个 的位置。

我们可以使用 std::set 维护极长的连续的 的段，每次取出来最长的一段，检查其长度是否大于 。如果小于 ，可以直接停止更新。否则就枚举这一段，从左侧开始把满足“后续有 个 的位置”设置成必败状态，对应更新 和 ，然后把剩下的段扔回 set 中即可。单次转移是 的。

最后检查 是否是 。如果是 说明先手必败，否则先手必胜。复杂度 。

▶

INFO 参考代码

#include <cassert>
#include <iostream>
#include <queue>
#include <set>
#include <vector>

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

namespace solve {
struct segments {
    struct range {
        uint l, r;
        constexpr uint size() const { return r - l; }
    };

    struct compare_location {
        bool operator()(const range &a, const range &b) const {
            return a.l < b.l;
        }
    };

    struct compare_size {
        bool operator()(const range &a, const range &b) const {
            return a.size() == b.size() ? a.l < b.l : a.size() < b.size();
        }
    };

    std::set<range, compare_location> seg;
    std::set<range, compare_size> pq;

    void erase(range rng) {
        seg.erase(rng);
        pq.erase(rng);
    }

    std::pair<std::set<range, compare_location>::iterator, bool>
    insert(const range &rng) {
        pq.insert(rng);
        return seg.insert(rng);
    }

    range get_max() const { return *pq.rbegin(); }

    void pop_max() {
        auto rng = get_max();
        erase(rng);
    }

    void set(uint pos) {
        range cur{pos, pos + 1};
        auto res = insert(cur);
        assert(res.second);

        auto it = res.first;

        if (std::next(it) != seg.end()) {
            auto nxt = std::next(it);

            if (nxt->l == pos + 1) {
                cur.r = nxt->r;

                erase(*it);
                erase(*nxt);
                res = insert(cur);
                assert(res.second);
                it = res.first;
            }
        }

        if (it != seg.begin()) {
            auto pre = std::prev(it);

            if (pre->r == cur.l) {
                cur.l = pre->l;

                erase(*it);
                erase(*pre);
                res = insert(cur);
                assert(res.second);
                it = res.first;
            }
        }
        return;
    }

    bool empty() const { return seg.empty(); }
};

void solve() {
    uint n;
    std::cin >> n;

    std::vector<uint> a(n);

    for (uint i = 0; i < n; i++) {
        std::cin >> a[i];

        a[i] = std::min(n - i - 1, a[i]); // 更大的就没有意义了。
    }

    /**
     * 请注意力量初始是 1。
     */

    std::vector<std::vector<uint>> set_pos(n);

    // init 0. strength 1.

    /**
     * 请注意这里是移动后到 n + 1 的赢。
     *
     * 也就是 n + 1, * 是必败局面，这意味着对面移动到了 n + 1。
     */

    std::vector<uint> last_fail(n + 1, n);

    for (size_t i = 1; i < n; i++) {
        if (i + 1 <= n) {
            set_pos[n - i - 1].push_back(i);
        }
    }

    segments seg;

    for (uint i = n - 1; i != uint(-1); i--) {
        for (auto &&j : set_pos[i]) {
            seg.set(j);
        }

        while (!seg.empty() && seg.get_max().size() >= a[i] + 1) {
            auto cur = seg.get_max();
            seg.pop_max();

            while (cur.size() >= a[i] + 1) {
                last_fail[cur.l] = i;

                if (cur.l + 1 <= i) {
                    set_pos[i - 1 - cur.l].push_back(cur.l);
                }

                cur.l++;
            }

            if (cur.size() != 0) {
                seg.insert(cur);
            }
        }
    }

    std::cout << (last_fail[1] == 0 ? "2\n" : "1\n");
}

} // namespace solve

int main() {
    uint t;
    std::cin >> t;
    while (t--) {
        solve::solve();
    }
    std::cout << std::flush;
    return 0;
}

/**
 * 呃啊。
 *
 * 首先根据两个 hint。
 *
 * 首先 a_i > n 是没有意义的。这个就直接赢了。
 *
 * 然后就是神秘题解的分析。
 *
 * 你注意到转移是右上角的一个梯形。
 * 如果一个点输了，那么说明右侧梯形全部都是赢的。
 *
 * 考察 (i, k)。请注意 (i, k) 右侧的 k 个点 (i + 1, k) 到 (i + k, k)
 * 这些也在梯形里，这个必须是赢的。
 *
 * 因而每行实际上输的并不多。
 *
 * 好的。
 *
 * 因此我们需要维护输的位置。
 *
 * 请注意什么时候一个点是输的。是右上角一个梯形全部是赢的情况。
 *
 * 那么显然可以考虑维护每一行上一个输的位置。
 *
 * 你会发现这是一个梯形，因此你可能需要先减掉 i。这样就会整齐一点。
 *
 * 然而你仍然不能暴力更新，你需要找到那 n log n 个“可能是输的的点”。
 *
 * 那么，可能是输的当且仅当这一行上一个输的位置距离超过 i 了。你发现我们 -i 恰好可以维护。
 *
 * 不过还是有一个问题，那就是我们必须要每次都恰好输掉一次。
 *
 * 哦哦然后你必须要从小到大去转移，转移实际上是一个三角形。
 *
 * 你需要连续 a_i 个都不满足才可以。
 *
 * 那么，维护不满足的位置，你实际上需要一个至少为 a_i 的连续段。
 *
 * 按照区间从大到小排序。然后合并一下，之类的。
 *
 * 需要删除重新插入。
 *
 * 然后插入最多 O(1) 次合并，可以用 set 轻松维护。
 */

最后还需要提一下实现的一个细节。参考代码的这个部分

void erase(range rng) {
    seg.erase(rng);
    pq.erase(rng);
}

如果参数写成 const range& rng 的话，在 set 函数中调用的 erase(*it) 会因为 seg 中的 *it 先被 erase 而使得 rng 变成悬空引用导致 RE。这里复制的代价并不是很高昂，因此直接按值传递即可。