143. 最大异或对
摘要
Title: 143. 最大异或对
Tag: Trie
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
143. 最大异或对
-
题意
在给定的 N 个整数 A1，A2……AN 中选出两个进行 xor（异或）运算，得到的结果最大是多少？
-
思路
01Trie模板
注意：- 先插入再查询
- 可以防止刚开始树为空的边界情况
- 省去一半的查询时间
- 核心思路就是，贪心的从高到低去往和自己不同的结点
- 清空Trie树
- 一开始
son[0][0] = son[0][1] = 0 - 每次插入时，最后进行
son[p][0] = son[p][1] = 0
- 一开始
- 先插入再查询
-
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42'''
Author: NEFU AB-IN
Date: 2022-03-01 10:18:29
FilePath: \ACM\Acwing\143.py
LastEditTime: 2022-03-01 10:48:29
'''
N = int(1e5 + 10)
son = [[0] * 2 for _ in range(N * 31)]
val, a, idx = [0] * (N * 31), [0] * N, 0 #val记录以结点p结尾的真实值
def insert(x):
global idx
p = 0
for i in range(30, -1, -1):
u = x >> i & 1
if not son[p][u]:
idx += 1
son[p][u] = idx
p = son[p][u]
val[p] = x
def query(x):
p = 0
for i in range(30, -1, -1):
u = x >> i & 1
if son[p][u ^ 1]:
p = son[p][u ^ 1]
else:
p = son[p][u]
return x ^ val[p]
n = int(input())
a = list(map(int, input().split()))
res = 0
for i in range(n):
insert(a[i])
res = max(res, query(a[i]))
print(res)