刷刷书上的例题
在给定的N个整数A1,A2……An中选出两个进行XOR运算,得到的结果最大是多少?N<=105,0<=Ai<231
SOlution:
我们思考到对于两个数相异或,是先将两数转为二进制数,然后比较同一位上不同为1否则为0,然后观察题目发现每个数的二进制不会超过31位,那么容易想到直接将每个数转为31位二进制存储(不足的补0),于是可以构建一颗Trie树。然后考虑对于每一个数,都在数列中找到一个数使其相异或值最大,我们将查询的这个数也转为31位二进制,贪心的想到从后往前扫,尽量使同一位上的数不同,实在没有节点时就走相同的,若没有节点了就用当前的异或值与ans比较,枚举n个数的情况。最后输出ans就OK了。
代码:
#include<bits/stdc++.h>
#define il inline
#define ll long long
using namespace std;
const int N=400005;
int trie[N][32],tot,n,a[N];
il int gi()
{
int a=0;char x=getchar();bool f=0;
while((x<'0'||x>'9')&&x!='-')x=getchar();
if(x=='-')x=getchar(),f=1;
while(x>='0'&&x<='9')a=a*10+x-48,x=getchar();
return f?-a:a;
}
il void insert(int x)
{
int p=0;
for(int k=30;k>=0;k--){
int c=(x>>k)&1;
if(!trie[p][c])trie[p][c]=++tot;
p=trie[p][c];
}
}
il int getans(int x)
{
int p=0,v=0,ans=0;
for(int k=30;k>=0;k--){
int c=(x>>k)&1,o=c?0:1;
if(trie[v][o])v=trie[v][o],ans=(ans<<1)|1;
else v=trie[v][c],ans<<=1;
p=trie[p][c];
}
return ans;
}
int main()
{
n=gi();
int ans=0;
for(int i=1;i<=n;i++)a[i]=gi(),insert(a[i]);
for(int i=1;i<=n;i++){
ans=max(ans,getans(a[i]));
}
printf("%d\n",ans);
return 0;
}
原文链接: https://www.cnblogs.com/five20/p/8521640.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/272915
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!