题解：CF2094E Boneca Ambalabu

· · 题解

我采用“分别求得每一个数与数组所有数异或的总和进行比较”来求得最终答案。当然，如果将所有数遍历一遍肯定会超时，所以我们可以换一种方式求得异或和。

首先 int 类型转换为二进制有 32 位，我统计这个数组中每一个数的每个二进制位出现一的次数，根据异或原则，两个数互相异或，二进制位同为一或者同为零的情况下，这个二进制位异或后为零，相反情况为一。

那么我就可以利用之前我统计好的数组，直接算出这个二进制位当前的贡献是多少，只需要 30 次二进制位遍历就可以算出这个数异或数组后的异或和。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int T, N;
//a[i][0]表示第i个数的第1个二进制位是否为1，是为1，否为0
long long a[200005][35];
//统计所有二进制位，1的数量
int sum[35];
int main()
{
    cin >> T;
    while (T--) {
        cin >> N;
        memset(sum, 0, sizeof(sum));
        for (int i = 1; i <= N; i++) {
            memset(a[i], 0, sizeof(a[i]));
            //这里我图方便用a[i][33]直接存储数组的数据
            cin >> a[i][33];
            for (int j = 30; j >= 0; j--) {
                if (((1 << j) & a[i][33]) != 0) {
                    sum[j]++, a[i][j]++;
                }
            }
        }
        long long ans = 0, S = 0;
        //遍历所有可能的答案
        for (int i = 1; i <= N; i++, S = 0) {
            for (int j = 0; j < 31; j++) {
                //如果这个二进制位为1，那么数组中数据的所有这个二进制位，只要是1就没有贡献
                if (((1 << j) & a[i][33]) != 0) {
                    //所以统计二进制位为零的数量
                    S += ((1ll << j) * (N - sum[j]));
                }
                else {
                    //相反就是有贡献，直接加上
                    S += ((1ll << j) * sum[j]);
                }
            }
            ans = max(ans, S);
        }
        cout << ans << '\n';
    }
    return 0;
}