算法(最大异或对)
143. 最大异或对
在给定的 N𝑁 个整数 A1,A2……AN𝐴1,𝐴2……𝐴𝑁 中选出两个进行 xor𝑥𝑜𝑟(异或)运算,得到的结果最大是多少?
输入格式
第一行输入一个整数 N𝑁。
第二行输入 N𝑁 个整数 A1𝐴1~AN𝐴𝑁。
输出格式
输出一个整数表示答案。
数据范围
1≤N≤1051≤𝑁≤105,
思路:
暴力的做法是对于第i个输入的数,分别于前i-1个数异或,得到一个最大值,然后用当前的最大值和ans比较大小,更大的给ans。当i从0到n走一遍以后完成求解,所用时间是o(N*N)。
优化的地方是内层的循环,即每次第i个数不用和前i-1个数都比较一遍,而是可以利用tire树找出其中能得到当前最大异或对的解,具体原理是对于已经存入tire树的前i-1个数,用到大到小遍历第i个数的二进制每一位,看tire数对于当前位,有无相反的那个数(1就是找0,0就是找1),若存在,则最大的异或一定是在这个分支上(因为高位大的一定大),若不存在,则只能选择相同的数,然后继续看下一位,重复上述过程。
注意idx是先加一,再去赋值,要把第0位空出来。开始用++idx出错了,因为若开头位数是0放下标位0的位置,相当于没动。
#include<iostream>
#include<cstring>
using namespace std;
const int N=3000100;
int e[N][2];
int idx;
int n;
void insert(int x)
{
int p=0;
for(int i=30;i>=0;i--)
{
int t=x>>i&1;
if(!e[p][t])e[p][t]=++idx;
p=e[p][t];
}
}
int serch(int x)
{
int ans=0;
int p=0;
for(int i=30;i>=0;i--)
{
int t=x>>i&1;
if(e[p][!t])
{
ans=ans*2+1;
p=e[p][!t];
}
else
{
p=e[p][t];
ans*=2;
}
}
return ans;
}
int main()
{
scanf("%d",&n);
int ans=0;
while(n--)
{
int a;
scanf("%d",&a);
insert(a);
ans=max(ans,serch(a));
}
printf("%d\n",ans);
return 0;
}