题解：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.代码

CPP

#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;
}

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

文章操作

1. 题意理解

2.贪心思路

3.代码

相关推荐

评论

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