题解 CF2094E

· · 题解

题意：

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

思路：

显然整数个数比较多不好下手，从二进制位上考虑。

由于 a_k 的每一位必然是 0 或者 1，所以我们可以对于每一位，预处理当前这一位的 a_k 如果是 0 或者 1 的话，能对最终结果造成多少贡献。预处理这一步一共是 O(nD)，D 表示二进制位数。

接下来可以直接暴力扫一遍所有的 a，对于每一位提取它的贡献并且加和，最后找出最大值。所以还是 O(nD) 的。

程序如下：

#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