题目描述

难度分:$1423$

输入$n(1 \leq n \leq 10^5)$、$k(0 \leq k \leq 10^{12})$和长为$n$的数组$a(0 \leq a[i] \leq 10^{12})$。

选择一个$[0,k]$中的整数$x$，最大化$(x \oplus a[1]) + (x \oplus a[2]) + … + (x \oplus a[n])$。

输出这个最大值。

输入样例$1$

3 7
1 6 3

输出样例$1$

14

输入样例$2$

4 9
7 4 0 3

输出样例$2$

46

输入样例$3$

1 0
1000000000000

输出样例$3$

1000000000000

算法

按位贪心

这样的题目一般都要拆位，从$k$的最高位往低位考虑，在这个过程中构造$x$。在构造的过程中需要考虑$x \leq k$这个限制，和数位DP的过程类似，初始化一个$islimit=$true。对于当前的位，分别考虑$x$在这一位是$1$还是$0$（如果$islimit=$true，那这一位只能和$k$保持一致，否则这一位就能取$0$和$1$两个值），分别算出目标函数在这一位的答案$t_1$和$t_2$，然后分情况讨论$x$在当前位填的数：

1. 如果当前位的填数上界$ub=1$。(1) 在$t_1 \gt t_2$时这一位就可以填$1$。(2) 在$t_1 \leq t_2$时这一位就填$0$。如果当前填的数和$k$原本的不一致，那么$islimit=$false，否则$islimit$保持不变。
2. 如果当前的填数上界$ub=0$，那就无所谓了，当前位只能填$0$，无论如何也不会改变$islimit$的取值。

得到$x$之后，遍历数组把目标函数算出来就可以了。

复杂度分析

时间复杂度

$k$的位数是$O(log_2k)$，对于$k$的每个位，需要遍历$a$数组来确定填的数字。因此，整个算法的时间复杂度为$O(nlog_2k)$。

空间复杂度

在整个算法过程中只使用了有限的几个变量，因此额外空间复杂度为$O(1)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010;
int n;
LL k, a[N];

int main() {
    scanf("%d%lld", &n, &k);
    for(int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }
    int b = 0;
    while((k>>b) > 0) b++;
    LL x = 0;
    bool islimit = true;
    for(int j = b - 1; j >= 0; j--) {
        int bit = k>>j&1;
        int ub = islimit? bit: 1;
        LL t1 = 0, t2 = 0;
        for(int i = 1; i <= n; i++) {
            t1 += (1LL ^ (a[i]>>j&1)) << j;
            t2 += (0LL ^ (a[i]>>j&1)) << j;
        }
        if(ub == 1) {
            if(t1 > t2) {
                x |= 1LL << j;
                if(bit == 0) {
                    islimit = false;
                }
            }else {
                if(bit == 1) islimit = false;
            }
        }
    }
    LL ans = 0;
    for(int i = 1; i <= n; i++) {
        ans += x ^ a[i];
    }
    printf("%lld\n", ans);
    return 0;
}