[CSP-J 2025] 异或和: 问题分析与动态规划解法详解

小 R 有一个长度为 n 的非负整数序列 a1​,a2​,…,an​。定义一个区间 [l,r] (1≤l≤r≤n) 的权值为 al​,al+1​,…,ar​ 的二进制按位异或和，即 al​⊕al+1​⊕⋯⊕ar​，其中 ⊕ 表示二进制按位异或。

小 X 给了小 R 一个非负整数 k。小 X 希望小 R 选择序列中尽可能多的不相交的区间，使得每个区间的权值均为 k。两个区间 [l1​,r1​],[l2​,r2​] 相交当且仅当两个区间同时包含至少一个相同的下标，即存在 1≤i≤n 使得 l1​≤i≤r1​ 且 l2​≤i≤r2​。

例如，对于序列 [2,1,0,3]，若 k=2，则小 R 可以选择区间 [1,1] 和区间 [2,4]，权值分别为 2 和 1⊕0⊕3=2；若 k=3，则小 R 可以选择区间 [1,2] 和区间 [4,4]，权值分别为 1⊕2=3 和 3。

你需要帮助小 R 求出他能选出的区间数量的最大值。

输入格式

输入的第一行包含两个非负整数 n,k，分别表示小 R 的序列长度和小 X 给小 R 的非负整数。

输入的第二行包含 n 个非负整数 a1​,a2​,…,an​，表示小 R 的序列。

输出格式

输出一行一个非负整数，表示小 R 能选出的区间数量的最大值。

输入输出样例

输入 #1

4 2
2 1 0 3

输出 #1

2

输入 #2

4 3
2 1 0 3

输出 #2

2

输入 #3

4 0
2 1 0 3

输出 #3

1

AC代码

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

int main() {
int n, k;
cin >> n >> k; // 读取序列长度n和目标异或值k

// 创建数组，使用1-based索引方便计算
int a[n + 1];
for (int i = 1; i <= n; i++) {
cin >> a[i]; // 读取序列元素
}

// mp[异或值] = 该异或值对应的最大区间数
map<int, int> mp;

// 关键初始化：空数组的前缀异或值为0，对应区间数为0
mp[0] = 0;

int xorh = 0; // 当前前缀异或值
int c = 0; // 当前最大区间数

for (int i = 1; i <= n; i++) {
// 更新前缀异或值：xorh = pref[i] = a[1]^a[2]^…^a[i]
xorh = xorh ^ a[i];

// 核心逻辑：寻找是否存在pref[l-1] = pref[i] ^ k
// 如果存在，说明区间[l, i]的异或和为k
if (mp.find(xorh ^ k) != mp.end()) {
// 状态转移：可以选择区间[l, i]
// 区间数 = mp[pref[i]^k] + 1
c = max(c, mp[xorh ^ k] + 1);
}

// 更新当前前缀异或值对应的最大区间数
// 原则：对于相同的前缀异或值，保留最大区间数
if (mp.find(xorh) == mp.end()) {
mp[xorh] = c; // 首次出现，直接记录
} else {
mp[xorh] = max(mp[xorh], c); // 已存在，取最大值
}
}

cout << c; // 输出最大区间数
return 0;
}

算法核心思路

1. 前缀异或技巧

这是解决异或区间问题的关键技巧。定义前缀异或数组：

text

pref[i] = a₁ ⊕ a₂ ⊕ … ⊕ aᵢ

根据异或运算的性质，区间 [l, r] 的异或和可以表示为：

text

aₗ ⊕ aₗ₊₁ ⊕ … ⊕ aᵣ = pref[r] ⊕ pref[l-1]

2. 问题转化

题目要求区间异或和等于 k，即：

text

pref[r] ⊕ pref[l-1] = k

根据异或运算的逆运算性质，上式等价于：

text

pref[l-1] = pref[r] ⊕ k

这意味着：对于每个位置 r，我们需要在之前的位置中找到 l-1，使得 pref[l-1] = pref[r] ⊕ k。

3. 动态规划定义

定义状态 dp[i] 表示考虑前 i 个元素时，能选出的最多不相交区间数。 定义状态 mp[x] 表示前缀异或值为 x 时对应的最大区间数。

算法复杂度分析

• 时间复杂度：O(n log n)，其中 n 为序列长度。使用 map 进行查找和更新，每次操作时间复杂度为 O(log n)。

• 空间复杂度：O(n)，用于存储数组和哈希表。

关键点解析

1. 为什么需要 mp[0] = 0 初始化？

这是算法中最容易遗漏的关键点。考虑区间从第一个元素开始的情况：

• 当区间 [1, r] 的异或和为 k 时，根据公式 pref[r] ⊕ pref[0] = k

• 因此需要 pref[0] = pref[r] ⊕ k

• 而 pref[0] 表示空数组的异或和，值为 0

所以 mp[0] = 0 确保了可以从数组开头选择区间。

2. 动态规划状态转移的理解

在遍历到位置 i 时，有两种选择：

取这两种情况的最大值作为新的 c。

3. 为什么使用 map 存储？

map 提供了高效的查找和更新操作。在本题中，我们需要快速判断某个前缀异或值是否出现过，以及获取该值对应的最大区间数。虽然 unordered_map 平均时间复杂度更低，但 map 的稳定性更好，适用于竞赛环境。

算法优化建议

总结

本题考察了前缀异或技巧与动态规划的结合应用。通过将区间异或和问题转化为前缀异或值的匹配问题，我们能够高效地求解最大不相交区间数。算法的时间复杂度为 O(n log n)，空间复杂度为 O(n)，完全满足题目要求。

关键点在于：

这种解题思路不仅适用于本题，也可以推广到其他类似的区间异或问题中。