P14359 [CSP-J 2025] 异或和 / xor 题解

题目分析

解题思路

代码实现

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

const int MAX = 1 << 20; 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    vector<int> max_dp(MAX, -1);
    max_dp[0] = 0;  // 前缀异或和为 0 时，dp 值为 0
    
    int s = 0;  // 前缀异或和
    int dp = 0; // 当前能选出的最多区间数
    
    for (int i = 1; i <= n; i++) {
        s ^= a[i];
        int x = s ^ k;
        
        // 如果 x 存在且可以形成新区间
        if (x < MAX && max_dp[x] != -1) {
            dp = max(dp, max_dp[x] + 1);
        }
        
        // 更新当前前缀异或值对应的最大 dp 值
        if (max_dp[s] == -1 || dp > max_dp[s]) {
            max_dp[s] = dp;
        }
    }
    
    cout << dp << endl;
    
    return 0;
}

正确性证明

关键概念

• 定义前缀异或和数组 ${pre}$，其中 ${pre}[i] = a_1 \oplus a_2 \oplus \dots \oplus a_i$，且 ${pre}[0] = 0$。
• 区间 $[l, r]$ 的异或和为 ${pre}[r] \oplus {pre}[l-1]$。因此，要求 ${pre}[r] \oplus {pre}[l-1] = k$，即 ${pre}[r] = {pre}[l-1] \oplus k$。

算法思路

• ${dp}$：表示当前处理到位置 $i$ 时能选出的最多区间数。
• ${max\_dp}$ 数组：${max\_dp}[x]$ 记录当遇到前缀异或和为 $x$ 时，能选出的最多区间数。

1. 计算当前前缀异或和 $s = {pre}[i]$。
2. 计算 $x = s \oplus k$。如果 ${max\_dp}[x]$ 存在（不为 $-1$），则说明存在某个位置 $j$（$j < i$）满足 ${pre}[j] = x$，从而区间 $[j+1, i]$ 的异或和为 $k$。此时，可以形成一个新的区间，更新 ${dp} = \max( {dp}, {max\_dp}[x] + 1)$。
3. 更新 ${max\_dp}[s] = \max( {max\_dp}[s], {dp})$，确保 ${max\_dp}[s]$ 记录当前最优值。

数学归纳法证明

• 当 $i = 0$ 时，${pre}[0] = 0$，${max\_dp}[0] = 0$，表示没有选择任何区间，$f(0) = 0$。

• $f(i)$ 可能等于 $f(i-1)$，即不选择以 $i$ 结尾的区间。
• 或者，如果存在 $j$ 满足 ${pre}[j] = {pre}[i] \oplus k$，则区间 $[j+1, i]$ 的异或和为 $k$，此时 $f(i) = f(j) + 1$。