题目

思路

怎么做？

首先观察题目，发现要取若干不相交的区间，求个数的最大值，因此可以考虑贪心。

怎么贪？

通过模拟推理不难发现，定义上一个区间的右端点为 $r_{last}$ ，可以枚举当前区间的右端点 $r_{now}$ ，使得存在一个左端点 $l$ ，满足 $r_{last}<l\le r_{now}$ 。

怎么判？

观察题目名称，可以想到使用前缀异或和。根据异或运算律，当 $pre_{r_{now}}\oplus k=pre_{l-1}$ 时，则表示取到了一个符合题意的 $[l,r_{now}]$ 区间。

代码

#include<bits/stdc++.h>
using namespace std;
int n,k,t,l,cnt,a[550000],pre[550000],plc[1100000];    //plc[i]表示前缀异或和为i的下标，即满足plc[pre[i]]=i
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;++i){
		cin>>a[i];
		pre[i]=pre[i-1]^a[i];
	}
	for(int i=1;i<=1100000;++i){
		plc[i]=-1;
	}
	for(int i=1;i<=n;++i){
		t=pre[i]^k;
		if(plc[t]>=l){    //枚举到了符合题意的右端点
			++cnt;
			l=i;
		}
		plc[pre[i]]=i;
	}
	cout<<cnt<<endl;
	return 0;
}

提交记录