描述

在给定的N个整数A1，A2……AN中选出两个进行xor运算，得到的结果最大是多少？

输入格式

第一行一个整数N，第二行N个整数A1～AN。

输出格式

一个整数表示答案。

样例输入

3

1 2 3

样例输出

数据范围与约定

对于100%的数据: N<=\(10^5\), 0<=Ai<\(2^{31}\).

题解

看到\(A_i\)最大为\(2^{31}\)很容易想到把数字拆成一个一个数位存进字典树,而为了异或值最大,我们可以想到一个贪心,在求一个数字\(A_i\)与另一个数字\(A_j\)最大异或值时,我们要尽量让它们对应数位上的数字不同,即0对1,1对0.

那么在trie树检索的时候,我们就可以尽量往与当前位相反的指针上跑,如果没有就只能走原来的数位,根据xor运算相同得0,不同为1的运算法则,这样是可以得到两个数异或的最大值的

然后在存进数字的时候,我们要倒着存,这要方便后续的检索中更新答案

综上所述,我们可以循环i=1~n,对于每个i,前面必定已经有i-1个数字插入进了trie树,我们每次将答案与检索得到的答案取个最小值就可以了

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#define Min(a,b) (a)<(b)?(a):(b)

#define Max(a,b) (a)>(b)?(a):(b)

#define in(i) (i=read())

using namespace std;

int read() {

    int ans=0,f=1; char i=getchar();

    while(i<'0' || i>'9') {if(i=='-') f=-1; i=getchar();}

    while(i>='0' && i<='9') {ans=(ans<<1)+(ans<<3)+i-'0'; i=getchar();}

    return ans*f;

}

int n,m,tot,ans;

int trie[4000010][2],cnt[4000010];

void insert(int x) {

    int p=0;

    for(int i=31;i>=0;i--) {

        int c=(x>>i)&1;

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

        p=trie[p][c];

    }

}

int search(int x) {

    int p=0,ans=0;

    for(int i=31;i>=0;i--) {

        int c=(x>>i)&1,o=c^1;

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

        else p=trie[p][c],ans<<=1;

    }

    return ans;

}

int main()

{

    in(n);

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

        int x; in(x);

        ans=Max(ans,search(x));

        insert(x);

    }

    cout<<ans<<endl;

    return 0;

}

巴特西

The XOR Largest Pair [Trie]

描述

输入格式

输出格式

样例输入

样例输出

数据范围与约定

题解

博主蒟蒻,随意转载.但必须附上原文链接

http://www.cnblogs.com/real-l/

最新文章

热门文章