题目 | XOR to All - 颢天笔记

AtCoder Regular Contest 135

C - XOR to All

https://atcoder.jp/contests/arc135/tasks/arc135_c

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : $500$ points

Problem Statement

You are given a sequence of non-negative integers $A = (A_{1}, \dots, A_{N})$ . You can do the operation below any number of times (possibly zero).

Choose an integer $x \in {A_{1}, \dots, A_{N}}$ .
Replace $A_{i}$ with $A_{i} \oplus x$ for every $i$ ( $\oplus$ denotes the bitwise $XOR$ operation).

Find the maximum possible value of $\sum_{i = 1}^{N} A_{i}$ after your operations.

Constraints

$1 \leq N \leq 3 \times 10^{5}$
$0 \leq A_{i} < 2^{30}$

Input

Input is given from Standard Input from the following format:

$N$
$A_{1}$ $\dots$ $A_{N}$

Output

Print the maximum possible value of $\sum_{i = 1}^{N} A_{i}$ after your operations.

Sample Input 1

5
1 2 3 4 5

Sample Output 1

19

Here is a sequence of operations that achieves $\sum_{i = 1}^{N} A_{i} = 19$ .

Initially, the sequence $A$ is $(1, 2, 3, 4, 5)$ .
An operation with $x = 1$ changes it to $(0, 3, 2, 5, 4)$ .
An operation with $x = 5$ changes it to $(5, 6, 7, 0, 1)$ , where $\sum_{i = 1}^{N} A_{i} = 5 + 6 + 7 + 0 + 1 = 19$ .

Sample Input 2

5
10 10 10 10 10

Sample Output 2

50

Doing zero operations achieves $\sum_{i = 1}^{N} A_{i} = 50$ .

Sample Input 3

5
3 1 4 1 5

Sample Output 3

18

我的笔记

本题中的 "You can do the operation below any number of times (possibly zero)." 和 "Sample 1" 就是个迷惑人的幌子，说是可以进行任意次异或操作，然而结果等价于只进行一次异或操作，因为： $(A_{x} XOR A_{i}) XOR (A_{y} XOR A_{i}) = A_{x} XOR A_{y}$

具体到示例 $1$ 的 $(1, 2, 3, 4, 5)$ ，先用 $1$ 异或得到 $(0, 3, 2, 5, 4)$ ，再用 $5$ 异或得到 $(5, 6, 7, 0, 1)$ ，这俩步其实等价于直接用 $4$ 异或（ $4$ 是第二步 $5$ 原来对应的那个数）

所以该题简化为：有 $N$ 个数，在其中选 $1$ 个数（可以不选），用这个数与这 $N$ 个数异或，将结果求和，求和的最大值。

然后直接暴力求解一个个异或再求和肯定是不可行的，要整体来操作。

本题异或、求和都可以看成按位操作，所以可以直接统计出每一位 $0$ 和 $1$ 的数量，如果异或的那个数该位为 $0$ ，那么 $0 、 1$ 不翻转，如果是 $1$ 那么 $0 、 1$ 翻转，统计一次需要循环 $30$ 次（因为数字不大于 $2^{30}$ ）。统计了一位之后就可以把这一位算出来，第一位乘 $2^{0}$ ，第二位乘 $2^{1}$ ，第三位乘 $2^{2}$ ， $\dots$ ，第三十位乘 $2^{29}$ ，这样就只花了 $30$ 次循环就求出了一次和。总共有 $N$ 个数字，用每个数字都试一遍，然后找到最大值即可，时间复杂度 $O (30 \times N)$ ， $1 \leq N \leq 3 \times 10^{5}$ ，因此可以 AC.

代码

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    vector<int> A(N);
    vector<int> bit(30);
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
        int t = A[i];
        for (int i = 0; t; i++, t >>= 1)
        {
            bit[i] += t & 1;
        }
    }
    long long sum = accumulate(A.begin(), A.end(), 0LL);
    for (int i = 0; i < N; i++)
    {
        long long cur_sum = 0, d = 1;
        int t = A[i], bit_sum;
        for (int j = 0; j < 30; j++)
        {
            if (t & 1)
            {
                bit_sum = N - bit[j];
            }
            else
            {
                bit_sum = bit[j];
            }
            t >>= 1;
            cur_sum += d * bit_sum;
            d <<= 1;
        }
        sum = max(sum, cur_sum);
    }
    cout << sum << endl;
    return 0;
}

题目 | XOR to All