E. Xor Tree
1.题意
给你n个数,n个数的权值,然后它们连边的规则是每个数连向它们异或最小的边.然后问你最少删掉多少个数,才能使得它们构成一棵树?
2.思路
对于位运算,我们应该从高位向低位进行.既然是从高位向低位进行,那么思考一下,假如那个高位有两个1,两个0,它们会如何连边.必定是1与1相连,0与0相连,所以考虑每一位,假如我选取1的话,这位为0的点就只能保留一个,假如我这位选0的话,这位的1的点就只能保留一个.所以直接dfs在字典树上跑就好了...maybe?
3.代码
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+50;
int son[2][N*100],id;
int cnt[N*100];
void insert(int x)
{
int p=0;
for(int i=29;i;i--)
{
int pos=(x>>i&1);//这位是1还是0.
int &s=son[pos][p];
if(!s) s=++id;
p=s;
}cnt[p]++;
}
int query(int u)//查询当前层最多保留的值的数量.
{
int l=son[0][u];int r=son[1][u];
if(l&&r) return cnt[u]+max(query(l),query(r))+1;
else if(l) return cnt[u]+query(l);
else if(r) return cnt[u]+query(r);
else return cnt[u];
}
int main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
insert(x);
}
int ans=n-query(0);
cout<<ans<<endl;
return 0;
}
lpt的小屋 文章被收录于专栏
我想要一份甜甜的爱情
