自动搬运

查看原文

来自洛谷，原作者为

	云殊呀 **

搬运于2025-08-24 22:35:12，当前版本为作者最后更新于2022-07-24 12:10:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解

前置知识：

做这个题之前我们先要了解与按位异或相关的两个性质：

1. $b=a\oplus b\oplus a$

2. $0\oplus1=1,0 \oplus 0=0$

以及按位或的一个性质：多个数按位或，任意一个数的第 $i$ 位为 $1$，则结果的第 $i$ 位为 $1$。

题目分析：

回到题目本身，要求将数列分成 $M$ 段，求每段的异或和，让最后每段异或和的按位或最小。首先每段异或和，根据上面异或的第一条性质，我们很容易想到前缀异或和，结合按位或的性质，我们可以按位从高往低贪心，尽量保证高位为 $0$，也就是说，让分成的 $M$ 段，每段都为 $0$。

代码设计：

对于第 $j$ 位，从前往后异或，统计出现 $0$ 的次数，若小于 $M$，则说明该位无论怎么分最后按位或结果都是 $1$。这里要注意的是，$0$ 的次数可能会大于 $M$，因为我们用的是前缀和，所以两个相邻 $0$ 区间合并之后异或和还是 $0$。

因为贪心思想为尽量保证高位为 $0$，所以低位的分发不能与高位相冲突，否则也是 $1$。

那么我们需要将高位不能作为 $M$ 段断点的位置标记下来，在枚举低位的时候，要同时异或和为 $0$ 以及该点是否为高位断点。

如果第 $j$ 位的结果能为 $0$，那么需要更新断点标记。

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define N 500010
ll n,m,a[N],flag[N],ans;
//flag数组为断点标记数组
int main(){
	ll i,j;
	cin>>n>>m;
	for(i=1;i<=n;i++){
		cin>>a[i];
	}
	for(j=62;j>=0;j--){
		ll tmp=0,sum=0;
		for(i=1;i<=n;i++){
			tmp ^= (a[i]>>j) & 1;
  			//判断第j位的异或和是否为1
			if(!tmp && !flag[i]) sum++;
  			//同时要保证不与高位冲突
		}
		if((tmp&1) || (sum<m)){
         //如果该位最终结果为1，或者不能分成超过M段
			ans+= 1ll<<j;
			continue;
		}
		tmp=0;
      //将第j为的断点标记加上去
		for(i=1;i<=n;i++){
			tmp^= (a[i]>>j) & 1;
			if(tmp && !flag[i]) flag[i]=1;
		}
	}
	cout<<ans;
	return 0;
}