题目描述

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

输入格式
第一行输入一个整数 N。

第二行输入 N 个整数 A1～AN。

输出格式
输出一个整数表示答案。

数据范围
1≤N≤105,
0≤Ai<2^31

样例

输入样例：
3
1 2 3
输出样例：
3

算法1

Trie树

python 代码

def insert(x):
    global idx
    p=0
    for i in range(31,-1,-1):
        if son[p][x>>i&1]==0:
            idx+=1
            son[p][x>>i&1]=idx
        p=son[p][x>>i&1]

def query(x):
    res=0
    p=0
    for i in range(31,-1,-1):
        s=x>>i&1
        if son[p][1-s]:         #s是0,1-s是1，s是1，1-s是0
            res+=1<<i
            p=son[p][1-s]
        else:
            p=son[p][s]
    return res


if __name__ == "__main__":
    idx=0
    N = 3000010         #10万个数，每个数31位
    son = [[0]*2 for _ in range(N)]
    n = int(input())
    a = list(map(int,input().split()))
    for i in range(n):
        insert(a[i])
    res=0
    for i in range(n):
        res = max(res,query(a[i]))
    print(res)