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

提供一个方便理解的思路

题目读完后，很明显是一个前缀异或，用一个数组存当前下标之前的所有数的异或和，调用跟前缀和一样，例

:

求区间

[l,r]

的异或和

CPP

a[l-1] xor a[r]

那什么情况下是最优的呢，当区间长度为

1

时是最具性价比的。遍历整个序列，把所有长度为

1

且等于

k

的区间都标记，这样我们可以得到这样的一个序列
样例

1:

2	1	0	3

给第一项，也就是

2

那一项打上标记，表示已经选取，接下来继续往后遍历如果不满足等于

k

，就从当前下标往前遍历，直到遇到标记过的数字或边界。这样每一次往前遍历，可以遍历到的所有数字都是没有标记，即未选择过的。那这样无论区间长度，都是最优的。
这里提供一个样例

:

CPP

5 2 
1 3 2 1 2

CPP

对所有长度为

1

且等于

k

的区间标记之后长这样

1	3	标记	1	标记

可以看到序列被分为两部分，对每个部分进行的每一项都往前遍历，找到第一个满足异或和为

k

的区间，然后标记当前下标

i

。因为遇到标记过的会结束循环，所以遍历的都为未被选择的项目，不存在更优解。

AC

代码

:

CPP

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

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

文章操作

相关推荐

评论

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