[CF2234G] Stripe, Token and Two Players 的题解

· · 题解

定义 (i,k) 为 token 位于 i 且未加东西时的状态。

称 (i,k) 为一个必败态，当且仅当现在拿到这个状态的人必败。注意到若 (i,k) 是必败态，则 (j,k) 是必胜态，其中 j \isin [i + 1, i + k]。因为如果里面存在一个必败态，当前这个人可以保持 k 不变，走到 j，与 (i,k) 是必败态矛盾。k\ge n 的情况显然必胜，所以 (i,k) 的数量是 O(n\ln n) 级别的。所以我们可以判断 (1,1) 是否为必败态。

最优操作下，一个状态是必败态，当且仅当其所有后继都是必胜态。

于是可以倒序维护，对于每个 i，维护一个 S，k \isin S 表示 (i + 1,k),(i + 2,k),\cdots,(i + k,k) 均为必胜态。所以 (i,k) 为必败态，当且仅当任意 k + d 都属于这个 S，其中 d\isin[0,a_i]。而当 (i,k) 被确定为必败态后，根据定义 j\isin [i - k, i - 1] 的 S 都不能再包含 j，打标记即可。

然后因为必败态很少，可以直接暴力维护。官解用了 set，这里使用了线段树。寻找必败态相当于在线段树上查连续段。

时间复杂度 O(n\ln n \log n)。

::::success[代码]

#include <bits/stdc++.h>

#define MSOD
using namespace std;
using ll = long long;

const int N = 1e5 + 5;

int n;
int a[N];
basic_string<int> bs[N];
struct SGT {
    #define ls (p << 1)
    #define rs (p << 1 | 1)
    #define mid ((pl + pr) >> 1)
    int len[N << 2], mx[N << 2], pre[N << 2], suf[N << 2];
    void bld(int p, int pl, int pr) {
        mx[p] = pre[p] = suf[p] = 0, len[p] = pr - pl + 1;
        if(pl == pr) return;
        bld(ls, pl, mid);
        bld(rs, mid + 1, pr);
        return;
    }
    void up(int p) {
        pre[p] = (suf[ls] == len[ls] ? len[ls] + pre[rs] : pre[ls]);
        suf[p] = (pre[rs] == len[rs] ? len[rs] + suf[ls] : suf[rs]);
        mx[p] = max({mx[ls], mx[rs], suf[ls] + pre[rs]});
        return;
    }
    void upd(int p, int pl, int pr, int pos, int d) {
        if(pl == pr) return mx[p] = pre[p] = suf[p] = d, void();
        if(pos <= mid) upd(ls, pl, mid, pos, d);
        else upd(rs, mid + 1, pr, pos, d);
        up(p);
        return;
    }
    int qry(int p, int pl, int pr, int d) {
        if(mx[p] < d) return -1;
        if(pl == pr) return pl;
        if(mx[ls] >= d) return qry(ls, pl, mid, d);
        else if(suf[ls] + pre[rs] >= d) return mid - suf[ls] + 1;
        else return qry(rs, mid + 1, pr, d);
    }
    int fnd() {
        int res = qry(1, 0, n, mx[1]);
        if(res != -1) upd(1, 0, n, res, 0);
        return res;
    }
} T;

void TEST() {
    cin>>n;
    for(int i = 1 ; i <= n ; i ++) cin>>a[i], bs[i].clear();
    for(int i = 0 ; i < n ; i ++) bs[n - i] += i;
    bool ok = true;
    T.bld(1, 0, n);
    for(int i = n ; i >= 1 ; i --) {
        for(auto j : bs[i]) T.upd(1, 0, n, j, 1);
        while(T.mx[1] > a[i]) {
            int res = T.fnd();
            if(i == 1 && res == 1) ok = false;
            if(i - res - 1 >= 1) bs[i - res - 1] += res;
        }
    }
    cout<<(ok ? 1 : 2)<<endl;
    return;
}

signed main() {
    ios::sync_with_stdio(false), cout.tie(0), cin.tie(0);
    int TC = 1;
#ifdef MSOD
    cin>>TC;
#endif
    while(TC --) TEST();
    return 0;
}

::::