G. Chino with Train to the Rabbit Town 【异或前缀和】【牛客】【2019西北工业大学程序设计创新实践基地春季选拔赛】

题意：

给你一个n, k

代表有n个长度的序列

让你求出最多有多少个不重合的区间的异或和为k

题解：

我们假设有 前m个数字的异或和为 sum[m]

第m个数字为x  sum[m] = sum[m-1] ^ x

由于异或的性质：

a ^ a = 0

0 ^ a = a

a ^ a ^ a = a

所以当 sum[m] ^ k 在前面出现过 且没有 被消除过 则说明前面有区间异或和为k

AC_code:

#include<bits/stdc++.h>
using namespace std;
map<int,int> mp;

int main() {
	int n,k,sum,ans=0,x;
	scanf("%d%d",&n,&k);
	sum=0;
	mp[0]=1;
	for(int i=1; i<=n; i++) {
		scanf("%d",&x);
		sum=sum^x;
		if(mp[sum^k]>0) {
			ans++;
			mp.clear();//清除map
			sum=0;//重新初始化
			mp[0]=1;
		} else {
			mp[sum]=1;
		}
	}
	printf("%d\n",ans);
	return 0;
}