Hướng giải của Tìm Chu Kỳ

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: Tìm Chu Kỳ

Phân tích bài toán

Cho một đồ thị hàm số, nhiệm vụ của chúng ta là tìm điểm đầu tiên lọt vào chu kỳ, chiều dài chu kỳ và khoảng cách từ điểm xuất phát \(U\) tới chu kỳ.

  1. Tìm một nút nằm trong chu kỳ: Xuất phát từ \(U\), đi liên tiếp đúng \(N\) bước chắc chắn ta sẽ lọt vào chu kỳ. Gọi nút này là cycle_node. Ta tìm cycle_node trong \(O(\log N)\) bằng cách nhảy nhị phân \(N\) bước từ \(U\).
  2. Tìm chiều dài chu kỳ cycle_length: Từ cycle_node, ta đi từng bước kế tiếp cho tới khi quay lại đúng cycle_node. Số bước đi chính là chiều dài chu kỳ \(L\).
  3. Tìm khoảng cách và điểm vào chu kỳ (entry_node): Ta nhận thấy: một nút \(V\) đã nằm trong chu kỳ nếu và chỉ nếu sau khi đi tiếp \(L\) bước, ta quay trở lại đúng \(V\). Ta có thể thực hiện tìm kiếm nhị phân số bước nhảy tối thiểu từ \(U\) bằng Binary Lifting:
    • Thử nhảy nhị phân từ đỉnh hiện tại \(curr\) một lượng \(2^j\) bước.
    • Nếu đỉnh mới đạt được chưa lọt vào chu kỳ (tức là đi tiếp \(L\) bước nữa từ đỉnh mới không quay về chính nó), ta thực hiện nhảy và cộng \(2^j\) vào khoảng cách.
    • Ngược lại, ta giữ nguyên vị trí và thử các bit nhỏ hơn.
    • Cuối cùng, đỉnh láng giềng kế tiếp (up[curr][0]) sẽ là đỉnh vào chu kỳ và khoảng cách là dist + 1.
Độ phức tạp
  • Thời gian: \(O(N \log N)\) tiền xử lý, và \(O(\log^2 N)\) mỗi truy vấn (do gọi hàm kiểm tra tính thuộc chu kỳ trong vòng lặp nhị phân).
  • Không gian: \(O(N \log N)\) bộ nhớ.
Mã nguồn C++ mẫu
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q;
    if (!(cin >> n >> q)) return 0;
    int LOG = 20;
    vector<vector<int>> up(n, vector<int>(LOG));
    for (int i = 0; i < n; i++) cin >> up[i][0];
    for (int j = 1; j < LOG; j++) {
        for (int i = 0; i < n; i++) {
            up[i][j] = up[up[i][j - 1]][j - 1];
        }
    }

    auto get_k_successor = [&](int node, int k) {
        for (int j = 0; j < LOG; j++) {
            if (k & (1 << j)) {
                node = up[node][j];
            }
        }
        return node;
    };

    while (q--) {
        int u;
        cin >> u;
        int cycle_node = get_k_successor(u, n);

        int len_node = up[cycle_node][0];
        int len = 1;
        while (len_node != cycle_node) {
            len_node = up[len_node][0];
            len++;
        }

        int dist = 0;
        int curr = u;
        if (get_k_successor(curr, len) != curr) {
            for (int j = LOG - 1; j >= 0; j--) {
                int next_node = up[curr][j];
                if (get_k_successor(next_node, len) != next_node) {
                    curr = next_node;
                    dist += (1 << j);
                }
            }
            curr = up[curr][0];
            dist += 1;
        }

        cout << curr << " " << len << " " << dist << "\n";
    }
    return 0;
}

Nhận xét

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