题目描述

You are given N non-negative integers A1,A2,...,AN and another non-negative integer K.
For a integer X between 0 and K (inclusive), let f(X)=(X XOR A1) + (X XOR A2) + ... + (X XOR AN).
Here, for non-negative integers a and b, a XOR b denotes the bitwise exclusive OR of a and b.
Find the maximum value of f.
What is XOR?
The bitwise exclusive OR of a and b, X, is defined as follows:
When X is written in base two, the digit in the 2k's place (k≥0) is 1 if, when written in base two, exactly one of A and B has 1 in the 2k's place, and 0 otherwise.
For example, 3 XOR 5=6. (When written in base two: 011 XOR 101=110.)
Constraints
·All values in input are integers.
·\(1≤N≤10^5\)
·\(0≤K≤10^{12}\)
·\(0≤A_i≤10^{12}\)

输入

Input is given from Standard Input in the following format:

N K
A1 A2 ... AN

输出

Print the maximum value of f.

样例输入

3 7
1 6 3

样例输出

14

提示

The maximum value is: f(4)=(4 XOR 1)+(4 XOR 6)+(4 XOR 3)=5+2+7=14.

题解

首先想到按位考虑
一开始我采用贪心构造x，每一位如果0多那么应该选1，如果1多就选0
为了符合题意中比k小，用一个flag记录是否已经比k小了

  • 如果k的这位为1，如果我选0的话，那x必然已经比k小了
  • 如果k的这位为0，只有当flag=1即x已经比k小了，才可以选1

下面是WA贪心代码

#include <bits/stdc++.h>

#define ll long long
using namespace std;
const int maxn = 1e5+7;
ll s[maxn],sum[63];
ll K[63];
void getS(ll num){
    int i=0;
    while(num){
        if(num & 1) sum[i]++;
        ++i;
        num >>= 1;
    }
}
int main() {
    int n;
    ll k;
    scanf("%d%lld",&n,&k);
    for(int i=1;i<=n;++i){
        scanf("%lld",&s[i]);
        getS(s[i]);
    }
    int p=0;
    while(k){
        if(k & 1) K[p]++;
        ++p;
        k >>= 1;
    }
    p-=1;
    bool flag = 0;
    for(int i=p;i>=0;--i){
        if(sum[i] < n - sum[i]){
            if(K[i] == 1||flag == 1) sum[i] = 1;
            else sum[i]=0;
        }else{
            if(K[i] == 1) flag = 1;
            sum[i] = 0;
        }
    }
    ll res = 0;
    for(int i=0;i<=p;++i){
        if(sum[i]){
            res = res + (1ll << i);
        }
    }
    ll ans=0;
    for(int i=1;i<=n;++i){
        ans= ans + (res^s[i]);
    }
    printf("%lld\n",ans);
    return 0;
}

这个可以被下面这个样例卡：

5 8
8 0 0 0 8

问题出在：每一位如果0多那么应该选1，如果1多就选0
这种情况只能保证在这一位上是最优解，不能保证整体最优
所以应该把这个贪心改成不会遗漏状态的动态规划

dp[i][j][z]:i代表第i位，j代表这位选0还是1，z代表x是否已经比k小了;dp代表价值

  • 我是直接从k的最高位开始遍历的，所以要先特判k为0的情况，高于最高位的直接选0 
#include <bits/stdc++.h>
 
#define ll long long
using namespace std;
const int maxn = 1e5+7;
ll s[maxn],sum[65];
int mx;
ll K[65];
ll dp[65][2][2];
void getS(ll num){
    int i=0;
    while(num){
        if(num & 1) sum[i]++;
        ++i;
        num >>= 1;
    }
    mx = max(mx,i-1);
}
int main() {
    int n;
    ll k;
    scanf("%d%lld",&n,&k);
    for(int i=1;i<=n;++i){
        scanf("%lld",&s[i]);
        getS(s[i]);
    }
    int p=0;
    while(k){
        if(k & 1) K[p]++;
        ++p;
        k >>= 1;
    }
    if(p==0){
        ll ans=0;
        for(int i=1;i<=n;++i){
            ans += s[i];
        }
        printf("%lld\n",ans);
        return 0;
    }
    p-=1;
    mx = max(p,mx);
    dp[p][1][0] = (n*1ll-sum[p])*(1ll << p);
    dp[p][0][1] = sum[p]*(1ll << p);
    for(ll i=p - 1;i>=0;--i){
        ll b = (n*1ll-sum[i])*(1ll << i);//1
        ll a = sum[i]*(1ll << i);//0
        if(K[i] == 1){ 
            dp[i][1][0] = max(dp[i+1][0][0],dp[i+1][1][0]) + b;
            dp[i][1][1] = max(dp[i+1][0][1],dp[i+1][1][1]) + b;
            dp[i][0][1] = max(max(dp[i+1][0][0],dp[i+1][0][1]),max(dp[i+1][1][1],dp[i+1][1][0])) + a;
        }else if(K[i] == 0){
            dp[i][0][0] = max(dp[i+1][0][0],dp[i+1][1][0])+ a;
            dp[i][1][1] = max(dp[i+1][0][1],dp[i+1][1][1]) + b;
            dp[i][0][1] = max(dp[i+1][1][1],dp[i+1][0][1])+ a;
        }
    }
    ll ans = max(max(dp[0][1][0],dp[0][1][1]),max(dp[0][0][1],dp[0][0][0]));
    for(ll i=mx;i>p;--i){
        ans += sum[i]*(1ll<<i);
    }
    printf("%lld\n",ans);
    return 0;
}