The XOR Largest Pair

刷刷书上的例题

在给定的N个整数A1，A2……An中选出两个进行XOR运算，得到的结果最大是多少？N<=10⁵，0<=Ai<2³¹

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=;

int trie[N][],tot,n,a[N];

il int gi()

{

    int a=;char x=getchar();bool f=;

    while((x<''||x>'')&&x!='-')x=getchar();

    if(x=='-')x=getchar(),f=;

    while(x>=''&&x<='')a=a*+x-,x=getchar();

    return f?-a:a;

}

il void insert(int x)

{

    int p=;

    for(int k=;k>=;k--){

        int c=(x>>k)&;

        if(!trie[p][c])trie[p][c]=++tot;

        p=trie[p][c];

    }

}

il int getans(int x)

{

    int p=,v=,ans=;

    for(int k=;k>=;k--){

        int c=(x>>k)&,o=c?:;

        if(trie[v][o])v=trie[v][o],ans=(ans<<)|;

        else v=trie[v][c],ans<<=;

        p=trie[p][c];

    }

    return ans;

}

int main()

{

    n=gi();

    int ans=;

    for(int i=;i<=n;i++)a[i]=gi(),insert(a[i]);

    for(int i=;i<=n;i++){

        ans=max(ans,getans(a[i]));

    }

    printf("%d\n",ans);

    return ;

}

巴特西

The XOR Largest Pair

最新文章

热门文章