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

FHY_patrickpp · 2025-11-01 15:59:07 · 题解

年龄限制考不了。反正明年就行了。

大意是选择尽可能多的不相交区间，使得每个区间的异或和都等于 k。

设前缀异或数组：

其中 s_0 = 0。

区间 [l, r] 的异或和可表示为：

要使区间 [l, r] 的异或和等于 k，需满足：

原问题转化为：在 s_0, s_1, \dots, s_n 中寻找尽可能多的下标对 (p, q)，满足：

• p < q
• s_q = s_p \oplus k
• 对应区间 [p+1, q] 互不重叠

可以用贪心来做，哈希表记录各前缀异或值最近出现位置，然后按照条件选取区间即可。

#include<bits/stdc++.h>
using namespace std;
const int N=500005;
int a[N],s[N];
unordered_map<int,int> lst;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    lst[0]=0;
    int last=0,ans=0;
    for(int i=1;i<=n;i++)
    {
        s[i]=s[i-1]^a[i];
        int tar=s[i]^k;
        if(lst.count(tar)&&lst[tar]>=last)
        {
            ans++;
            last=i;
        }
        lst[s[i]]=i;
    }
    cout<<ans;
    return 0;
}