专栏文章

题解 CF2094E

HHYdroKomide
CF2094E题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipgztm4
此快照首次捕获于
2025/12/03 11:51
3 个月前
此快照最后确认于
2025/12/03 11:51
3 个月前
查看原文

题意：

给定一个整数数组 aa，求其中之一 aka_k 异或其它所有整数之和的最大值。

思路：

显然整数个数比较多不好下手，从二进制位上考虑。
由于 aka_k 的每一位必然是 00 或者 11，所以我们可以对于每一位，预处理当前这一位的 aka_k 如果是 00 或者 11 的话，能对最终结果造成多少贡献。预处理这一步一共是 O(nD)O(nD)，DD 表示二进制位数。
接下来可以直接暴力扫一遍所有的 aa，对于每一位提取它的贡献并且加和，最后找出最大值。所以还是 O(nD)O(nD) 的。

程序如下：

CPP
#include<cstdio>
#include<cstring>
using namespace std;
const int N=2e5+5,D=35;
int T,n,a[N];
long long con[D][2],power[D];
int main(){
	scanf("%d",&T);
	power[0]=1;
	for(int i=1;i<=30;i++)power[i]=power[i-1]*2;
	while(T--){
		long long ans=0;
		scanf("%d",&n);
		memset(con,0,sizeof(con));
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			int tmp=a[i];
			for(int j=1;j<=30;j++){
				con[j][!(tmp%2)]+=power[j-1];
				tmp/=2;
			}
		}
		for(int i=1;i<=n;i++){
			int tmp=a[i];
			long long nowans=0;
			for(int j=1;j<=30;j++){
				nowans+=con[j][tmp%2];
				tmp/=2;
			}
			if(nowans>ans)ans=nowans;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

THE END

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...