The 2020 ICPC Asia Macau Regional Contest I Nim Cheater

题目描述

http://codeforces.com/gym/103119/problem/I

简要题意：现在有 $n$ 个操作，每个操作要么在最右边添加一堆石子，个数为 $a$，价值为 $b$，要么删除最右边的一堆，在每次操作后，求价值最小的移除方案使得先手必败

$n\le 4\times 10^4,a<2^{14}$，空间限制 $8M$

Solution

首先我们不考虑空间限制，容易得到操作构成一个树形结构，每次相当于查询从点 $u$ 的树链上选价值和最小的若干个点使得它们的以后和等于 $u$ 的树链的异或和

容易得到一个 $dp$，令 $f[u][S]$ 表示从 $u$ 到根，异或和为 $S$ 的最小价值，我们考虑压缩一下第一维

实际上第一位我们并不用存 $1$ 到 $n$，我们只需要保证从 $u$ 点到其子树内第一维不会重复即可

我们考虑轻重链剖分，然后令第一维表示轻边的个数，那么第一维就不会超过 $O(\log n)$，然后我们先 $dfs$ 轻儿子，最后 $dfs$ 重儿子即可

时间复杂度 $O(nS)$，空间复杂度 $O(S\log n)$

#include <iostream>
#include <vector>
#define maxn 20010
#define maxm 16384
#define INF 2000000001
using namespace std;

int n, m, a[maxn], b[maxn];

vector<int> G[maxn]; 
int dep[maxn], son[maxn], sz[maxn], fa[maxn]; 
void dfs(int u) {
    int Max = 0; sz[u] = 1;
    for (auto v : G[u]) { 
        dep[v] = dep[u] + 1;
        dfs(v); sz[u] += sz[v];
        if (sz[v] > Max) Max = sz[v], son[u] = v;
    }
}

int top[maxn];
void dfs(int u, int topf) {
    top[u] = topf; 
    if (son[u]) dfs(son[u], topf);
    for (auto v : G[u]) {
        if (v == son[u]) continue;
        dfs(v, v);
    }
}

vector<int> A[maxn];
int f[20][maxm], ans[maxn * 2], g[maxm];
void Dfs(int u, int k, int s) {
    for (auto t : A[u]) ans[t] = f[k][s];
    for (auto v : G[u]) {
        if (v == son[u]) continue;
        for (int S = 0; S < 16384; ++S) f[k + 1][S] = f[k][S];
        for (int S = 0; S < 16384; ++S)
            if (f[k][S] != INF) f[k + 1][S ^ a[v]] = min(f[k + 1][S ^ a[v]], f[k][S] + b[v]);
        Dfs(v, k + 1, s ^ a[v]); 
    } if (!son[u]) return ; int v = son[u];
    for (int S = 0; S < 16384; ++S) g[S] = INF;
    for (int S = 0; S < 16384; ++S)
        if (f[k][S] != INF) g[S ^ a[v]] = min(g[S ^ a[v]], f[k][S] + b[v]);
    for (int S = 0; S < 16384; ++S) f[k][S] = min(f[k][S], g[S]);
    Dfs(v, k, s ^ a[v]); 
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> m; 
    for (int i = 1, u = 0; i <= m; ++i) {
        char s[10]; int x, y; cin >> s;
        if (s[0] == 'A') {
            fa[++n] = u; G[u].push_back(n);
            u = n; A[u].push_back(i); 
            cin >> a[n] >> b[n];
        }
        else u = fa[u], A[u].push_back(i); 
    } dfs(0); dfs(0, 0);
    for (int S = 0; S < 16384; ++S) f[0][S] = INF; f[0][0] = 0;
    Dfs(0, 0, 0);
    for (int i = 1; i <= m; ++i) cout << ans[i] << "\n";
    return 0; 
}