题解 CF1446C 【Xor Tree】
xukuan
2020-11-23 21:57:12
根据套路，这种题应该用字典树来做
满足的条件是存在且只存在一对$(i,j)$，$a_i \space xor \space a_j$的值对双方都是最小的
那么询问的时候，
$$
query(p)=\begin{aligned}
1,lson_p=empty,rson_p=empty\\
query(lson_p),lson_p \neq empty,rson_p=empty\\
query(rson_p),lson_p=empty,rson_p \neq empty\\
max(query(lson_p),query(rson_p))+1,lson_p \neq empty,rson_p \neq empty\\
\end{aligned}
$$
前三个柿子都不解释，就解释最后一个
我们假设有两个集合：lson和rson，最小的结果就是一个的最优解加上另外里面选1个，这样另外集合xor剩下的当前为都是1，所以一定不影响结果
代码：
```cpp
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const ll N=200010;
ll n,cnt=1,tree[N*20][2],root=1;
inline ll read(){
ll x=0,tmp=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') tmp=-1;
ch=getchar();
}
while(isdigit(ch)){
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return tmp*x;
}
inline void Insert(ll val){
ll p=root;
for(ll i=30; i>=0; i--){
ll x=(val>>i)&1;
if(!tree[p][x]) tree[p][x]=++cnt;
p=tree[p][x];
}
}
ll query(ll p){
if(!tree[p][0]&&!tree[p][1]) return 1;
if(!tree[p][0]) return query(tree[p][1]);
if(!tree[p][1]) return query(tree[p][0]);
return max(query(tree[p][0]),query(tree[p][1]))+1;
}
int main(){
n=read();
for(ll i=1; i<=n; i++) Insert(read());
cout<<n-query(root)<<endl;
return 0;
}
```