[ Xor最小生成树 分治 字典树 ] Codeforces888G Xor-MST

裸的 xor x o r 最小生成树。

枚举每一位，把这一位为 0 0 的放在一起形成一个连通块，为 11 的放在一起形成一个连通块，之间用字典树求一条最小边，然后分治做。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=;
int k,n,m;
vector<int> g;
int Rt,nx[M][],num;
void Insert(int& x,int y,int d) {
    if(!x) x=++num,nx[x][]=nx[x][]=;
    if(d==-) return;
    Insert(nx[x][y>>d&],y,d-);
}
int Query(int x,int y,int d) {
    if(d==-) return ;
    int p=y>>d&;
    if(nx[x][p]) return Query(nx[x][p],y,d-);
    return Query(nx[x][p^],y,d-)+(<<d);
}
ll Solve(vector<int>g,int d) {
    if(!g.size()||d==-) return ;
    vector<int> a[];
    for(int v:g) a[v>>d&].push_back(v);
    ll Ans=Solve(a[],d-)+Solve(a[],d-);
    if(a[].size()&&a[].size()) {
        Rt=num=;
        for(int v:a[]) Insert(Rt,v,d-);
        int Res=<<d;
        for(int v:a[]) Res=min(Res,Query(Rt,v,d-));
        Ans+=Res+(<<d);
    }
    return Ans;
}
int main() {
    scanf("%d",&n);
    for(int i=;i<=n;i++) {
        int x;scanf("%d",&x);
        g.push_back(x);
    }
    printf("%I64d\n",Solve(g,));
    return ;
}