组一辈子钥队

· · 题解

ZROI#3312. 魔力之钥

题意：给两个长度为n的数组a,b~其中,a_i,b_i\in[0,2^{31}),n<=10^5，找到一个x使得\sum\lvert a_i-(b_i\oplus x)\rvert最小，输出这个式子的最小值。

首先有个我一开始就没看出来的结论，通过比较两个数最高的不同位上谁是1来比的，也就是两数的异或值的最高位上谁是1，因此a_i和b_i\oplus x的大小就是看a_i\oplus b_i\oplus x的最高位，也就是(a_i\oplus b_i)\oplus x。而

当a_i和b_i能够放在一起考虑时，发现能够通过逐位确定x把每一位的贡献从绝对值分离出来，具体而言，对于a_i\oplus b_i建字典树，然后让x在上面dfs，往左则表示此位为0，此时右子树a_i\oplus b_i\oplus x此位的值为1，因此要加上右子树的贡献，但我们此时只知道x的前k位，低位的贡献就需要预处理了。

令g_{i,j,k}表示所有a_i\oplus b_i在i子树内的(a_i,b_i)在x第j位为k时在第j位上的贡献，因此插入a_i\oplus b_i的时候遍历所有更低位，将a_i-b_i\oplus x在遍历的位上的正负性和点i代表的位以下a_i和b_i的正负性相乘再乘上遍历的位本身的贡献即可。上面的位不需要考虑，因为遍历到i说明x是顺着i子树内所有a_i\oplus b_i(显然相同)的高位走的，所以a_i\oplus b_i\oplus x高位全为0。

然后dfs时记录f_{i,j}表示x第i位为j时所有(a_i,b_i)的贡献，每次跳一边的点时把另一子节点v的g_{v,i,j}加到f_{i,j}上即可，最后无法遍历时剩下没选的低位贪心选择每一位的较小贡献统计就行，具体看代码。

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010
#define ll long long
const int K=32;
int trie[MAXN*K][2],n,cnt=1;
ll f[MAXN*K][2],ans=1e18;
ll g[MAXN*K][K][2];
void insert(int x,int a,int b){
    int p=1;
    for(int i=30;i>=0;i--){
        int now=(x>>i)&1;
        if(!trie[p][now])
            trie[p][now]=++cnt;
        p=trie[p][now];
        int q=(((a>>i)&1)?1:-1);
        for(int j=i;j>=0;j--)
            for(int now:{0,1})
                g[p][j][now]+=(1ll<<j)*(((a>>j)&1)-(((b>>j)&1)^now))*q;
    }
}
void dfs(int x,int k,ll sum){
    if(k<0||!x){
        for(int i=0;i<=k;i++)
            sum+=min(f[i][0],f[i][1]);
        ans=min(ans,sum);
        return;
    }
    for(int now:{0,1}){
        for(int i=k;i>=0;i--)
            for(int j:{0,1})
                f[i][j]+=g[trie[x][!now]][i][j];
        dfs(trie[x][now],k-1,sum+f[k][now]);
        for(int i=k;i>=0;i--)
            for(int j:{0,1})
                f[i][j]-=g[trie[x][!now]][i][j];
    }
}
int a[MAXN],b[MAXN];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++){
        cin>>b[i];
        insert(a[i]^b[i],a[i],b[i]);
    }
    dfs(1,30,0);
    cout<<ans<<"\n";
    return 0;
}