Hướng giải của Cặp XOR Giới Hạn

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 đếm số lượng cặp \((i, j)\) sao cho \(A[i] \oplus A[j] < K\). Ta sử dụng Bitwise Trie. Mỗi node của Trie lưu số lượng phần tử đi qua node đó (count). Khi duyệt qua phần tử \(A[j]\) (với các phần tử \(A[i]\) đã chèn trước đó vào Trie), ta đếm số lượng số trong Trie có XOR với \(A[j]\) nhỏ hơn \(K\):

Tại bit thứ i từ cao xuống thấp:

Nếu bit thứ i của \(K\) là \(1\):
- Nhánh đi theo hướng cùng bit với \(A[j]\) sẽ tạo ra kết quả XOR có bit thứ i bằng \(0\), luôn nhỏ hơn bit \(1\) của \(K\). Do đó, toàn bộ số lượng phần tử thuộc nhánh này đều thỏa mãn \(\Rightarrow\) ta cộng count của nhánh này vào kết quả.
- Sau đó, ta tiếp tục đi sâu xuống nhánh ngược bit với \(A[j]\) để tìm thêm các khả năng khác.
Nếu bit thứ i của \(K\) là \(0\):
- Ta buộc phải đi theo nhánh cùng bit với \(A[j]\) để kết quả XOR có bit thứ i bằng \(0\) (bằng với \(K\)). Nếu nhánh này không tồn tại, ta dừng lại.

Độ phức tạp thời gian: \(O(31 \times N)\).

Mã nguồn C++ mẫu

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

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

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];
            cur->count++;
        }
    }

    int countLessXor(int n, int k) {
        Node* cur = root;
        int ans = 0;
        for (int i = 30; i >= 0; i--) {
            if (!cur) break;
            int bit = (n >> i) & 1;
            int k_bit = (k >> i) & 1;
            if (k_bit == 1) {
                if (cur->children[bit] != nullptr) {
                    ans += cur->children[bit]->count;
                }
                cur = cur->children[1 - bit];
            } else {
                cur = cur->children[bit];
            }
        }
        return ans;
    }
};

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

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

    vector<int> a(n);
    Trie trie;
    long long total = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (i > 0) {
            total += trie.countLessXor(a[i], k);
        }
        trie.insert(a[i]);
    }
    cout << total << "\n";
    return 0;
}

Nhận xét

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