异或最大值

1216: 异或最大值

http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1216

Time Limit: 2 Sec Memory Limit: 128 Mb

Description

给定一些数，求这些数中两个数的异或值最大的那个值

Input

多组数据。第一行为数字个数n，1 <= n <= 10 ^ 5。接下来n行每行一个32位有符号非负整数。

Output

任意两数最大异或值

Sample Input

3
3
7
9

Sample Output

14

Hint

Source
CSGrandeur的数据结构习题

思路：

暴力\(N^2\)铁定超时

贪心一下

xor 即不同为1，相同为0

如果一个数a去找能得到最大异或值的b

（我也搞不清楚哪里是最高位了，就把最右边当第一位吧）

则二进制较高位不同的数字一定比他们二进制较高位相同的异或值大

比如有三个数 10 6 8

10的二进制是1010

6的二进制是0101

8的二进制是1000

则和10异或值最大的就是6(第4位比较）

贪心好了

下面就该实现了

二进制无非就0和1

要快速查找，就可以建一个01字典树

比如这样

cmd-markdown-logo

当范围大到int也最多有30层时间复杂度\(nlogn\)

ps:与(&)和或(|)的最大值也是可以求的,博客.

考试居然忘了输出\n了，我TM真的是，╮(╯▽╰)╭ 哎

实现的话，sturct记录左孩子（1）右孩子（0）的位置

从大到小一层层遍历就好了，实现也没辣么难

附上又臭又长的代码

/*
                       ▍ ★∴
　　．．．．▍▍．..．█▍ ☆ ★∵ ..../ 
　　◥█▅▅██▅▅██▅▅▅▅▅███◤ 
 　 ．◥███████████████◤
～～～～◥█████████████◤～～～～
*/
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

inline int read()
{
    int x=0,f=1;char s=getchar();
    while('0'>s||s>'9') {if(s=='-')f=-1;s=getchar();}
    while('0'<=s&&s<='9') {x=x*10+s-'0';s=getchar();}
    return x*f;
}

int n;
int a[100007];

inline int max(int a,int b) {return a>b?a:b;}

struct node{
    int a,b;
}e[100007*20];
int tot=1;

inline void build(int x)
{
    int p=1;
    for(int i=30;i>=0;i--) {
        int tmp=x&(1<<i);
        if(tmp)
            if(!e[p].a)
                e[p].a=++tot,p=tot;
            else p=e[p].a;
        else
            if(!e[p].b) e[p].b=++tot,p=tot;
            else p=e[p].b;
    }
}

inline int query(int x)
{
    int p=1;
    int ans=0;
    for(int i=30;i>=0;i--) {
        int tmp=x&(1<<i);
        if(!tmp) {
            if(e[p].a) p=e[p].a,ans+=(1<<i);
            else p=e[p].b;
        }
        else {
            if(e[p].b)  p=e[p].b;
            else p=e[p].a,ans+=(1<<i);
        }
    }
    return ans^x;
}

int main()
{
    while(scanf("%d",&n)==1) {
        memset(e,0,sizeof(e));
        int ans=-0x3f3f3f3f;
        for(int i=1;i<=n;++i)
            a[i]=read(); 
        for(int i=1;i<=n;++i)
            build(a[i]);
        for(int i=1;i<=n;++i)
            ans=max(ans,query(a[i]));
        printf("%d\n",ans); 
    }
    return 0;
}