「梦熊 X16 · 异或赛」XOR and Rockets

· · 题解

前言

:::epigraph[] 只有我赛时写的 Trie 树优化转移，然后卡了一年的常吗？ :::

状态定义的方式不同，转移优化的难度和时间复杂度是不同的。这个还是第一次见，感觉挺深刻的。

:::info[题目描述] 给定两个长度为 n 的非负整数序列 a,b。接下来进行若干次操作：

输出通过若干次操作使得 a 变为单调不降的最小代价。 :::

思路

不难想到用 DP 求解。由于每次是将前缀异或，所以倒着做会比较方便（应该正着做也行，没细想）。

需要观察到答案分为两种情况：

情况 1（a_n 不操作）

令 f_{i,j} 表示 i\sim n 位置中，所有位置的操作的异或和为 j。这时候，如果 i 位置操作为异或 k，则需满足 a_i\oplus k\oplus j\le a_{i+1}\oplus j。所有合法的 k 是 Trie 树上 \log V 个子树。这样，复杂度即可做到 O(nV\log V)。

不过，这样太不好了。我们将限制放在转移中，但实际上可以将限制放在状态里。即，令 f_{i,j} 表示 i\sim n 位置中，a_i 最终的值为 j。如果操作，则 a_{i} 可以变成任何值。这样，转移只需要做后缀 \max 即可（也就是转化成了一段区间）。

时间复杂度：O(nV)。

情况 2（a_n 操作）

根据上述分析，只要操作，异或值可以变成任何值。于是，令 f_{i,j} 表示 i\sim n 位置，所有操作的异或和为 j。转移是容易做到 O(1) 的。

时间复杂度：O(nV)。

代码

:::success[赛时代码 O(nV\log V)]

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

int n;
int a[1 << 13], b[1 << 13];
i64 dp[2][1 << 13], fg[13][1 << 13];

inline void chmin(i64 &a, i64 b) { a = min(a, b); }
void solve() {
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];
    for (int i = 1; i <= n; i ++)
        cin >> b[i];

    memset(dp, 0x3f, sizeof dp);
    dp[n & 1][0] = 0;
    for (int i = n - 1; i >= 1; i --) {
        memset(dp[i & 1], 0x3f, sizeof dp[i & 1]);
        memset(fg, 0x3f, sizeof fg);
        for (int j = 0; j < 1 << 13; j ++) {
            if (dp[~i & 1][j] >= 1E18) continue;
            int x = a[i] ^ j, y = a[i + 1] ^ j;
            int S = j;
            for (int k = 12; k >= 0; k --)
                if (y >> k & 1) {
                    chmin(fg[k][(S ^ ((x >> k & 1) << k)) >> k], dp[~i & 1][j]);
                    S ^= (~x >> k & 1) << k;
                } else if (x >> k & 1) S ^= 1 << k;
            fg[0][S] = min(fg[0][S], dp[~i & 1][j]);
            if (x <= y)
                dp[i & 1][j] = min(dp[i & 1][j], dp[~i & 1][j]);
        }
        for (int k = 12; k >= 0; k --)
            for (int x = 0; x < 1 << 13 - k; x ++)
                if (fg[k][x] < 1E18)
                    for (int y = 0; y < 1 << k; y ++)
                        dp[i & 1][x << k | y] = min(dp[i & 1][x << k | y], fg[k][x] + b[i]);
    }
    i64 res = 1ll << 60;
    for (int i = 0; i < 1 << 13; i ++)
        res = min(res, dp[1][i]);

    for (int i = 0; i < 1 << 13; i ++)
        dp[n & 1][i] = b[n];
    for (int i = n - 1; i >= 1; i --) {
        i64 mn = 1ll << 60;
        for (int j = 0; j < 1 << 13; j ++)
            mn = min(mn, dp[~i & 1][j]);
        for (int j = 0; j < 1 << 13; j ++) {
            dp[i & 1][j] = mn + b[i];
            if ((a[i] ^ j) <= (a[i + 1] ^ j))
                dp[i & 1][j] = min(dp[i & 1][j], dp[~i & 1][j]);
        }
    }
    for (int i = 0; i < 1 << 13; i ++)
        res = min(res, dp[1][i]);

    cout << res << '\n';
}

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

    int T;
    cin >> T;

    while (T -- ) solve();

    return 0;
}

:::

:::success[O(nV) 代码]{open}

void solve() {
    cin >> n;
    int mx = 0;
    for (int i = 1; i <= n; i ++)
        cin >> a[i], mx = max(mx, a[i]);
    for (int i = 1; i <= n; i ++)
        cin >> b[i];
    mx = (1 << __lg(mx) + 1);

    memset(dp, 0x3f, sizeof dp);
    dp[n & 1][a[n]] = 0;
    for (int i = n - 1; i >= 1; i --) {
        memset(dp[i & 1], 0x3f, sizeof dp[i & 1]);
        i64 mn = 1ll << 60;
        for (int j = mx - 1; j >= 0; j --) {
            int k = a[i] ^ j ^ a[i + 1];
            if (k <= j) dp[i & 1][k] = min(dp[i & 1][k], dp[~i & 1][j]);
            mn = min(mn, dp[~i & 1][j]);
            dp[i & 1][j] = min(dp[i & 1][j], mn + b[i]);
        }
    }
    i64 res = 1ll << 60;
    for (int i = 0; i < mx; i ++)
        res = min(res, dp[1][i]);

    for (int i = 0; i < mx; i ++)
        dp[n & 1][i] = b[n];
    for (int i = n - 1; i >= 1; i --) {
        i64 mn = 1ll << 60;
        for (int j = 0; j < mx; j ++)
            mn = min(mn, dp[~i & 1][j]);
        for (int j = 0; j < mx; j ++) {
            dp[i & 1][j] = mn + b[i];
            if ((a[i] ^ j) <= (a[i + 1] ^ j))
                dp[i & 1][j] = min(dp[i & 1][j], dp[~i & 1][j]);
        }
    }
    for (int i = 0; i < mx; i ++)
        res = min(res, dp[1][i]);

    cout << res << '\n';
}

:::