Hướng dẫn giải của [VTT Q4 Contest 03] Bài 4: Phủ đoạn thẳng [COVER]
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Chọn ít đoạn nhất sao cho hợp của chúng phủ kín ~[a, b]~ (hai đoạn chạm đầu mút vẫn tính là liền nhau). Nếu không thể phủ thì in ~-1~. Đây là bài tham lam kinh điển.
Sub 1: Duyệt mọi tập con — ~O(2^n \cdot n^2)~, dùng khi ~n \le 15~
Thử mọi tập con các đoạn, kiểm tra tập đó có phủ kín ~[a, b]~ không bằng cách đi từ ~a~ và nới dần bằng các đoạn bắt đầu không quá vị trí hiện tại. Lấy tập có ít đoạn nhất. Máy chấm thật chấp nhận mọi phương án có cùng số đoạn, còn lệnh chấm cục bộ so từng chữ nên sub này có thể bị tính sai ở vài test do khác phương án; nếu chỉ nộp sub này: đúng 2/40 test theo lệnh chấm cục bộ.
Sub 2: Tham lam — ~O(n \log n)~
Sắp xếp các đoạn theo đầu mút trái. Đang phủ tới vị trí ~cur~ (ban đầu bằng ~a~), trong các đoạn có đầu trái ~\le cur~ chọn đoạn có đầu phải lớn nhất, rồi đặt ~cur~ bằng đầu phải đó. Lặp đến khi ~cur \ge b~. Nếu không có đoạn nào làm ~cur~ tăng thì in ~-1~. Chú ý trường hợp ~a = b~ vẫn cần ít nhất một đoạn chứa điểm đó. Cuối cùng in các chỉ số theo thứ tự tăng dần. Đúng 40/40 test.
Chương trình hoàn chỉnh
Main đọc dữ liệu; ~n \le 15~ gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
int n, A, B;
int l[100005], r[100005];
// Kiểm tra tập đoạn (theo mask) có phủ kín [A, B] không: đi từ trái, mở rộng bằng các đoạn bắt đầu <= cur
static bool covers(const vector<int> &ids) {
long long cur = A;
bool moved = true;
while (moved && cur < B) {
moved = false;
for (int x : ids)
if (l[x] <= cur && r[x] > cur) { cur = r[x]; moved = true; }
}
return cur >= B;
}
// Sub 1: duyệt mọi tập con, lấy tập ít đoạn nhất phủ được — O(2^n * n^2), dùng khi n <= 15
void sub1() {
int bestK = INT_MAX;
vector<int> best;
for (int mask = (1 << n) - 1; mask >= 1; mask--) {
int k = __builtin_popcount(mask);
if (k >= bestK) continue;
vector<int> ids;
for (int i = 0; i < n; i++) if (mask >> i & 1) ids.push_back(i + 1);
if (covers(ids)) { bestK = k; best = ids; }
}
if (bestK == INT_MAX) { cout << -1 << "\n"; return; }
cout << bestK << "\n";
for (int x : best) cout << x << "\n";
}
// Sub 2: tham lam — O(n log n). Đang phủ đến cur, chọn trong các đoạn có l <= cur đoạn có r lớn nhất.
void sub2() {
vector<int> ord(n);
iota(ord.begin(), ord.end(), 1);
sort(ord.begin(), ord.end(), [&](int x, int y) { return l[x] < l[y]; });
vector<int> chosen;
long long cur = A;
size_t p = 0;
bool first = true;
int keep = -1; // đoạn có r lớn nhất trong các đoạn đã thấy (l <= cur)
while (cur < B || first) {
first = false;
int bi = -1;
while (p < ord.size() && l[ord[p]] <= cur) {
if (r[ord[p]] >= cur && (bi == -1 || r[ord[p]] > r[bi])) bi = ord[p];
p++;
}
if (bi != -1 && (keep == -1 || r[bi] > r[keep])) keep = bi;
if (keep == -1 || r[keep] < cur || (r[keep] == cur && cur < B)) { cout << -1 << "\n"; return; }
chosen.push_back(keep);
cur = r[keep];
keep = -1;
}
sort(chosen.begin(), chosen.end());
cout << chosen.size() << "\n";
for (int x : chosen) cout << x << "\n";
}
int main() {
freopen("COVER.INP", "r", stdin);
freopen("COVER.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> A >> B;
for (int i = 1; i <= n; i++) cin >> l[i] >> r[i];
if (n <= 15) sub1();
else sub2();
}
Bình luận