【CSP】CSP-J 2025真题 | 异或和 luogu-P14359 （相当于GESP六级水平）
CSP-J 2025真题- 异或和，动态规划考点，适合GESP六级考生练习，难度⭐⭐⭐☆☆，洛谷难度等级普及/提高−。
P14359 [CSP-J 2025] 异或和
题目要求
题目描述
小 R 有一个长度为 $n$ 的非负整数序列 $a_1, a_2, \dots, a_n$。定义一个区间 $[l, r]$ ($1 \leq l \leq r \leq n$) 的权值为 $a_l, a_{l+1}, \dots, a_r$ 的二进制按位异或和，即 $a_l \oplus a_{l+1} \oplus \dots \oplus a_r$，其中 $\oplus$ 表示二进制按位异或。
小 X 给了小 R 一个非负整数 $k$。小 X 希望小 R 选择序列中尽可能多的不相交的区间，使得每个区间的权值均为 $k$。两个区间 $[l_1, r_1], [l_2, r_2]$ 相交当且仅当两个区间同时包含至少一个相同的下标，即存在 $1 \leq i \leq n$ 使得 $l_1 \leq i \leq r_1$ 且 $l_2 \leq i \leq r_2$。
例如，对于序列 $[2, 1, 0, 3]$，若 $k = 2$，则小 R 可以选择区间 $[1, 1]$ 和区间 $[2, 4]$，权值分别为 $2$ 和 $1 \oplus 0 \oplus 3 = 2$；若 $k = 3$，则小 R 可以选择区间 $[1, 2]$ 和区间 $[4, 4]$，权值分别为 $1 \oplus 2 = 3$ 和 $3$。
你需要帮助小 R 求出他能选出的区间数量的最大值。
输入格式
输入的第一行包含两个非负整数 $n, k$，分别表示小 R 的序列长度和小 X 给小 R 的非负整数。
输入的第二行包含 $n$ 个非负整数 $a_1, a_2, \dots, a_n$，表示小 R 的序列。
输出格式
输出一行一个非负整数，表示小 R 能选出的区间数量的最大值。
输入输出样例 #1
输入 #1
1
2
3
4 2
2 1 0 3
输出 #1
1
2
输入输出样例 #2
输入 #2
1
2
4 3
2 1 0 3
输出 #2
1
2
输入输出样例 #3
输入 #3
1
2
4 0
2 1 0 3
输出 #3
1
1
说明/提示
【样例 1 解释】
小 R 可以选择区间 $[1, 1]$ 和区间 $[2, 4]$，异或和分别为 $2$ 和 $1 \oplus 0 \oplus 3 = 2$。可以证明，小 R 能选出的区间数量的最大值为 $2$。
【样例 2 解释】
小 R 可以选择区间 $[1, 2]$ 和区间 $[4, 4]$，异或和分别为 $1 \oplus 2 = 3$ 和 $3$。可以证明，小 R 能选出的区间数量的最大值为 $2$。
【样例 3 解释】
小 R 可以选择区间 $[3, 3]$，异或和为 $0$。可以证明，小 R 能选出的区间数量的最大值为 $1$。注意：小 R 不能同时选择区间 $[3, 3]$ 和区间 $[1, 4]$，因为这两个区间同时包含下标 $3$。
【样例 4】
见选手目录下的 $xor/xor4.in$ 与 $xor/xor4.ans$。
该样例满足测试点 $4, 5$ 的约束条件。
【样例 5】
见选手目录下的 $xor/xor5.in$ 与 $xor/xor5.ans$。
该样例满足测试点 $9, 10$ 的约束条件。
【样例 6】
见选手目录下的 $xor/xor6.in$ 与 $xor/xor6.ans$。
该样例满足测试点 $14, 15$ 的约束条件。
【数据范围】
对于所有测试数据，保证：
- $1 \leq n \leq 5 \times 10^5$, $0 \leq k < 2^{20}$;
- 对于所有 $1 \leq i \leq n$，均有 $0 \leq a_i < 2^{20}$。
| 测试点编号 | $n \leq$ | $k$ | 特殊性质 |
|---|---|---|---|
| $1$ | $2$ | $=0$ | A |
| $2$ | $10$ | $\leq 1$ | B |
| $3$ | $10^2$ | $=0$ | A |
| $4, 5$ | $10^2$ | $\leq 1$ | B |
| $6 \sim 8$ | $10^2$ | $\leq 255$ | C |
| $9, 10$ | $10^3$ | $\leq 255$ | C |
| $11, 12$ | $10^3$ | $< 2^{20}$ | 无 |
| $13$ | $2 \times 10^5$ | $\leq 1$ | B |
| $14, 15$ | $2 \times 10^5$ | $\leq 255$ | C |
| $16$ | $2 \times 10^5$ | $< 2^{20}$ | 无 |
| $17$ | $5 \times 10^5$ | $\leq 255$ | C |
| $18 \sim 20$ | $5 \times 10^5$ | $< 2^{20}$ | 无 |
特殊性质 A: 对于所有 $1 \leq i \leq n$，均有 $a_i = 1$。
特殊性质 B: 对于所有 $1 \leq i \leq n$，均有 $0 \leq a_i \leq 1$。
特殊性质 C: 对于所有 $1 \leq i \leq n$，均有 $0 \leq a_i \leq 255$。
题目分析
本题考查 异或性质、前缀和思想 以及 动态规划 (DP)。
1. 核心数学性质：前缀异或和
题目关心的区间 $[l, r]$ 的异或和。对于区间求和问题，最常用的技巧是 前缀和。同样地，对于区间异或，我们可以使用 前缀异或和。
定义 $pre[i]$ 为序列前 $i$ 个元素的异或和：
\[pre[i] = a_1 \oplus a_2 \oplus \dots \oplus a_i\]特别地，$pre[0] = 0$。
根据异或的性质，特别是 归零律（$x \oplus x = 0$）和 结合律，我们可以推导出区间异或和的公式： \(XOR(l, r) = pre[r] \oplus pre[l-1]\)
推导过程如下：
- 展开前缀异或和定义：
- $pre[r]$ 表示从第 $1$ 个到第 $r$ 个元素的异或和： \(pre[r] = a_1 \oplus a_2 \oplus \dots \oplus a_{l-1} \oplus \mathbf{a_l \oplus \dots \oplus a_r}\)
- $pre[l-1]$ 表示从第 $1$ 个到第 $l-1$ 个元素的异或和： \(pre[l-1] = a_1 \oplus a_2 \oplus \dots \oplus a_{l-1}\)
进行异或运算：我们将 $pre[r]$ 和 $pre[l-1]$ 进行异或： \(pre[r] \oplus pre[l-1] = (\underbrace{a_1 \oplus \dots \oplus a_{l-1}}_{\text{公共前缀}} \oplus \underbrace{a_l \oplus \dots \oplus a_r}_{\text{目标区间}}) \oplus (\underbrace{a_1 \oplus \dots \oplus a_{l-1}}_{\text{公共前缀}})\)
利用结合律和交换律：将相同的项放在一起（即 $a_1$ 对 $a_1$，…，$a_{l-1}$ 对 $a_{l-1}$）。由于异或运算满足交换律和结合律，我们可以随意调整运算顺序： \(= (a_1 \oplus a_1) \oplus (a_2 \oplus a_2) \oplus \dots \oplus (a_{l-1} \oplus a_{l-1}) \oplus (a_l \oplus \dots \oplus a_r)\)
- 利用归零律消去：因为任何数异或自己都等于 0（$x \oplus x = 0$），前面的公共部分全部抵消变为 0： \(= 0 \oplus 0 \oplus \dots \oplus 0 \oplus (a_l \oplus \dots \oplus a_r)\) \(= a_l \oplus \dots \oplus a_r\)
这正是区间 $[l, r]$ 的异或和。这个性质非常重要，它让我们能够在 $O(1)$ 的时间内通过两个前缀值的异或，快速求出任意子区间的异或和，类似于前缀和求子区间和（$Sum(l, r) = pre[r] - pre[l-1]$）。
题目要求找到最多的不相交区间，使得每个区间的异或和都为 $k$。 也就是说，如果我们要选一个以 $r$ 结尾的区间 $[l, r]$，必须满足： \(pre[r] \oplus pre[l-1] = k\) 根据异或的交换律，这等价于： \(pre[l-1] = pre[r] \oplus k\)
这意味着，当我们遍历到位置 $r$ 时，我们只需要在它前面找到一个位置 $l-1$（即 $j$），满足 $pre[j] = pre[r] \oplus k$，那么区间 $[j+1, r]$ 就是一个符合条件的区间。
2. 动态规划 (DP) 设计
这是一个典型的线性 DP 问题。设 $dp[i]$ 表示在前 $i$ 个数中，最多能选出多少个符合条件的不相交区间。
对于当前位置 $i$，我们有两种选择：
不选以 $i$ 结尾的区间：此时我们只需继承前面的最优结果，即 $dp[i] = dp[i-1]$。
选一个以 $i$ 结尾的区间 $[j+1, i]$： 这就要求区间异或和为 $k$，即 $pre[j] = pre[i] \oplus k$（其中 $0 \le j < i$）。 为了让总区间数最大，我们应该选择一个满足条件的 $j$，使得 $dp[j]$ 尽可能大。 此时状态转移方程为： \(dp[i] = \max(dp[i], dp[j] + 1)\)
综合起来，状态转移方程为： \(dp[i] = \max(dp[i-1], \max_{j < i, pre[j] = pre[i] \oplus k} \{ dp[j] + 1 \})\)
为了更直观地理解上述 DP 转移过程，我们以 样例 1 为例进行手动模拟：
场景设定：
- 序列：
a = [2, 1, 0, 3](下标 $1 \sim 4$) - 目标异或值：$k = 2$
- 前缀异或数组
pre：- $pre[0] = 0$
- $pre[1] = 2$
- $pre[2] = 2 \oplus 1 = 3$
- $pre[3] = 3 \oplus 0 = 3$
- $pre[4] = 3 \oplus 3 = 0$
DP 模拟过程：
- $i=1$ (数值 2)：
- 继承：$dp[1]$ 至少为 $dp[0]=0$。
- 尝试选区间：需找 $j < 1$ 使得 $pre[j] = pre[1] \oplus k = 2 \oplus 2 = 0$。
- 发现 $pre[0]=0$，符合条件！构成区间 $[1, 1]$。
- 决策：$dp[1] = \max(dp[0], dp[0]+1) = 1$。
- $i=2$ (数值 1)：
- 继承：$dp[2]$ 至少为 $dp[1]=1$。
- 尝试选区间：需找 $j < 2$ 使得 $pre[j] = pre[2] \oplus k = 3 \oplus 2 = 1$。
- 此前 $pre$ 值为 ${0, 2}$，无 $1$。无法构成新区间。
- 决策：$dp[2] = 1$。
- $i=3$ (数值 0)：
- 继承：$dp[3]$ 至少为 $dp[2]=1$。
- 尝试选区间：需找 $j < 3$ 使得 $pre[j] = pre[3] \oplus k = 3 \oplus 2 = 1$。
- 此前 $pre$ 值为 ${0, 2, 3}$，无 $1$。
- 决策：$dp[3] = 1$。
- $i=4$ (数值 3)：
- 继承：$dp[4]$ 至少为 $dp[3]=1$。
- 尝试选区间：需找 $j < 4$ 使得 $pre[j] = pre[4] \oplus k = 0 \oplus 2 = 2$。
- 发现 $pre[1]=2$，符合条件！这意味着区间 $[2, 4]$ (即 $a_2 \dots a_4$) 的异或和为 $k$。
- 决策：$dp[4] = \max(dp[3], dp[1] + 1) = \max(1, 1+1) = 2$。
最终答案： $2$。
通过这个过程可以看到，DP 的核心在于：在每一个位置 i，我们既要“守成”（继承 dp[i-1]），也要“进取”（查找是否存在 pre[j] 满足条件，从而接上一个新的区间）。
🤔 核心疑问解答：如何保证区间不重叠？
很多同学可能会问：“为什么直接用 $dp[j] + 1$ 就可以？怎么保证 $dp[j]$ 里统计的那些区间，和当前新选的区间 $[j+1, i]$ 不冲突？”
答案就在下标上：
- $dp[j]$ 的含义是：在下标 $1 \sim j$ 的范围内，最多能选多少个不相交区间。也就是说，这里面所有被选中的区间，结束位置都 $\le j$。
- 我们新选的区间是 $[j+1, i]$，它的起始位置是 $j+1$。
- 因为 $j < j+1$，所以新区间 $[j+1, i]$ 和 $1 \sim j$ 范围内的任何区间在物理位置上都是完全错开的，绝对不可能有重叠。这就是线性 DP 的妙处，通过下标的自然分割保证了“无后效性”和“无重叠”。
3. 优化 DP (贪心 + 桶/哈希表)
直接套用上面的 DP 方程，对于每个 $i$ 都要回头遍历找 $j$，时间复杂度是 $O(N^2)$，这对于 $N=5 \times 10^5$ 的数据规模是会超时的。我们需要优化查找过程。
观察转移方程：$\max_{j < i, pre[j] = pre[i] \oplus k} { dp[j] }$。 我们需要快速找到满足 $pre[j] = \text{target}$ 的所有 $j$ 中，$dp[j]$ 最大的那个值。
我们可以维护一个数组（桶）max_val[v]，用来记录：在前缀异或和为 v 的所有位置中，最大的 DP 值是多少。 即 max_val[v] = max(dp[j])，其中 pre[j] == v。
这样，当我们处理到位置 $i$ 时：
- 计算当前前缀异或和
curr = pre[i]。 - 计算我们需要寻找的目标前缀异或值
target = curr ^ k。 - 查找
max_val[target]。如果max_val[target]存在（即之前出现过满足条件的前缀和），说明我们可以形成一个新区间，此时候选答案为max_val[target] + 1。 - 同时，不要忘了 $dp[i]$ 至少可以继承 $dp[i-1]$（即代码中的
dp变量在循环开始时就保留了上一轮的值）。 - 更新桶：计算出 $dp[i]$ 后，用它来更新
max_val[curr]，供后面使用。
4. 算法流程总结
- 初始化数组
max_val为 -1（表示该异或值从未出现过），特别地max_val[0] = 0（表示还未开始时，前缀异或为 0，区间数为 0）。 - 维护一个变量
dp，表示当前位置的最大区间数。 - 遍历序列，维护当前的前缀异或和
curr_xor。 - 对于每个位置：
- 计算需要寻找的目标前缀值
target = curr_xor ^ k。 - 如果
max_val[target]有效，尝试更新dp = max(dp, max_val[target] + 1)。 - 更新当前前缀异或值的记录：
max_val[curr_xor] = max(max_val[curr_xor], dp)。
- 计算需要寻找的目标前缀值
- 最后输出
dp即为答案。
这种做法的时间复杂度是 $O(N)$，空间复杂度是 $O(2^M)$（取决于数值范围，题目中 $a_i < 2^{20}$）。
示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <algorithm>
#include <iostream>
#include <vector>
const int MAX_VAL = 1 << 20; // 2^20 = 1048576, 题目限制 a_i < 2^20, k < 2^20
int max_dp[MAX_VAL];
int main() {
// 优化 I/O 速度，避免大量输入输出导致超时
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n;
int k;
std::cin >> n >> k;
// 初始化 max_dp 数组
// max_dp[v] 存储的是：当某个位置的前缀异或和为 v
// 时，该位置及之前能得到的最大区间数
for (int i = 0; i < MAX_VAL; ++i) {
max_dp[i] = -1;
}
// 初始状态：还没有读取任何数时，前缀异或和为 0，区间数为 0
max_dp[0] = 0;
int current_xor = 0; // 当前的前缀异或和 (pre[i])
int dp = 0; // 当前位置的最大区间数 (dp[i])
for (int i = 1; i <= n; ++i) {
int a;
std::cin >> a;
current_xor ^= a; // 计算到当前位置 i 的前缀异或和
// 步骤 A: 尝试以当前位置 i 作为区间的结尾
// 我们需要找一个之前的断点 j-1，使得 pre[j-1] ^ pre[i] == k
// 即 pre[j-1] == pre[i] ^ k
int target = current_xor ^ k;
// 如果之前存在某个位置的前缀异或和等于 target
if (max_dp[target] != -1) {
// 尝试以当前位置为结尾构成一个新区间
// dp[i] = max(dp[i-1], max_dp[target] + 1)
// 注意：这里的 dp 变量实际上在迭代过程中一方面代表
// dp[i-1]，更新后代表 dp[i] 因为 dp[i] 至少是
// dp[i-1]，所以直接比较即可
dp = std::max(dp, max_dp[target] + 1);
}
// 更新当前前缀异或值的最大 dp 值
// 如果当前 dp 值比之前记录的更大，则更新
if (dp > max_dp[current_xor]) {
max_dp[current_xor] = dp;
}
}
std::cout << dp << std::endl;
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
