题目描述
若有 $k$ 个点，第 $i$ 个点的权值为 $b_i$ ，点权互不相同，那么 $i$ 会和 $j$ 连边当与 $b_i$ 异或值最小的值为 $b_j$ 。
现在有 $n$ 个点，求删掉最少的点使得最终的图，去掉重边后是棵树。
数据范围
$n \le 2 \times 10^5,a_i \le 10^9$
题解
一张图有 $n$ 条边，其中肯定会有最小值的数对，也就是最多有 $n-1$ 条边，若要删点说明这张图没有联通。
这张图什么时候没有联通？我们考虑最高有效位，若 $0$ 的个数和 $1$ 的个数都 $\ge 2$ ，则这张图不会联通，因为 $0$ 的内部会自己连， $1$ 的内部会自己连，因此要让一边的个数降至最多一个，另一边接着往下删点，这可以递归实现。
效率 $O(nlogMax(a_i))$
代码
#include<bits/stdc++.h> using namespace std; const int N=2e5+5; int n,a[N]; int solve(int k,int l,int r){ if (k==1) return 0; int mid=l; for (;mid<=r;mid++) if (k&a[mid]) break; if (mid==l || mid>r) return solve(k>>1,l,r); if (mid==l+1) return solve(k>>1,l+1,r); if (mid==r) return solve(k>>1,l,r-1); return min(solve(k>>1,l,mid-1)+r-mid,solve(k>>1,mid,r)+mid-1-l); } int main(){ scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+n+1); printf("%d\n",solve(1<<30,1,n)); return 0; }
原文：https://www.cnblogs.com/xjqxjq/p/15070845.html