内推鸭

题解：贪心+位运算

本题是蚂蚁算法岗2925-9-7笔试第一题原题：【蚂蚁算法岗】2025-9-7-第一题-按位或运算

题目内容拆解

本题本质是：每次可以选择一个数组中的数 $x$ ，将所有元素异或 $x$ ，目标是最大化数组元素之和。由于异或操作可逆，且每次操作都可以选择任意 $x$ ，最优方案一定是选择某个 $a_i$ 作为 $x$ ，并只操作一次。

算法实现

统计每一位上为 $1$ 的元素个数，记为 $cnt1[b]$ ， $b$ 为二进制位。
枚举每个 $a_i$ $a_{i}$ 作为异或操作的 $x$ $x$ ，计算异或后所有元素之和：
- 对每一位 $b$ ，若 $a_i$ 该位为 $1$ ，则异或后该位为 $1$ 的元素个数为 $n-cnt1[b]$ ，否则为 $cnt1[b]$ 。
- 该位贡献为 $1<<b$ 乘以上述个数。
- 累加所有位贡献，得到异或后数组之和。
对所有 $a_i$ 取最大值，与原数组和比较，输出最大值。

时间复杂度分析

每组数据统计位数 $O(n)$ ，枚举每个 $a_i$ 计算贡献 $O(n\cdot\log A)$ ，总复杂度 $O(n\cdot\log A)$ ，空间复杂度 $O(\log A)$ 。

#include <bits/stdc++.h>
using namespace std;

int main() {
  cin >> T;
  while (T--) {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<long long> cnt1(31, 0); // 每一位上为1的个数
    long long baseSum = 0;
    for (int i = 0; i < n; ++i) {
      cin >> a[i];
      baseSum += a[i];
      for (int b = 0; b < 31; ++b) {
        if (a[i] >> b & 1) {
          cnt1[b]++;
        }
      }
    }

    long long res = baseSum; // 不操作的情况
    for (int i = 0; i < n; ++i) {
      long long cur = 0;
      for (int b = 0; b < 31; ++b) {
        long long bitVal = 1LL << b;
        if (a[i] >> b & 1) {
          // 该位为1 -> xor后该位为 (n - cnt1[b]) 个1
          cur += (n - cnt1[b]) * bitVal;
        } else {
          // 该位为0 -> xor后该位为 cnt1[b] 个1
          cur += cnt1[b] * bitVal;
        }
      }
      res = max(res, cur);
    }
    cout << res << endl;
  }
  return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T;
        T = sc.nextInt();
        while (T-- > 0) {
            int n;
            n = sc.nextInt();
            int[] a = new int[n];
            long[] cnt1 = new long[31]; // 每一位上为1的个数
            long baseSum = 0;
            for (int i = 0; i < n; ++i) {
                a[i] = sc.nextInt();
                baseSum += a[i];
                for (int b = 0; b < 31; ++b) {
                    if (((a[i] >> b) & 1) == 1) {
                        cnt1[b]++;
                    }
                }
            }

            long res = baseSum; // 不操作的情况
            for (int i = 0; i < n; ++i) {
                long cur = 0;
                for (int b = 0; b < 31; ++b) {
                    long bitVal = 1L << b;
                    if (((a[i] >> b) & 1) == 1) {
                        // 该位为1 -> xor后该位为 (n - cnt1[b]) 个1
                        cur += (n - cnt1[b]) * bitVal;
                    } else {
                        // 该位为0 -> xor后该位为 cnt1[b] 个1
                        cur += cnt1[b] * bitVal;
                    }
                }
                res = Math.max(res, cur);
            }
            System.out.println(res);
        }
    }
}

T = int(input())
for _ in range(T):
    n = int(input())
    a = list(map(int, input().split()))
    cnt1 = [0] * 31  # 每一位上为1的个数
    baseSum = 0
    for x in a:
        baseSum += x
        for b in range(31):
            if (x >> b) & 1:
                cnt1[b] += 1

    res = baseSum  # 不操作的情况
    for x in a:
        cur = 0
        for b in range(31):
            bitVal = 1 << b
            if (x >> b) & 1:
                # 该位为1 -> xor后该位为 (n - cnt1[b]) 个1
                cur += (n - cnt1[b]) * bitVal
            else:
                # 该位为0 -> xor后该位为 cnt1[b] 个1
                cur += cnt1[b] * bitVal
        res = max(res, cur)
    print(res)

package main

import (
    "bufio"
    "fmt"
    "os"
)

func main() {
    in := bufio.NewReader(os.Stdin)
    var T int
    fmt.Fscan(in, &T)
    for ; T > 0; T-- {
        var n int
        fmt.Fscan(in, &n)
        a := make([]int64, n)
        cnt1 := make([]int64, 31) // 每一位上为1的个数
        var baseSum int64 = 0
        for i := 0; i < n; i++ {
            fmt.Fscan(in, &a[i])
            baseSum += a[i]
            for b := 0; b < 31; b++ {
                if (a[i]>>b)&1 == 1 {
                    cnt1[b]++
                }
            }
        }

        res := baseSum // 不操作的情况
        for i := 0; i < n; i++ {
            var cur int64 = 0
            for b := 0; b < 31; b++ {
                bitVal := int64(1) << b
                if (a[i]>>b)&1 == 1 {
                    // 该位为1 -> xor后该位为 (n - cnt1[b]) 个1
                    cur += (int64(n) - cnt1[b]) * bitVal
                } else {
                    // 该位为0 -> xor后该位为 cnt1[b] 个1
                    cur += cnt1[b] * bitVal
                }
            }
            if cur > res {
                res = cur
            }
        }
        fmt.Println(res)
    }
}