题解：P14359 [CSP-J 2025] 异或和 / xor（民间数据）

· · 题解

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

题目分析

题目要求从序列中选出尽可能多的不相交区间，每个区间的异或和都等于给定的 k。我们需要找出最多能选出多少个这样的区间。

解题思路

定义前缀异或和数组 {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 记录当前能选出的最多区间数，用 max\_dp 数组记录每个前缀异或值对应的最大 dp 值，遍历序列，对于每个位置，计算当前前缀异或和 s，检查是否存在 x = s \oplus k，如果存在则更新 dp，更新 max\_dp[s] 为当前 {dp} 值。

代码实现

#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;
}

正确性证明

关键概念

算法思路

遍历序列时，对于每个位置 i：

  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] 记录当前最优值。

数学归纳法证明

定义：设 f(i) 表示考虑前 i 个元素时能选出的最大区间数。

归纳基础：

归纳步骤： 假设对于所有 j < i，f(j) 已正确计算。考虑 f(i)：

因此，有：

f(i) = \max \left( f(i-1), \max_{j: pre[j] = pre[i] \oplus k} \{ f(j) + 1 \} \right)

由于遍历顺序从 i=1 到 n， {max\_dp} 数组始终记录当前位置之前的最优值，因此算法能正确计算 f(n)。