题目描述:
思路:
1、首先此题我们要知道异或的规则,这里不赘述了,可以百度
2、如果利用trie树去找到一个数字与其异或能得到最大值
比如二进制数:1010.....是一个很大的数
我们想要异或得到的值更大,就需要让异或的值,最好去找与其相反的数
比如 1010.....最高位是1我当然找到0与其异或是比较好的,况且还在最高位如果异或
是1的话就很好,假如没找到0的话,那只能和1将就一下。
3、为了避免边界情况,少写一个判断,所以我们先插入后查找,不会影响最后结果的
因为本身异或是0
图解:
如图:
第一个数是5,我们先进行插入操作,101,插入进去
第二个数是6,依然先插入后找最大异或对象,此树中目前只有5和6本身,根据上面规则,
6的二进制是110,最高位是1我们想找一个0与其匹配最好,但是5的二进制是101,第一位是1,加上trie树中没有最高位0与其匹配所以只能勉强,和1匹配后是1,再依次按照规则,继续,6异或5是3(011-->二进制数)
第三个数是3(011-->二进制),依旧先插入,最高位是0,所以我们要去找1与其匹配,trie树中有1,所以继续,第二位是1,最好情况是找到0与其匹配, 同样0我们也找到了,继续第三位是1,我们还想找0,但是trie树中好像没有0与其匹配,我们只好将就一下找1吧~,所以3与其匹配的二进制数是101-->5,3^5--->110(6)
第四个数是4(100-->二进制),先插入,最高位是1,我们可以找0与其匹配的,我们可以找到0,此0来源于3的二进制011中的最高位0,第二位是0我们就要找1与其匹配,1也同样有,继续往下走,第三位也是0,同样要找1,还是有,所以4^3--->7(111)
第五个数是7(111-->二进制),先插入,最高位是 1,我们还是找到0与其匹配,然后按照规则走下去,7^3--->4(100)
通过上述图解和例子,我们可以看出5 6 3 4 7这组数的最大异或对是4 和 3 -----> 7(111)
AC代码:
#include<iostream>
using namespace std;
//解释一下M为啥是31*N,因为根据数据范围,一个数小于2^31-->一个数31位,N个数
//就是31*N
const int N = 1e5+10, M = 31*N;
int a[N];
int son[M][2];
int idx;
void insert(int x)
{
int p = 0;
for(int i=30;i>=0;i--)
{
//右移动大最大的位置,看下当前位置是1还是0
int u = x >> i & 1;
//如果没有创建一个节点存一下
if(!son[p][u]) son[p][u] = ++idx;
p = son[p][u];//指向下一个节点
}
}
int query(int x)
{
int p = 0;
int res = 0;
for(int i=30;i>=0;i--)
{
int u = x >> i & 1;
if(son[p][!u])
{
p = son[p][!u];
//这里等价于十进制中的 n = n * 10 + x;
//八进制的话就是n = n * 8 + x;
res = res * 2 + !u;
}
else
{
p = son[p][u];
res = res * 2 + u;
}
}
}
int main()
{
int n;
scanf("%d", &n);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
int res = 0;
for(int i=0;i<n;i++)
{
insert(a[i]); //插入
int t = query(a[i]); //查找最合适的那个他
res = max(res,a[i]^t); //找出最大值
}
printf("%d",res);
return 0;
}
如果有错误,欢迎大家指正~