题解归档 - cf888G

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf888G
• 本地来源：problems/cf888G/idea.md
• 题目链接：https://codeforces.com/contest/888/problem/G
• 原始标题：cf888G — Xor-MST

思路

cf888G — Xor-MST

题意

完全图，点权 a[i]，边 (i,j) 权为 a[i] xor a[j]。求最小生成树权值和。n≤2×10^5，a[i]<2^30。

做法

按二进制位从高到低递归分治：

1. 按当前位 b 将集合拆成 bit b = 0 与 bit b = 1 两组。
2. 若仅一组非空，该位不产生跨边代价，递归更低位。
3. 若两组都非空，必须在 MST 中至少连一条跨组边；用 01 Trie 在一组中插入、对另一组每个数查询 最小 xor，取最小跨边权 w。
4. 答案为 w + solve(零组, b-1) + solve(一组, b-1)。

正确性：任意 MST 在最高不同位上必有一条跨组边；取最小跨边后，两组内部最优连接独立。Trie 单次 O(log A)，总复杂度 O(n log A)。

实现注意

• 递归子问题必须用局部 vector 保存分组（或显式拷贝），不能用会被下层递归 clear() 的全局分组数组。
• Trie 节点池 ptr 单调递增、每次新建根，不复用旧根下未清零的子指针。

结论

Educational Round 32 G，经典「xor 权完全图 MST」+ 按位分治 + 01 Trie 最小 xor。与 lib/数据结构(字典树).cpp 同源技巧。

代码

来源：problems/cf888G/solution.cpp

/* Author: likely
 * Time: 2026-06-08 03:44:15
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=200005,maxt=6200005,wd=30,inf=1e18;
ll s[maxn+5],ch[maxt+5][2],ptr,rt,cur,pd,bit,i,j,k,n,ans;
vector<ll>v;
ll mn_xor(const vector<ll>&za,const vector<ll>&zb){
    rt=++ptr;
    ch[rt][0]=ch[rt][1]=0;
    for(i=0;i<(ll)za.size();i++){
        cur=rt;
        for(pd=wd;pd>=0;pd--){
            bit=(za[i]>>pd)&1;
            if(!ch[cur][bit]){
                ch[cur][bit]=++ptr;
                ch[ptr][0]=ch[ptr][1]=0;
            }
            cur=ch[cur][bit];
        }
    }
    ans=inf;
    for(i=0;i<(ll)zb.size();i++){
        cur=rt;
        ll zc=0;
        for(pd=wd;pd>=0;pd--){
            bit=(zb[i]>>pd)&1;
            if(ch[cur][bit]) cur=ch[cur][bit];
            else{
                cur=ch[cur][bit^1];
                zc|=(1ll<<pd);
            }
        }
        ans=min(ans,zc);
    }
    return ans;
}
ll dfs(vector<ll>vv,ll bit){
    if(vv.size()<=1) return 0;
    if(bit<0) return 0;
    vector<ll>za,zb;
    for(i=0;i<(ll)vv.size();i++){
        if(vv[i]&(1ll<<bit)) zb.push_back(vv[i]);
        else za.push_back(vv[i]);
    }
    if(za.empty()) return dfs(zb,bit-1);
    if(zb.empty()) return dfs(za,bit-1);
    ll w=mn_xor(za,zb);
    return w+dfs(za,bit-1)+dfs(zb,bit-1);
}
int main(){
    cin>>n;
    v.clear();
    ptr=0;
    for(i=1;i<=n;i++){
        cin>>s[i];
        v.push_back(s[i]);
    }
    if(n<=1){
        cout<<"0\n";
        return 0;
    }
    cout<<dfs(v,wd)<<"\n";
    return 0;
}