题解：P13687 【MX-X16-T5】「DLESS-3」XOR and Rockets

· · 题解

Link & Cnblogs.

妙妙题。

前缀异或很丑，考虑放在 a 的差分上刻画，操作 (x, y) 转换成 \Delta a_1 \gets \Delta a_1 \oplus y 和 \Delta a_{x + 1} \gets \Delta a_{x + 1} \oplus y。

这里有个小技巧：我们先将 a 翻转，此时修改变为后缀，再做差分，操作 (x, y) 等价于 \Delta a_{n - x + 1} \gets \Delta a_{n - x + 1} \oplus y。

翻转后问题变为求单调不增的 a，即其差分的前缀异或积单调不增，容易想到一种 dp：记 f_{i, j} 为考虑到 \Delta a_i，前缀异或积为 j 的方案，考虑当前这个位置是否进行修改。

若不修改，枚举 k \lt 2^{13}，若有 k\oplus a_i \le a_i，则可以从 f_{i - 1, k} 转移而来；若修改，则可以由所有 k \ge j 的 f_{i - 1, k} 转移而来。随便维护可以 \mathcal O(nV)。

但这个 dp 是错误的。修改的 y 没有限定范围，实际上修改后的值域不一定为 [0, 2^{13})！但发现当 a_1 不进行修改时，由于序列单调不增，所以这么做是对的。接下来钦定 a_1 进行了修改。

考虑整个东西的形态，对于一个进行操作的位置 i，记下一个进行操作的位置为 j，考虑前面所有修改的影响，若总的对 a_i 的贡献是 a_i \gets a_i \oplus s，那么 [i, j) 整一段的数都异或了 s，称整个段局部合法当且仅当所有 a_p\oplus s 单调不增，其中 i\le p\lt j。

最厉害的一步：假设我们已经构造出了一种方案使每个段都局部合法，实际上我们仅需 0 的代价就可以使全局合法！记从右往左第 i 段的第一个数上进行的操作的 y 为 y_i，那么仅需让 y_i \gets y_i\oplus 2^{100i} 即可，这不改变局部合法性，且在不同的两段之间，极大的位数差距使得低位的内容已经不重要了。

所以可以直接忽略这部分，仅需再用一个类似的 dp 求满足局部合法性的答案，记为 g_{i, j}，和 f 的部分去以下 \min 即为最终答案。仍是 \mathcal O(nV) 的。

// godmoo's code
#define ckmn(a, b) (a = min(a, b))
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const int N = 5005;
const int V = 1 << 13;
int n, a[N], b[N]; ll f[2][1 << 13], g[2][1 << 13], ans;
void solve(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i]; reverse(a + 1, a + n + 1);
    for(int i = 1; i <= n; i++) cin >> b[i]; reverse(b + 1, b + n + 1);
    for(int i = n; i; i--) a[i] ^= a[i - 1];

    mem(f, 0x3f), mem(g, 0x3f);

    fill(f[1], f[1] + V, b[1]), f[1][a[1]] = 0;
    for(int i = 2; i <= n; i++){
        mem(f[i & 1], 0x3f);
        for(ll j = V - 1, mn = 1e18; ~j; j--){
            if((a[i] ^ j) <= j) ckmn(f[i & 1][a[i] ^ j], f[~i & 1][j]);
            ckmn(f[i & 1][j], ckmn(mn, f[~i & 1][j]) + b[i]);
        }
    }
    ans = *min_element(f[n & 1], f[n & 1] + V);

    fill(g[1], g[1] + V, b[1]);
    for(int i = 2; i <= n; i++){
        mem(g[i & 1], 0x3f);
        ll mn = *min_element(g[~i & 1], g[~i & 1] + V);
        for(int j = 0; j < V; j++){
            g[i & 1][j] = mn + b[i];
            if((a[i] ^ j) <= j) ckmn(g[i & 1][a[i] ^ j], g[~i & 1][j]);
        }
    }
    ckmn(ans, *min_element(g[n & 1], g[n & 1] + V));

    cout << ans << '\n';
}
int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int Cas; for(cin >> Cas; Cas; Cas--) solve();
    cout << flush;
    return 0;
}