Lưới che nắng (Đề tự luyện HSG Tin 9 – Bài 2)
Đề bài
Lưới che nắng. Sân trường là đoạn $[0, D]$. Đã có $N$ tấm lưới che các đoạn $[l_i, r_i]$ (có thể chồng nhau). Thầy Sơn căng thêm một tấm lưới dài $L$ ở đoạn $[x, x + L]$ với $x$ nguyên, $0 \le x \le D - L$. Tìm tổng độ dài lớn nhất của phần sân được ít nhất một tấm lưới che.
Dữ liệu vào: dòng 1 gồm $N, D, L$ $(1 \le N \le 2\cdot 10^5;\ 1 \le L \le D \le 10^9)$; $N$ dòng sau, mỗi dòng $l_i, r_i$ $(0 \le l_i < r_i \le D)$, không nhất thiết theo thứ tự.
Kết quả: tổng độ dài lớn nhất phần sân có bóng mát.
- Subtask 1 (20%): $D \le 1000$.
- Subtask 2 (30%): $N \le 2000$.
- Subtask 3 (50%): không ràng buộc thêm.
4 22 6
15 16
3 7
8 11
17 1915Lưới cũ che $[3,7]$, $[8,11]$, $[15,16]$, $[17,19]$. Căng lưới mới ở $[11, 17]$ thì phần có bóng mát là $[3,7]$ và $[8,19]$, dài $4 + 11 = 15$ mét.
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.
Nộp bài Lưới che nắngLời mở đầu
Tấm lưới mới chỉ có ích ở những chỗ chưa có bóng mát. Vậy đáp án bằng
$$\text{(phần sân đã được che)} + \max_{x}\ \text{(độ dài phần CHƯA che nằm trong } [x, x+L]).$$Nhận xét 1 – Gộp lưới cũ thành các "khe". Các tấm lưới cũ có thể chồng nhau nên không được cộng thẳng $r_i - l_i$. Sắp xếp các tấm theo đầu trái rồi đi từ trái sang, giữ biến cur = điểm xa nhất đã được che. Gặp tấm $[l, r]$ mà $l > cur$ thì đoạn $[cur, l]$ là một khe (chưa che). Cuối cùng nếu $cur < D$ thì $[cur, D]$ cũng là một khe. Đừng quên khe ở đầu sân (trước tấm đầu tiên) và cuối sân!
Nhận xét 2 – Chỉ cần thử vài vị trí $x$. Hãy tưởng tượng trượt tấm lưới mới. Nếu mép trái của nó đang nằm trong một khe mà mép phải nằm dưới lưới cũ, thì dịch sang trái làm lợi thêm (mép trái "ăn" thêm khe, mép phải chỉ bỏ phần đã che). Lập luận tương tự cho các trường hợp khác, ta luôn có thể dịch tấm lưới tới một vị trí tốt nhất mà mép trái trùng đầu một khe, hoặc tấm lưới chạm biên sân ($x = 0$ hay $x = D - L$).
Hình 1. Sau khi gộp, sân chia thành các khối đã che xen kẽ các khe; tấm lưới mới chỉ cần thử đặt bắt đầu ở đầu mỗi khe (hoặc sát hai biên sân).
Cách 1Đánh dấu từng mét – O(N·D + D·L) · 20%
Khi $D \le 1000$, ta chia sân thành $D$ "mét" $[t, t+1]$ và dùng mảng che[t]. Với mỗi tấm lưới cũ, đánh dấu các mét nó che (tấm chồng nhau thì đánh dấu lại cũng không sao — đây là cách "gộp" tự nhiên nhất). Rồi thử mọi $x$ từ $0$ tới $D - L$, đếm số mét chưa che trong $[x, x + L]$ và lấy lớn nhất.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, D, L;
cin >> n >> D >> L;
vector<int> che(D, 0); // che[t] = 1 neu met thu t (doan [t, t+1]) da co bong mat
for (int i = 0; i < n; i++) {
int l, r;
cin >> l >> r;
for (int t = l; t < r; t++) che[t] = 1;
}
int daChe = 0;
for (int t = 0; t < D; t++) daChe += che[t];
int best = 0;
for (int x = 0; x + L <= D; x++) { // thu moi vi tri dat tam luoi moi [x, x + L]
int them = 0; // so met chua che nam trong [x, x + L]
for (int t = x; t < x + L; t++) them += 1 - che[t];
best = max(best, them);
}
cout << daChe + best << '\n';
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, D, L = int(data[0]), int(data[1]), int(data[2])
che = [0] * D # che[t] = 1 neu met thu t (doan [t, t+1]) da co bong mat
for i in range(n):
l, r = int(data[3 + 2 * i]), int(data[4 + 2 * i])
for t in range(l, r):
che[t] = 1
daChe = sum(che)
best = 0
for x in range(D - L + 1): # thu moi vi tri dat tam luoi moi [x, x + L]
them = L - sum(che[x:x + L]) # so met chua che nam trong [x, x + L]
if them > best:
best = them
print(daChe + best)
main()che cần $10^9$ phần tử (4 GB) – vượt xa giới hạn bộ nhớ. Ta phải làm việc với các đầu mút của tấm lưới thay vì từng mét.Cách 2Thử vài vị trí, mỗi lần tính lại hợp các đoạn – O(N² log N) · 50%
Theo Nhận xét 2, chỉ cần thử $x = 0$, $x = D - L$ và $x$ = đầu mỗi khe. Mà đầu mỗi khe luôn là $0$ hoặc mép phải $r_i$ của một tấm lưới cũ, nên ta thử luôn $x = \min(r_i, D - L)$ cho mọi tấm (thừa vài vị trí cũng không sao). Với mỗi $x$, thêm đoạn $[x, x + L]$ vào danh sách, sắp xếp rồi tính độ dài hợp các đoạn: đi từ trái sang, đoạn nào bắt đầu sau điểm xa nhất đang có thì mở "khúc" mới, ngược lại nối dài khúc hiện tại.
| Vị trí thử | Lưới mới | Phần có bóng mát | Độ dài |
|---|---|---|---|
| $x = 0$ | [0, 6] | [0, 7], [8, 11], [15, 16], [17, 19] | 13 |
| $x = D - L = 16$ | [16, 22] | [3, 7], [8, 11], [15, 22] | 14 |
| $x = \min(7, 16) = 7$ | [7, 13] | [3, 13], [15, 16], [17, 19] | 13 |
| $x = \min(11, 16) = 11$ | [11, 17] | [3, 7], [8, 19] | 15 |
| $x = \min(16, 16)$, $\min(19, 16)$ | [16, 22] | (như trên) | 14 |
Có $N + 2$ vị trí, mỗi vị trí sắp xếp và quét $N + 1$ đoạn: với $N = 2000$ chỉ khoảng vài chục triệu phép tính.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
vector<pair<ll, ll>> a;
// do dai hop cua cac tam luoi cu va tam luoi moi [x, x + L]
ll hop(ll x, ll L) {
vector<pair<ll, ll>> b = a;
b.push_back({x, x + L});
sort(b.begin(), b.end());
ll tong = 0, lo = b[0].first, hi = b[0].second;
for (size_t i = 1; i < b.size(); i++) {
if (b[i].first > hi) { tong += hi - lo; lo = b[i].first; hi = b[i].second; } // bat dau doan moi
else hi = max(hi, b[i].second); // noi dai doan dang xet
}
return tong + hi - lo;
}
int main() {
ll D, L;
cin >> n >> D >> L;
a.resize(n);
for (auto &p : a) cin >> p.first >> p.second;
// tam luoi moi chi can thu bat dau o 0, o D - L, hoac ngay mep phai mot tam luoi cu
ll best = max(hop(0, L), hop(D - L, L));
for (int i = 0; i < n; i++)
best = max(best, hop(min(a[i].second, D - L), L));
cout << best << '\n';
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, D, L = int(data[0]), int(data[1]), int(data[2])
a = sorted(zip(map(int, data[3:3 + 2 * n:2]), map(int, data[4:4 + 2 * n:2])))
def hop(x):
# do dai hop cua cac tam luoi cu va tam luoi moi [x, x + L]
tong = 0; lo = -1; hi = -1; them = False
for l, r in a + [(D + 1, D + 1)]:
if not them and x <= l: # chen tam luoi moi dung thu tu (a da sap xep)
them = True
if x > hi: tong += hi - lo; lo, hi = x, x + L
elif x + L > hi: hi = x + L
if l > hi: # bat dau doan moi
tong += hi - lo; lo, hi = l, r
elif r > hi: # noi dai doan dang xet
hi = r
return tong
# tam luoi moi chi can thu bat dau o 0, o D - L, hoac ngay mep phai mot tam luoi cu
best = max(hop(0), hop(D - L))
for l, r in a:
v = hop(min(r, D - L))
if v > best:
best = v
print(best)
main()Cách 3Danh sách khe + tổng tiền tố + tìm nhị phân – O(N log N) · 100%
Ta chỉ gộp một lần, lấy ra danh sách khe $[gs_0, ge_0], [gs_1, ge_1], \dots$ (đã tăng dần). Gọi $P[k]$ là tổng độ dài $k$ khe đầu tiên và
$$F(t) = \text{độ dài phần chưa che trong } [0, t].$$Để tính $F(t)$: tìm số khe bắt đầu $\le t$ (gọi là $k$, dùng upper_bound trên mảng $gs$). Các khe $0..k-2$ nằm trọn bên trái $t$ (góp $P[k-1]$), khe thứ $k-1$ góp phần $[gs_{k-1}, \min(t, ge_{k-1})]$. Khi đó phần chưa che trong $[x, x+L]$ đúng bằng $F(x + L) - F(x)$ — tính trong $O(\log N)$.
Với ví dụ: các khe là $[0,3], [7,8], [11,15], [16,17], [19,22]$, $P = (0, 3, 4, 8, 9, 12)$, phần đã che $= 22 - 12 = 10$. Thử $x = 11$: $F(17) - F(11) = 9 - 4 = 5$, đáp án $10 + 5 = 15$.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> gs, ge, P; // khe thu k la [gs[k], ge[k]]; P[k] = tong do dai k khe dau
// F(t) = tong do dai phan CHUA duoc che trong doan [0, t]
ll F(ll t) {
int k = upper_bound(gs.begin(), gs.end(), t) - gs.begin(); // so khe bat dau <= t
if (k == 0) return 0;
return P[k - 1] + min(t, ge[k - 1]) - gs[k - 1];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
ll D, L;
cin >> n >> D >> L;
vector<pair<ll, ll>> a(n);
for (auto &p : a) cin >> p.first >> p.second;
sort(a.begin(), a.end()); // sap xep theo dau trai
ll cur = 0; // [0, cur] da xet xong
for (auto &p : a) {
if (p.first > cur) { gs.push_back(cur); ge.push_back(p.first); } // khe chua che
cur = max(cur, p.second);
}
if (cur < D) { gs.push_back(cur); ge.push_back(D); }
int m = gs.size();
P.assign(m + 1, 0);
for (int k = 0; k < m; k++) P[k + 1] = P[k] + ge[k] - gs[k];
ll daChe = D - P[m]; // phan san da co bong mat
// thu dat tam luoi moi bat dau o 0, o D - L, hoac o dau moi khe
ll best = F(L) - F(0);
best = max(best, F(D) - F(D - L));
for (int k = 0; k < m; k++) {
ll x = min(gs[k], D - L);
best = max(best, F(x + L) - F(x));
}
cout << daChe + best << '\n';
return 0;
}import sys
from bisect import bisect_right
def main():
data = sys.stdin.buffer.read().split()
n, D, L = int(data[0]), int(data[1]), int(data[2])
a = sorted(zip(map(int, data[3:3 + 2 * n:2]), map(int, data[4:4 + 2 * n:2]))) # sap xep theo dau trai
gs = []; ge = [] # khe thu k la [gs[k], ge[k]]
cur = 0 # [0, cur] da xet xong
for l, r in a:
if l > cur: # khe chua che
gs.append(cur); ge.append(l)
if r > cur:
cur = r
if cur < D:
gs.append(cur); ge.append(D)
m = len(gs)
P = [0] * (m + 1) # P[k] = tong do dai k khe dau
for k in range(m):
P[k + 1] = P[k] + ge[k] - gs[k]
def F(t):
# tong do dai phan CHUA duoc che trong doan [0, t]
k = bisect_right(gs, t)
if k == 0:
return 0
e = ge[k - 1]
return P[k - 1] + (t if t < e else e) - gs[k - 1]
daChe = D - P[m] # phan san da co bong mat
# thu dat tam luoi moi bat dau o 0, o D - L, hoac o dau moi khe
best = max(F(L) - F(0), F(D) - F(D - L))
lim = D - L
for k in range(m):
x = gs[k] if gs[k] < lim else lim
v = F(x + L) - F(x)
if v > best:
best = v
print(daChe + best)
main()Bộ test chấm "bắt" những lỗi nào?
Bộ test có 34 test: Subtask 1 có 12 test ($D \le 1000$; gồm ví dụ, sân được phủ kín, $D = 1$), Subtask 2 có 10 test ($N \approx 2000$ tấm, $D$ tới $5\cdot10^8$), Subtask 3 có 12 test ($N \approx 2\cdot 10^5$). Các tấm lưới luôn bị xáo thứ tự và chồng/lồng nhau nhiều; có các kiểu: một khe rất dài đứng riêng giữa nhiều khe nhỏ, khe đầu/cuối sân là chỗ tốt nhất, hai đầu sân đã che, sân phủ kín. Điểm tính theo từng test (thang 100%).
| Cách làm | Sub 1 (12 test) | Sub 2 (10 test) | Sub 3 (12 test) | Điểm |
|---|---|---|---|---|
| Cách 1 – Đánh dấu từng mét | Đúng 12/12 | RE/TLE 0/10 | RE/TLE 0/12 | 20 |
| Cách 2 – Thử vài vị trí, tính lại hợp | Đúng 12/12 | Đúng 10/10 | TLE 0/12 | 50 |
| Cách 3 – Khe + tổng tiền tố (chuẩn) | Đúng 12/12 | Đúng 10/10 | Đúng 12/12 | 100 |
| Sai: quên khe đầu/cuối sân | WA 9/12 | WA 8/10 | WA 9/12 | 76,5 |
| Sai: đặt lưới mới ở đầu khe dài nhất | WA 11/12 | WA 3/10 | WA 6/12 | 52,3 |
| Sai: lưới mới chỉ che một khe | WA 8/12 | WA 3/10 | WA 5/12 | 43,2 |
| Sai: không gộp, cộng thẳng $r_i - l_i$ | WA 4/12 | WA 0/10 | WA 0/12 | 6,7 |
Ghi chú của mình: các cách C++ ở trên đã được chấm thử với đúng bộ test của bài: Cách 1 đúng 12/12 test Subtask 1 và bị lỗi bộ nhớ hoặc quá thời gian ở toàn bộ 22 test còn lại; Cách 2 đúng 22/22 test của hai subtask đầu và quá thời gian (hơn 3 giây) ở cả 12 test Subtask 3; Cách 3 đúng 34/34 test, test lâu nhất chạy khoảng 0,05 giây. Lời giải Python của Cách 3 cũng đúng 34/34 test, chạy tối đa khoảng 0,6 giây với CPython. Ví dụ của đề khá "hiền": các tấm lưới không chồng nhau và vị trí tốt nhất không dùng khe biên, nên lời giải quên gộp, lời giải quên khe biên và lời giải tham lam khe dài nhất đều vẫn ra đúng $15$ — nhớ tự nghĩ thêm test nha!
Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét