The XOR Largest Pair

LOJ

题意:在给定的\(n\)个整数\(a_1,a_2,...,a_n\)之中选出两个并进行异或运算,得到的最大结果是多少?\(n<=1e5.a_i<2^{31}.\)

把n个数转化成二进制数,看成长度为32的字符串,不足的前面补上0,插入\(Trie\)树中.然后对于每一个数,去\(Trie\)树中查询,尽量沿着相反的边走(即当前这个数的这一位为1,我要优先向0走),这样才能保证异或值最大.

\(ch\)数组要看大点.

本题是这题的弱化版.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=1e7+5;
int tot=1,a[N],ch[N][2];
inline void insert(int x){
    int u=1;
    for(int i=31;i>=0;--i){
        int c=(x&(1<<i))>>i;
        if(!ch[u][c])ch[u][c]=++tot;
        u=ch[u][c];
    }
}
inline int query(int x){
    int u=1,ans=0;
    for(int i=31;i>=0;--i){
        int c=(x&(1<<i))>>i;
        if(ch[u][c^1])ans+=1<<i,u=ch[u][c^1];
        else u=ch[u][c];
    }
    return ans;
}
int main(){
    int n=read(),ans=0;
    for(int i=1;i<=n;++i){
        a[i]=read();
        insert(a[i]);
    }
    for(int i=1;i<=n;++i)
        ans=max(ans,query(a[i]));
    printf("%d\n",ans);
    return 0;
}

The XOR Largest Pair

原文：https://www.cnblogs.com/PPXppx/p/11609930.html