题目链接

大意

给出\(N\)个点的点权，定义两个点之间的边权为这两个点权的异或和，求这\(N\)个点间的最小生成树。

思路

贪心地想，相连的两个点异或和应当尽量的小。
那么应先从高位确定，因为高位的大小比低位大，所以高位间的连边首先要尽量小。

考虑对于某一数位怎么做：
首先将这一位的数字全部抽出来，变成一个01串。
明显0应先和0连，1应先和1连，最后留出一条0和1间的连边要尽量小。
那么全0和全1的部分就又可以分治到下一个数位去了。
考虑0和1间的连边怎么做：
那么我们对于0和1中的某个集合中的某个数，把它拿到另外一个数集中去比较，
从高位往下比，每位尽量贴近该数，对于每个数都这样操作然后取较小值就可以得到这条边了。

注：

• 找数可以用Trie树实现。
• 时间复杂度根据实现不同在\(O(N\cdot log(N))\)与\(O(N\cdot log(N)^2)\)之间。

代码

#include<queue>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXK=3;
const int MAXN=200005;
const int INF=2e9;
int N,A[MAXN],Cnt;
long long Ans;
struct Node{
    int dep,L,R;
    int ch[MAXK];
}s[MAXN*40];
void Push_Up(int rt){
    if(s[rt].ch[0]&&s[rt].ch[1]){
        s[rt].L=min(s[s[rt].ch[0]].L,s[s[rt].ch[1]].L);
        s[rt].R=max(s[s[rt].ch[0]].R,s[s[rt].ch[1]].R);
    }
    else if(s[rt].ch[0])s[rt].L=s[s[rt].ch[0]].L,s[rt].R=s[s[rt].ch[0]].R;
    else if(s[rt].ch[1])s[rt].L=s[s[rt].ch[1]].L,s[rt].R=s[s[rt].ch[1]].R;
}
void Insert(int rt,int val,int k,int id){
    s[rt].dep=k;
    if(k==-1){s[rt].L=s[rt].R=id;return ;}
    int u=(1&(val>>k));
    if(!s[rt].ch[u])s[rt].ch[u]=++Cnt;
    Insert(s[rt].ch[u],val,k-1,id);
    Push_Up(rt);
}
long long query(int rt,int x){
    long long ret=0;
    for(int i=s[rt].dep;i>=0;i--){
        int u=((x>>i)&1);
        if(s[rt].ch[u])rt=s[rt].ch[u];
        else ret+=(1<<i),rt=s[rt].ch[!u];
    }
    return ret;
}
long long DFS(int rt){
    long long ret=0;
    if(s[rt].ch[0])ret+=DFS(s[rt].ch[0]);
    if(s[rt].ch[1])ret+=DFS(s[rt].ch[1]);
    if(s[rt].ch[0]&&s[rt].ch[1]){
        long long tmp=INF;
        int ls=s[rt].ch[0],rs=s[rt].ch[1];
        for(int i=s[ls].L;i<=s[ls].R;i++)
            tmp=min(tmp,query(rs,A[i]));
        ret+=tmp+(1<<s[rt].dep);
    }
    return ret;
}
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
        scanf("%d",&A[i]);
    sort(A+1,A+N+1);
    for(int i=1;i<=N;i++)
        Insert(0,A[i],30,i);
    printf("%lld\n",DFS(0));
}

【CF888G】Xor-MST(生成树 Trie)

原文：https://www.cnblogs.com/ftotl/p/11788892.html