题目

思路

怎么做？

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

怎么贪？

通过模拟推理不难发现，定义上一个区间的右端点为 $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;
}

提交记录

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, k;
int a[500005], sz[500005];
map<int, int>mp;
signed main() {
	cin >> n >> k;
mp[0]=0;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		sz[i] = sz[i - 1] ^ a[i];


	}
	int lstpo = 0;
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		
		//cout<<sz[i]<<"  "<<k<<"  "<<(k^sz[i])<<"  "<<mp[sz[i] ^ k]<<" "<<ans<<endl;

		 
		int z = sz[i] ^ k;
	
		if (mp.count(z)&&mp[z] >= lstpo) {
			ans++;
			lstpo = i;

		}
		mp[sz[i]] = i;
	}


	cout << ans;
}