专栏文章

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

ssigned_long_long
P14359题解参与者 49已保存评论 59

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
59 条
当前快照
1 份
快照标识符
@minfos4c
此快照首次捕获于
2025/12/02 01:39
3 个月前
此快照最后确认于
2025/12/02 01:39
3 个月前
查看原文
本人没打，写篇题解。话说为啥有人觉得这是 DP 啊？

题目解法

由于异或的逆运算就是自身，所以异或是可以通过类似前缀和的方法来快速求区间和的。那么对于每一个区间，有：
sr⊕sl−1=ksr⊕k=sl−1\begin{aligned} s_r\oplus s_{l-1} &= k \\ s_r\oplus k&=s_{l-1}\end{aligned}
定义上一个区间的右端点位置为 lstlst，于是，我们就可以通过枚举右端点 rr，如果存在一个 l(lst≤l<r)l(lst\le l<r) 使得 sr⊕k=sls_r\oplus k=s_l，那么就存在区间 (l,r](l,r] 符合条件了。
代码：
CPP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+10;
ll n,k;
ll a[N],s[N];
ll id[2005000],lst;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]^a[i];
    memset(id,-1,sizeof id);
    id[0]=0;
    ll ans=0;
    for(int r=1;r<=n;r++){
        ll x=s[r]^k;
        if(id[x]>=lst){
            ans++;
            lst=r;
        }
        id[s[r]]=r;
    }
    cout<<ans;
    return 0;
}

评论

共 59 条评论，欢迎与作者交流。

正在加载评论...