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;
}