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

· · 题解

1. 题意理解

给定一个长度为 n 的非负整数序列 a[1..n] 和一个整数 k 。
定义区间 [l, r] 的权值为 a[l] ⊕ a[l+1] ⊕ ... ⊕ a[r]。
要求选出最多的不相交区间，每个区间的权值都等于 k。 输出最大区间数量。

2.贪心思路

这是一个经典的不相交区间选择问题，可以用贪心解决： 从左到右扫描，记录当前前缀异或和。
当我们发现当前前缀异或和 p[r] 等于某个之前出现过的 p[pos] ⊕ k 时，说明区间 [pos+1, r] 的权值是 k。 为了不相交，一旦我们选择了一个区间，就重置记录，从下一个位置重新开始（因为不能重叠）。
为什么这样贪心是对的？
因为如果我们在最早可能的位置结束一个区间，就能给右边留下更多的空间去形成新区间，这样总体数量不会比最优解差。

3.代码

#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
    int n,k;
    cin>>n>>k;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }

    if(k==0){
        int cnt=0;
        for(int i=0;i<n;i++){
            if(a[i]==0) cnt++;
        }
        cout<<cnt<<endl;
        return 0;
    }

    unordered_set<int>s;
    seen.insert(0);
    int p=0;
    int c=0;

    for(int i=0;i<n;i++){
        p^=a[i];
        if(s.find(p^k)!=s.end()){
            c++;
            s.clear();
            s.insert(p);
        } else {
            s.insert(p);
        }
    }

    cout<<c<<endl;

    return 0;
}