Hướng giải của Phủ Đoạ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: Phủ Đoạn

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

Yêu cầu tìm số đoạn thẳng ít nhất để phủ kín đoạn \([A, B]\).

  1. Để phủ từ \(A\) đi xa nhất có thể, ta luôn chọn đoạn thẳng bắt đầu trước hoặc tại vị trí hiện tại và có đầu mút phải lớn nhất có thể.
    • Định nghĩa best_right[x] là tọa độ xa nhất về bên phải có thể đạt tới bằng 1 đoạn thẳng bắt đầu trước hoặc tại \(x\).
    • Ta tính best_right[x] cho mọi \(x\) bằng cách khởi tạo best_right[L_i] = max(best_right[L_i], R_i) và quét dồn max từ trái qua phải best_right[x] = max(best_right[x], best_right[x-1]) trong thời gian \(O(M)\) với \(M = 10^6\).
  2. Xây dựng bảng Binary Lifting up[x][j] đại diện cho tọa độ xa nhất đạt được sau khi chọn \(2^j\) đoạn thẳng tối ưu bắt đầu từ \(x\).
  3. Với mỗi truy vấn \([A, B]\):
    • Sử dụng nhảy nhị phân từ \(A\) để đi xa nhất có thể nhưng dừng lại ngay trước khi vượt qua hoặc bằng \(B\).
    • Đi thêm 1 bước cuối cùng để vượt qua \(B\).
    • Nếu tọa độ đạt được không \(\ge B\) hoặc không di chuyển được chút nào, in ra -1.
Độ phức tạp
  • Thời gian: \(O(M \log N)\) tiền xử lý với \(M = 10^6\), và \(O(\log N)\) mỗi truy vấn.
  • Không gian: \(O(M \log N)\) bộ nhớ.
Mã nguồn C++ mẫu
#include <bits/stdc++.h>
using namespace std;

const int MAXC = 1000005;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q;
    if (!(cin >> n >> q)) return 0;

    vector<int> best_right(MAXC);
    for (int i = 0; i < MAXC; i++) best_right[i] = i;

    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        best_right[l] = max(best_right[l], r);
    }

    for (int i = 1; i < MAXC; i++) {
        best_right[i] = max(best_right[i], best_right[i - 1]);
    }

    int LOG = 21;
    vector<vector<int>> up(MAXC, vector<int>(LOG));
    for (int i = 0; i < MAXC; i++) {
        up[i][0] = best_right[i];
    }
    for (int j = 1; j < LOG; j++) {
        for (int i = 0; i < MAXC; i++) {
            up[i][j] = up[up[i][j - 1]][j - 1];
        }
    }

    while (q--) {
        int a, b;
        cin >> a >> b;
        if (a >= b) {
            cout << 0 << "\n";
            continue;
        }
        int curr = a;
        int steps = 0;
        for (int j = LOG - 1; j >= 0; j--) {
            if (up[curr][j] < b) {
                steps += (1 << j);
                curr = up[curr][j];
            }
        }
        curr = up[curr][0];
        steps += 1;
        if (curr >= b && curr > a) {
            cout << steps << "\n";
        } else {
            cout << -1 << "\n";
        }
    }
    return 0;
}

Nhận xét

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