c++ - 最大化异或方程

Question

问题陈述:

Given an array of n elements and an integer k, find an integer x inthe range [0,k] such that Xor-sum(x) is maximized. Print the maximumvalue of the equation.

Xor-sum(x)=(x XOR A1)+(x XOR A[2])+(x XOR A[3])+…………..+(x XOR A[N])

Input Format

The first line contains integer N denoting the number of elements inA. The next line contains an integer, k, denoting the maximum valueof x. Each line i of the N subsequent lines(where 0<=i<=N) containsan integer describing Ai.

Constraints

1<=n<=10^5
0<=k<=10^9
0<=A[i]<=10^9

Sample Input

3
7
1
6
3

Sample Output

14

Explanation

Xor_sum(4)=(4^1)+(4^6)+(4^3)=14.

这个问题在 Infosys 需求测试中被问到。我正在浏览前一年的论文&我遇到了这个问题。我只能想出一个蛮力解决方案，它只是为了计算方程式对于 [0,k] 范围内的每个 x 并打印最大值。但是，该解决方案不适用于给定约束。

我的解决方案

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n, k, ans = 0;
  cin >> n >> k;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i <= k; i++) {
    int temp = 0;
    for (int j = 0; j < n; j++) {
      temp += (i ^ a[j]);
    }
    ans = max(temp, ans);
  }
  cout << ans;
  return 0;
}

我在网站上找到了解决方案。我无法理解代码的作用，但此解决方案对某些测试用例给出了错误的答案。

Scroll down to question 3

Answer 1

这里的技巧是 XOR 并行、独立地处理位。您可以优化 x 的每一位。考虑到约束条件，暴力破解需要 2*32 次尝试。