Hướng giải của Cặp XOR Nhỏ Nhất

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Hướng dẫn giải

Bài toán tìm cặp số phân biệt có XOR nhỏ nhất. Nhận xét quan trọng: Cặp số có XOR nhỏ nhất trong một tập hợp sau khi được sắp xếp tăng dần sẽ là cặp số đứng cạnh nhau. Do đó, ta sắp xếp mảng tăng dần trước, sau đó chèn các số lần lượt vào Bitwise Trie. Khi chèn số \(A[i]\), ta tìm số có XOR nhỏ nhất với \(A[i]\) trong Trie (các số đã chèn \(A[0 \dots i-1]\)). Ở mỗi bit, ta ưu tiên đi theo nhánh cùng bit với \(A[i]\) để XOR tại vị trí đó bằng \(0\). Nếu không có, ta buộc phải đi nhánh ngược lại.

Độ phức tạp thời gian: \(O(N \log N + 31 \times N)\) cho việc sắp xếp và duyệt Trie.

Mã nguồn C++ mẫu

#include <bits/stdc++.h>
using namespace std;

struct Node {
    Node* children[2];
    Node() { children[0] = children[1] = nullptr; }
};

struct Trie {
    Node* root;
    Trie() { root = new Node(); }

    void insert(int n) {
        Node* cur = root;
        for (int i = 30; i >= 0; i--) {
            int bit = (n >> i) & 1;
            if (cur->children[bit] == nullptr) {
                cur->children[bit] = new Node();
            }
            cur = cur->children[bit];
        }
    }

    int getMinXor(int n) {
        Node* cur = root;
        int ans = 0;
        for (int i = 30; i >= 0; i--) {
            int bit = (n >> i) & 1;
            if (cur->children[bit] != nullptr) {
                cur = cur->children[bit];
            } else {
                ans |= (1 << i);
                cur = cur->children[1 - bit];
            }
        }
        return ans;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    sort(a.begin(), a.end());
    Trie trie;
    int ans = 2e9 + 7;
    for (int i = 0; i < n; i++) {
        if (i > 0) {
            ans = min(ans, trie.getMinXor(a[i]));
        }
        trie.insert(a[i]);
    }
    cout << ans << "\n";
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.