题解：P14359 [CSP-J 2025] 异或和 / xor（民间数据）
newsname
·
·
题解
水一下 CSP-J 2025 的题解。
思路：
设前缀异或 p_i=a_1\oplus\cdots\oplus a_i，则区间 [l,r] 的异或和为 k 当且仅当 p_{l-1}=p_r\oplus k。设 dp_i 为前 i 个元素内能选的不相交区间最多个数。若区间以 i 结尾，则它的左端点前一个位置是某个 j 满足 p_j=p_i\oplus k，贡献为 d_j+1。因此只需维护每个前缀异或值 v 的“目前最优 dp”。
其中，“目前最优 dp”指的是：对每个前缀异或值 v，在当前下标之前出现过的所有位置 j 里，dp_j 的最大值。
故转移为
先用 $best$ 计算，再更新 $best$，可避免把当前下标当作左端的“空区间”，确保不重叠。
* 初始：$p_0=0$，$dp_0=0$，故令 $best[0]=0$，其余置为 $-\infty$。
* 取值范围 $a_i,k<2^{20}$，故数组 $best$ 大小取 $2^{20}$ 即可。时间复杂度 $\mathcal O(n+2^{20})$，空间复杂度 $\mathcal O(2^{20})$。足以通过本题。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=1<<20;
int best[maxn];
int main(){
int n,k;
cin>>n>>k;
for(int i=1;i<=maxn;i++) best[i]=-1e9;
best[0]=0;
int x=0,dp=0;
for(int i=1,a;i<=n;i++){
cin>>a;
x^=a;
int t=best[x^k];
int nd=dp;
if(t>-1e9) nd=max(nd,t+1);
dp=nd;
if(best[x]<dp) best[x]=dp;
}
cout<<dp;
return 0;
}
```