Hướng dẫn giải của [2526 VTT THPT KS2] Bài 2: Sơn hàng rào [FENCEPNT]
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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
Đếm số đoạn cọc liên tiếp cần sơn (các đoạn chạm hoặc chồng nhau được gộp thành một) và số cọc có chỉ số chia hết cho K trong các đoạn đó.
Sub 1: Đánh dấu từng cọc — ~O(R)~, dùng khi ~T \le 500~ và ~R \le 10000~
Dùng mảng đánh dấu cho từng cọc từ 1 đến R. Duyệt mảng: mỗi lần gặp cọc được đánh dấu mà cọc trước không được đánh dấu thì tăng số đoạn; cọc được đánh dấu và chia hết cho K thì tăng số cọc sơn.
Chưa đo riêng sub này.
Sub 2: Sắp xếp và gộp đoạn — ~O(T \log T)~
Sắp xếp các đoạn theo L. Gộp đoạn mới vào đoạn hiện tại nếu ~L \le R_{cũ}+1~ (không có cọc trống giữa). Mỗi đoạn gộp ~[a,b]~ có ~\lfloor b/K \rfloor - \lfloor (a-1)/K \rfloor~ cọc chia hết cho K. Giá trị R lên tới ~10^9~ nên dùng số nguyên 64 bit.
Chương trình hoàn chỉnh
Chương trình đọc dữ liệu, dữ liệu nhỏ (~T \le 500~, ~R \le 10000~) gọi sub1, dữ liệu lớn gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int T, K;
vector<pair<long long, long long>> seg; // cac doan [L, R]
long long maxR = 0;
// Sub 1: danh dau tung coc, dem doan lien tiep va so coc chia het cho K
// Dung khi T <= 500 va R <= 10000
void sub1() {
vector<int> mark(10005, 0);
for (auto &p : seg)
for (long long x = p.first; x <= p.second; x++) mark[x] = 1;
long long cnt = 0, plant = 0;
for (int x = 1; x <= 10000; x++) {
if (mark[x] && !mark[x - 1]) cnt++; // bat dau mot doan moi
if (mark[x] && x % K == 0) plant++;
}
cout << cnt << " " << plant << "\n";
}
// Sub 2: sap xep, gop cac doan chong/cham nhau, moi doan gop dem so chia het cho K bang cong thuc
void sub2() {
sort(seg.begin(), seg.end());
long long cnt = 0, plant = 0;
long long curL = -1, curR = -2;
bool has = false;
for (auto &p : seg) {
if (!has) { curL = p.first; curR = p.second; has = true; continue; }
if (p.first <= curR + 1) { // cham hoac chong: cung mot doan
curR = max(curR, p.second);
} else {
cnt++;
plant += curR / K - (curL - 1) / K;
curL = p.first; curR = p.second;
}
}
if (has) {
cnt++;
plant += curR / K - (curL - 1) / K;
}
cout << cnt << " " << plant << "\n";
}
int main() {
freopen("FENCEPNT.INP", "r", stdin);
freopen("FENCEPNT.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> T >> K;
seg.resize(T);
for (int i = 0; i < T; i++) {
cin >> seg[i].first >> seg[i].second;
maxR = max(maxR, seg[i].second);
}
if (T <= 500 && maxR <= 10000) sub1();
else sub2();
return 0;
}
Bình luận