怎么用微信做网站,全国私人订制平台,最超值的赣州网站建设,wordpress文章密码插件题目截图 题目分析
排序后#xff0c;限定了x和y的相对位置 假设y x#xff0c;随着y的移动#xff0c;必须要保证2x y 所以可以使用滑动窗口维护一堆满足条件的x 这些x的异或值记录在Trie树中即可
ac code
class Node:__slots__ children, cntdef __init__(s…题目截图 题目分析
排序后限定了x和y的相对位置 假设y x随着y的移动必须要保证2x y 所以可以使用滑动窗口维护一堆满足条件的x 这些x的异或值记录在Trie树中即可
ac code
class Node:__slots__ children, cntdef __init__(self):self.children [None, None]self.cnt 0 # 子树大小class Trie:HIGH_BIT 19def __init__(self):self.root Node()# 添加 valdef insert(self, val: int) - None:cur self.rootfor i in range(Trie.HIGH_BIT, -1, -1):bit (val i) 1if cur.children[bit] is None:cur.children[bit] Node()cur cur.children[bit]cur.cnt 1 # 维护子树大小return cur# 删除 val但不删除节点# 要求 val 必须在 trie 中def remove(self, val: int) - None:cur self.rootfor i in range(Trie.HIGH_BIT, -1, -1):cur cur.children[(val i) 1]cur.cnt - 1 # 维护子树大小return cur# 返回 val 与 trie 中一个元素的最大异或和# 要求 trie 中至少有一个元素def max_xor(self, val: int) - int:cur self.rootans 0for i in range(Trie.HIGH_BIT, -1, -1):bit (val i) 1# 如果 cur.children[bit^1].cnt 0视作空节点if cur.children[bit ^ 1] and cur.children[bit ^ 1].cnt:ans | 1 ibit ^ 1cur cur.children[bit]return ansclass Solution:def maximumStrongPairXor(self, nums: List[int]) - int:nums.sort()t Trie()ans left 0for y in nums:t.insert(y)# 只考虑nums[left] * 2 y否则滑走while nums[left] * 2 y:t.remove(nums[left])left 1ans max(ans, t.max_xor(y))return ans
01Trie树模版
class Node:__slots__ children, cntdef __init__(self):self.children [None, None]self.cnt 0 # 子树大小class Trie:HIGH_BIT 19def __init__(self):self.root Node()# 添加 valdef insert(self, val: int) - None:cur self.rootfor i in range(Trie.HIGH_BIT, -1, -1):bit (val i) 1if cur.children[bit] is None:cur.children[bit] Node()cur cur.children[bit]cur.cnt 1 # 维护子树大小return cur# 删除 val但不删除节点# 要求 val 必须在 trie 中def remove(self, val: int) - None:cur self.rootfor i in range(Trie.HIGH_BIT, -1, -1):cur cur.children[(val i) 1]cur.cnt - 1 # 维护子树大小return cur# 返回 val 与 trie 中一个元素的最大异或和# 要求 trie 中至少有一个元素def max_xor(self, val: int) - int:cur self.rootans 0for i in range(Trie.HIGH_BIT, -1, -1):bit (val i) 1# 如果 cur.children[bit^1].cnt 0视作空节点if cur.children[bit ^ 1] and cur.children[bit ^ 1].cnt:ans | 1 ibit ^ 1cur cur.children[bit]return ans细节
__slot__加速
