2025 异或和 · 方案二动态规划加值域数组

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 4/5 · 共 1299 字

best 数组记下每个前缀异或值的最优 dp

2025
动态规划

正文

// CSP-J 2025 复赛 T3 · 异或和（方案二）
// 原题：https://oj.yecheng.tv/p/CSP2025JC
//
// 方案二 · 动态规划 + 值域数组（写法更严谨，也更快）
// 同样用前缀异或 s[i]。定义 dp[i] = 只在前 i 个数里选，最多能选几个区间。
// 转移只有两种：
//   不用第 i 个：dp[i] = dp[i-1]；
//   用第 i 个收尾：选一个区间 [j+1, i]，要求 s[j] == s[i] ^ k，此时 dp[i] = dp[j] + 1。
// 关键是第二种怎么快速求：用一个 best[v] 记下「在所有 s[j] == v 的位置里，dp[j] 最大是多少」。
// 因为 dp 是单调不减的，取最大的 dp[j] 一定最优，于是每个位置只要 O(1)。
// 注意顺序：先用 best 算 dp[i]，再把 dp[i] 并进 best[s[i]]，这样保证 j < i。
// 值域：k 和所有 a[i] 都小于 2^20，前缀异或也小于 2^20，直接开数组不用哈希。
// 复杂度 O(n + 2^20)。

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

const int MAXV = 1 << 20;
const int NEG = -1000000000;

int best[MAXV];
int dp[500005];

int main() {
    freopen("xor.in", "r", stdin);
    freopen("xor.out", "w", stdout);

    int n;
    int k;
    cin >> n >> k;

    for (int v = 0; v < MAXV; v++) best[v] = NEG;
    best[0] = 0;                     // j = 0：一个区间都没选，dp 为 0

    int s = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        s ^= x;                      // s = s[i]
        dp[i] = dp[i - 1];           // 不选以 i 结尾的区间
        int need = s ^ k;            // 需要一个 s[j] == need
        if (best[need] != NEG) dp[i] = max(dp[i], best[need] + 1);
        best[s] = max(best[s], dp[i]);   // 位置 i 也可以当以后的起点
    }
    cout << dp[n] << "\n";
    return 0;
}

2025 异或和 · 方案二 动态规划加值域数组

正文

CSP-J 标程 · 复赛真题的其它内容

2025 异或和 · 方案二动态规划加值域数组