Chương trình tìm phần tử ≤ limit cho XOR lớn nhất với x trong Python

Cho mảng nums và các truy vấn [x, limit]. Với mỗi truy vấn, tìm e trong nums sao cho e <= limit và e XOR x lớn nhất. Không có → -1.

Ví dụ: nums=[3,5,9], queries=[[4,6],[2,0]] → [3, -1].

Giải thuật (Trie nhị phân + Xử lý truy vấn offline theo limit)

1. Sắp xếp nums tăng dần.
2. Sắp xếp truy vấn theo limit tăng dần, giữ chỉ số gốc.
3. Duyệt truy vấn: chèn vào Trie các nums[j] <= limit (con trỏ j chỉ tiến).
4. Truy vấn Trie để tìm số cho XOR max: ưu tiên bit ngược với x.

Ví dụ minh họa

class Solution:
    def solve(self, A, queries):
        trie = {}
        def bits(x):
            return map(int, bin(x)[2:].zfill(32))
        def insert(x):
            node = trie
            for b in bits(x):
                node = node.setdefault(b, {})
            node[2] = x  # lưu giá trị tại lá
        def query(x):
            node = trie
            for b in bits(x):
                want = b ^ 1
                node = node.get(want, node.get(b))
            return node[2]
        
        A.sort()
        B = sorted([(i, x, lim) for i, (x, lim) in enumerate(queries)], key=lambda x: x[2])
        j, n, ans = 0, len(A), [-1] * len(queries)
        for i, x, lim in B:
            while j < n and A[j] <= lim:
                insert(A[j])
                j += 1
            if j > 0:
                ans[i] = query(x)
        return ans

ob = Solution()
nums = [3, 5, 9]
queries = [[4, 6], [2, 0]]
print(ob.solve(nums, queries))  # Output: [3, -1]

Đầu vào / Đầu ra

Input: [3, 5, 9], [[4, 6], [2, 0]]

Output: [3, -1]