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

icaijy · 2025-11-01 17:38:08 · 题解

分享一个时间空间复杂度都是 O(n) 的做法。

这题很显然是 dp。令 dp_i 为前 i 个数的答案，最终答案即为 dp_n。

考虑状态转移。很显然有当区间 [j+1,i] 的异或和为 k 时， dp_i = dp_j + 1。

这个时候可以写出一个比较暴力的代码（这里使用了类似前缀和的前缀异或和，跟前缀和是一码事）。

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

但很显然时间复杂度太高了，那怎么优化呢？

观察到一个废话：dp 肯定是单调递增的，所以如果我们只需要找到最大的 j 使得 [j+1,i] 的异或和为 k 即可。

符合这个的 j 会有 prexor_j \oplus prexor_i = k, prexor_j = k \oplus prexor_i。所以找到最大的符合 k \oplus prexor_i 的 j 即可。

最终代码：

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