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

· · 题解

提供一个方便理解的思路

题目读完后，很明显是一个前缀异或，用一个数组存当前下标之前的所有数的异或和，调用跟前缀和一样，例: 求区间 [l,r] 的异或和 

a[l-1] xor a[r]
那什么情况下是最优的呢，当区间长度为 1 时是最具性价比的。遍历整个序列，把所有长度为 1 且等于 k 的区间都标记，这样我们可以得到这样的一个序列
样例 1:		 2 1 0 3

给第一项，也就是 2 那一项打上标记，表示已经选取，接下来继续往后遍历如果不满足等于 k ，就从当前下标往前遍历，直到遇到标记过的数字或边界。这样每一次往前遍历，可以遍历到的所有数字都是没有标记，即未选择过的。那这样无论区间长度，都是最优的。
这里提供一个样例: 

5 2 
1 3 2 1 2
3
对所有长度为 1 且等于 k 的区间标记之后长这样 1 3 标记 1 标记

可以看到序列被分为两部分，对每个部分进行的每一项都往前遍历，找到第一个满足异或和为 k 的区间，然后标记当前下标 i 。因为遇到标记过的会结束循环，所以遍历的都为未被选择的项目，不存在更优解。

AC$代码$: 
#include<bits/stdc++.h>
using namespace std;
long long a[500001],b[500001],c[500001];
//a存序列，b存前缀异或，c为标记数组
int main(){
    long long n,k,ans=0;//ans记录区间数量
    cin>>n>>k;
    for(long long i=1;i<=n;i++){
        cin>>a[i];
        b[i]=b[i-1] xor a[i];//记录从1到i的异或和
        if(a[i]==k){//标记长度1的区间
            c[i]=1;
            ans++;
        }
        else{
            for(long long j=i-1;j>=1;j--){
                if(c[j]==1) break;//遇到标记过的就退出循环
                if((b[i] xor b[j-1])==k){
                    ans++;
                    c[i]=1;//往前遍历，只需标记i项
                    break;
                }
            }
        }
    }
    cout<<ans;
    return 0;
}