Codeforces 888G(分治+trie)

时间:2023-03-08 23:41:00
Codeforces 888G(分治+trie)

  按位贪心,以当前考虑位是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!!!!!
}