AcWing 143. 最大异或对(python)
原题链接
简单
作者:
柠檬茶去冰
,
2024-12-11 22:51:54
,
所有人可见
,
阅读 1
def insert(x):
global idx
q=0
for i in range(32)[::-1]: #从每个数的第31位为开始
u=x>>i&1 #右移i位看是1还是0,#u存的是树的权
if not Trie[q][u]:
idx+=1
Trie[q][u]=idx
q=Trie[q][u]
def query(x):
q=0
res=0
for i in range(32)[::-1]: #从每个数的第31位为开始
u=x>>i&1 #右移i位看是1还是0,#u存的是树的权
if Trie[q][u^1]: #判断所想要(使其异或是1)的另一个值在树中有没有 例如:如果是1,1^1=0,看Trie[q][0]有没有
res=res*2+1^u #相当于右移1位,即是空出右边一位的值 例如:res=3(011),右移1位res=5(11x)+u,res=11u(u是1或0)
q=Trie[q][1^u]
else:
res=(res<<1)+u #2种方法(<<1 or *2)运行的时间差不多
q=Trie[q][u]
return res
Trie=[[0]*2 for i in range(3000000)]#3000000是指向节点的索引(往下走)的个数
idx=0
n=int(input())
a=list(map(int,input().split()))
res=0
for i in a:
insert(i)
t=query(i)
res=max(res,t^i)
print(res)