Trie
Trie 不仅可以储存和查找字符串集合,还可以储存二进制数。
总的来说,就是Trie的适用范围: 一个节点可以储存明确的个数(a~z个数明确,0和1个数明确等)。
C++ 代码
#include <algorithm>
#include <iostream>
using namespace std;
const int N=1e5+10,M=N*31;
int s[M][2],a[N],idx;
void insert(int n)
{
int p=0;
for(int i=30;i>=0;i--)
{
int u=n>>i&1;
if(!s[p][u]) s[p][u]=++idx;
p=s[p][u];
}
}
int fd(int n)
{
int p=0,res=0;
for(int i=30;i>=0;i--)
{
int u=n>>i&1;
if(s[p][!u])
{
p=s[p][!u];
res=res*2+1;
}
else
{
p=s[p][u];
res*=2;
}
}
return res;
}
int main ()
{
int n;
int res=0;
//scanf("%d",&n);
cin.tie(0);
cin>>n;
for(int i=0;i<n;i++) cin>>a[i],insert(a[i]);
for(int i=0;i<n;i++) res=max(res,fd(a[i]));
cout<<res<<endl;
return 0;
}