题解：P9178 [COCI2022-2023#5] Diskurs

· · 题解

题意：对于长度为 N 的数列中的每一个数，求数列中的数与它的哈明距离最大为多少。哈明距离指两个数的二进制表示中不一样的位数。

首先，如果数列中的一个数为 0 ，那么数列中的数与它的哈明距离最大值就等于数列中的数的 popcount （二进制表示中 1 的个数）最大值。

于是我们可以想到，对于每个 a_i ，都把数列中的所有数异或上 a_i ，将 a_i 强制变成 0 。因为两个数异或上同一个数后，二进制表示中原本相同的位仍旧相同，原本不同的位仍旧不同，所以任意两个数间的哈明距离不变。

现在我们将原问题拆解为了两个问题：全局异或和全局 popcount 最大值，考虑用 01trie 处理。

全局异或x可以对于x二进制表示中的每一个 1 的位置对应的所有 trie 树节点暴力交换左右儿子。

说得可能不是很清楚，这里举个例子，如果m=3,x=5，那么就将 trie 树第一层和第三层的所有节点交换左右儿子。

然后全局 popcount 可以对于每一节点维护一个 val 值，在每一次修改之后将节点 p 的 val 更新为max(val[son[p][0]],val[son[p][1]]+1)

但——是，直接这样做时间复杂度显然是不对的，每一个 a_i 和上一个数最多有 m 位不一样，所以需要进行 m 次修改，修改第 x 位一次的复杂度上限为 trie 树第 x 层的点数上限，即 O(2^x) ，那么修改 m 位的总时间复杂度为 O(2^m) ，整个程序的复杂度就是 O(2^m) ，T飞了。

我们试着找一些可以优化的地方，单次修改的复杂度不是很好优化，那么我们开始优化总的修改次数。

考虑对原数组排序，排完序后，从高往低第 i 位就至多会修改 2^i 次，这一点不理解的同学可以对 1 ～ 64 的二进制表示打个表理解一下，这里不细讲了。

然而，现在对于第 i 位的修改总次数上限为 2^i×2^i=2^{2i} ，依然不过关，所以可以在建 trie 树时，将低位放在靠近根的位置，将修改第 i 位一次的复杂度为 O(2^{m-i}) ，对于第 i 位的修改总次数上限就变成了 2^i\times2^{m-i}=2^m ，再加上排序的时间复杂度，整个程序的复杂度就是 O(n\log n+m2^m) ，可以通过，实际上每一位不一定被卡到修改次数上限，所以对于 n<2^m 的测试点跑不到这个复杂度。

看不懂的就着代码理解一下吧：

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,ans[1100010],son[2200010][2],val[2200010],tot,root;
pair<int,int> a[1100010];
void pushup(int p){
    if(son[p][0]&&son[p][1])val[p]=max(val[son[p][0]],val[son[p][1]]+1);//下一位为0不会对答案做贡献，下一位是1则会做出1的贡献 
    else if(son[p][0])val[p]=val[son[p][0]];
    else if(son[p][1])val[p]=val[son[p][1]]+1;
    else val[p]=0;
}
void modify(int p,int c){
    if(!c){
        swap(son[p][0],son[p][1]);//c每往下走一层就会减一，c==0就意味着到了指定层，交换左右儿子 
        pushup(p);
        return;
    }
    if(son[p][0])modify(son[p][0],c-1);
    if(son[p][1])modify(son[p][1],c-1);
    pushup(p);
}
void update(int &p,int x,int len){
    if(!p)p=++tot;
    if(!len)return;
    update(son[p][x&1],x>>1,len-1);//从最低位开始遍历 
    pushup(p);
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i].first);
        a[i].second=i;
        update(root,a[i].first,m);//建trie树 
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){
        for(int j=0;j<m;j++)if((a[i].first>>j&1)^(a[i-1].first>>j&1))modify(1,j);//与上一个数的第j位不一样就将第j层所有节点交换左右儿子 
        ans[a[i].second]=val[root];
    }
    for(int i=1;i<=n;i++)printf("%lld ",ans[i]);
}