CF888G Xor-MST

题意

有一张\(n\)个点的完全图，点权为\(a[i]\)，\(w_{i,j}=a_i \space \oplus a_j\)。问这个图的最小生成树。
\(n \leq 2*10^5,a[i]<2^{30}\)
传送门

思路

前一题想写个\(Boruvka\)，然后发现可以用熟知的\(Kruskal\)过掉，于是就又找了一道。
然后发现，好像也没啥关系，而且2300难度肉眼可见
只要把点权扔进一棵\(trie\)里，然后根据\(Boruvka\)或者是简单思考，对于第\(k\)位：

1. 如果只有0或1，那么直接跳到下一位。
2. 01都有，那么贪心，有且只有一条边连接两边，在两边找出异或值最小的两个数，加上它们的异或和，我是直接暴力两边一直搜的，也可以把一边建一棵\(trie\)，另一边的拉上去跑。然后01两边一定是分别跑最小生成树的（可以分开考虑），递归下去就能求得答案。

#include <bits/stdc++.h>
typedef long long ll;
const int N=200005,W=30;
int trie[N*30][2],cnt=1,n;
void insert(int x){
    int u=1;
    for (int i=W;i>=0;i--){
        int c=(x&(1<<i))>>i;
        if (!trie[u][c]) trie[u][c]=++cnt;
        u=trie[u][c];
    }
}
int read(){
    char c=getchar();
    int t=0;
    while (c<'0' || c>'9') c=getchar();
    while (c>='0' && c<='9') t=t*10+c-'0',c=getchar();
    return t;
}
ll query(int x,int y,int k){
    if (x==0 || y==0) return 1<<30;
    if (k==0) return 0;
    int f1=std::min(query(trie[x][0],trie[y][0],k-1),query(trie[x][1],trie[y][1],k-1));
    int f2;
    if (f1>=(1<<30)) f2=std::min(query(trie[x][0],trie[y][1],k-1),query(trie[x][1],trie[y][0],k-1))+(1<<(k-1));
    else f2=1<<30;
    return std::min(f1,f2);
}
ll solve(int k,int x){
    if (k==0 || x==-1) return 0;
    int t=0;
    if (trie[k][0] && trie[k][1]) t=(1<<(x-1))+query(trie[k][0],trie[k][1],x-1);
    return solve(trie[k][0],x-1)+solve(trie[k][1],x-1)+t;
}
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++) insert(read());
    printf("%lld\n",solve(1,W+1));
}

后记

代码较丑，自己都嫌弃，请谅解