按位贪心,以当前考虑位是0还是1将数分成两部分,则MST中这两部分之间只会存在一条边,因为一旦有两条或以上的边,考虑两条边在原图中所成的环,显然这两条边有一条是环上的权值最大边,不会出现在MST中。则建出trie后每次分治时用数较少的部分在trie上贪心求出边的最小权值即可。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long #define N 200010 #define inf (1<<30) char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } int n,a[N],trie[N<<5][2],size[N<<5],val[N<<5],cnt; ll ans; void ins(int x,int i) { int k=0;size[k]++; for (int j=30;~j;j--) { if (!trie[k][(x&(1<<j))>0]) trie[k][(x&(1<<j))>0]=++cnt; k=trie[k][(x&(1<<j))>0];size[k]++; } val[k]=i; } int query(int k,int x,int i) { int s=1<<i; for (int j=i-1;~j;j--) { if (trie[k][(x&(1<<j))>0]) k=trie[k][(x&(1<<j))>0]; else s|=1<<j,k=trie[k][(x&(1<<j))==0]; } return s; } void solve(int l,int r,int k,int x) { if (l>=r||x<0) return; if (!trie[k][0]||!trie[k][1]) {solve(l,r,trie[k][0]|trie[k][1],x-1);return;} int u=inf; if (size[trie[k][0]]<size[trie[k][1]]) { for (int i=l;i<l+size[trie[k][0]];i++) u=min(u,query(trie[k][1],a[i],x)); } else { for (int i=l+size[trie[k][0]];i<=r;i++) u=min(u,query(trie[k][0],a[i],x)); } ans+=u; solve(l,l+size[trie[k][0]]-1,trie[k][0],x-1); solve(l+size[trie[k][0]],r,trie[k][1],x-1); } signed main() { #ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout); #endif n=read(); for (int i=1;i<=n;i++) a[i]=read(); sort(a+1,a+n+1); for (int i=1;i<=n;i++) ins(a[i],i); solve(1,n,0,30); cout<<ans; return 0; //NOTICE LONG LONG!!!!! }