888G. Xor-MST(分治法-最小异或生成树)

G. Xor-MST

最小生成树,但是边太多了,不好写

但是如果按照最高位1来分类成个集合

集合内部连边肯定比较优秀

集合与集合之间连一条边构成树就好了

连哪条边呢?可以采用字典树来完成

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e7+10;
int n,zi[maxn][2],id,a[maxn];
long long ans;
void insert(int x)
{
    int now=0;
    for(int i=30;i>=0;i--)
    {
        int t = (x>>i)&1;
        if( !zi[now][t] )    zi[now][t]=++id;
        now = zi[now][t];
    }
}
int ask(int x)
{
    int now=0,ans=0;
    for(int i=30;i>=0;i--)
    {
        int t = ((x>>i)&1);
        if( zi[now][t] )    now = zi[now][t];
        else    now = zi[now][t^1],ans+=(1<<i);
    }
    return ans;
}
void dfs(int l,int r,int dep)
{
    if( dep==-1||l>=r )    return;
    int mid = l;
    while( mid<=r&&((a[mid]>>dep)&1)==0 )    mid++;
    mid--;
    dfs(l,mid,dep-1);
    dfs(mid+1,r,dep-1);
    if( mid==l-1||mid==r )    return;
    for(int i=l;i<=mid;i++)    insert(a[i]);
    long long temp = 1e18;
    for(int i=mid+1;i<=r;i++)    
        temp = min( temp,(long long)ask(a[i]) );
    ans+=temp;
    for(int i=0;i<=id;i++)    zi[i][0]=zi[i][1]=0;
    id=0;
}
signed main()
{
    cin >> n;
    for(int i=1;i<=n;i++)    cin >> a[i];
    sort(a+1,a+1+n);
    dfs(1,n,30);
    printf("%lld",ans);
}