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

题意： 给定一个长度为

n

的序列

a

和

k

，尝试选择尽可能多的不相交的区间，使每个区间的异或和都为

k

。

思路： 由于

a\oplus b\oplus b=a

，考虑使用类似前缀和的做法来求区间异或和，并用 map 存可以使区间

[1,i]

的异或和为

x

的所有

i

。因为区间不相交，所以考虑维护最后一个区间的尾部，从

1

到

n

枚举

i

，upper_bound 一下不小于最后一个区间的结尾，小于

i

，且

[j,i]

的异或和为

k

（即

[1,j]

的异或和

\oplus [1,i]

的异或和）的最小的

j

（可以证明，选哪个

j

不影响答案），如果找到了，答案加

1

，更新最后一个区间的末尾。

代码：

CPP

#include<bits/stdc++.h>
using namespace std;
int a[500010],s[500010],vis=-1,ans,n,k;//vis初始化为-1，因为s[0]也可以用
map<int,vector<int>>mp;
int main(){
    cin>>n>>k;
    mp[0].push_back(0);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s[i]=s[i-1]^a[i];
        mp[s[i]].push_back(i);
    }
    for(int i=1;i<=n;i++){
        auto pl=upper_bound(mp[s[i]^k].begin(),mp[s[i]^k].end(),vis);//求大于vis（即不小于最后一个区间的结尾）的最小j
        if(pl==mp[s[i]^k].end())continue;//防止访问空地址导致RE
        if(*pl<i)ans++,vis=i-1;
    }
    cout<<ans<<endl;
}

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

文章操作

相关推荐

评论

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