题目链接：传送门
题目思路：
对于异或最小值，可以根据贪心的思想，对于 ai 的二进制表示，从高位向低位枚举，去寻找 j 使得 ai ^ aj 最小化。
可以考虑构建一颗01字典树，叶子节点表示值ai，在同一棵子树下（有公共前缀）肯定优先匹配，公共前缀越长肯定优先级越高。对于字典树上 一个点 的两棵不同子树，如果其叶子个数均大于1，这两棵子树各自的ai就会相互匹配，导致形成多个连通块，为保证最后能够形成树形结构（只有一个连通块），因此就需要选择左子树 或者 右子树 将其所有的叶子节点 删到 至多只剩1个 ， 这样就不存在 一棵子树上的点相互连接 导致形成多个连通块的情况。
代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 typedef unsigned long long uLL; 5 typedef pair<int,int> pii; 6 typedef pair<LL,LL> pLL; 7 typedef pair<double,double> pdd; 8 const int N=2e5+5; 9 const int M=1e7+5; 10 const int inf=0x3f3f3f3f; 11 const LL mod=1e9+7; 12 const double eps=1e-8; 13 const long double pi=acos(-1.0L); 14 #define ls (i<<1) 15 #define rs (i<<1|1) 16 #define fi first 17 #define se second 18 #define pb push_back 19 #define eb emplace_back 20 #define mk make_pair 21 #define mem(a,b) memset(a,b,sizeof(a)) 22 LL read() 23 { 24 LL x=0,t=1; 25 char ch; 26 while(!isdigit(ch=getchar())) if(ch=='-') t=-1; 27 while(isdigit(ch)){ x=10*x+ch-'0'; ch=getchar(); } 28 return x*t; 29 } 30 int bt[N<<5][2],a[N],cnt=1; 31 void ins(int x) 32 { 33 int p=1; 34 for(int i=29;i>=0;i--) 35 { 36 int t=((1<<i)&x)>0; 37 if(!bt[p][t]) bt[p][t]=++cnt; 38 p=bt[p][t]; 39 } 40 } 41 int dfs(int u) 42 { 43 if(!bt[u][0]&&!bt[u][1]) return 1; // 叶子节点 44 int t0=0,t1=0; 45 if(bt[u][0]) t0=dfs(bt[u][0]); 46 if(bt[u][1]) t1=dfs(bt[u][1]); 47 if(t0&&t1) return max(t0,t1)+1; 48 else return t1+t0;//t0=0 返回t1 , t1=0 返回t0 49 } 50 int main() 51 { 52 int n=read(); 53 for(int i=1;i<=n;i++) a[i]=read(); 54 for(int i=1;i<=n;i++) ins(a[i]); 55 printf("%d ",n-dfs(1)); 56 return 0; 57 } 58 /* 59 4 60 1 2 3 4 61 */