专栏文章

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

iicaijy
P14359题解参与者 10已保存评论 10

文章操作

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

当前评论
10 条
当前快照
1 份
快照标识符
@minfo9i6
此快照首次捕获于
2025/12/02 01:39
3 个月前
此快照最后确认于
2025/12/02 01:39
3 个月前
查看原文
分享一个时间空间复杂度都是 O(n)O(n) 的做法。
这题很显然是 dp。令 dpidp_i 为前 ii 个数的答案，最终答案即为 dpndp_n。
考虑状态转移。很显然有当区间 [j+1,i][j+1,i] 的异或和为 kk 时， dpi=dpj+1dp_i = dp_j + 1。
这个时候可以写出一个比较暴力的代码（这里使用了类似前缀和的前缀异或和，跟前缀和是一码事）。
CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[500005];
int dp[500005];
int prexor[500005];
signed main(){
    int n,m;
    cin>>n>>m;
    for (int i=1;i<=n;i++){
        cin>>a[i];
        prexor[i]=a[i]^prexor[i-1];
    }
    for (int i=1;i<=n;i++){
        for (int j=1;j<=i;j++) dp[i]=max(dp[i],dp[j-1]+(int)((prexor[i]^prexor[j-1])==m));
    }
    cout<<dp[n];
}
但很显然时间复杂度太高了，那怎么优化呢？
观察到一个废话：dpdp 肯定是单调递增的，所以如果我们只需要找到最大的 jj 使得 [j+1,i][j+1,i] 的异或和为 kk 即可。
符合这个的 jj 会有 prexorj⊕prexori=k,prexorj=k⊕prexoriprexor_j \oplus prexor_i = k, prexor_j = k \oplus prexor_i。所以找到最大的符合 k⊕prexorik \oplus prexor_i 的 jj 即可。
最终代码：
CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[500005];
int dp[500005];
int prexor[500005];
unordered_map<int,int> mp;
signed main(){
    mp[0]=0;
    int n,m;
    cin>>n>>m;
    for (int i=1;i<=n;i++){
        cin>>a[i];
        prexor[i]=a[i]^prexor[i-1];
    }
    for (int i=1;i<=n;i++){
        dp[i]=dp[i-1];
        int want=m^prexor[i];
        if (mp.count(want)) dp[i]=max(dp[i],dp[mp[want]]+1);
        mp[prexor[i]]=i;
    }
    cout<<dp[n];
}

评论

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

正在加载评论...