Đắp đường (Đề tự luyện HSG Tin 9 – Bài 2)
Đề bài
Đắp đường. Con đường gồm $N$ đoạn, đoạn $i$ cần được rải ít nhất $d_i$ lớp đất; đoạn có $d_i = -1$ là cống (không cần đắp, không được rải lên). Mỗi lượt rải phủ đúng $L$ đoạn liên tiếp (nằm trọn trong đường, không đi qua cống), mỗi đoạn được thêm một lớp. Tính số lượt rải ít nhất để mọi đoạn đủ lớp, hoặc in $-1$ nếu không thể.
Dữ liệu vào: dòng 1 gồm $N, L$ $(1 \le L \le N \le 2 \cdot 10^5)$; dòng 2 gồm $d_1, \dots, d_N$ $(-1 \le d_i \le 10^9)$.
Kết quả: số lượt rải ít nhất, hoặc $-1$.
- Subtask 1 (20%): $N \le 100$ và $d_i \le 100$.
- Subtask 2 (30%): $N \le 5000$.
- Subtask 3 (50%): không ràng buộc thêm.
10 3
0 2 0 0 0 -1 4 1 4 39Đoạn 6 là cống, $L = 3$. Rải 2 lượt phủ đoạn 2–4, 4 lượt phủ đoạn 7–9, 3 lượt phủ đoạn 8–10: mọi đoạn đều đủ, tổng $9$ lượt, không có cách ít hơn.
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 Đắp đườngLời mở đầu
Gọi một lượt rải "bắt đầu tại $s$" nếu nó phủ các đoạn $s, s+1, \dots, s+L-1$. Vị trí bắt đầu $s$ là hợp lệ khi $1 \le s \le N - L + 1$ và $L$ đoạn đó không có cống.
Hãy nhìn vào đoạn chưa đủ lớp nằm bên trái nhất, gọi là đoạn $i$. Mọi lượt rải phủ được đoạn $i$ đều bắt đầu ở một vị trí $s$ trong khoảng $[i - L + 1,\ i]$. Các đoạn bên trái $i$ đều đã đủ lớp rồi, nên phần lượt rải "lấn" sang bên trái $i$ là phí. Vì vậy ta nên chọn $s$ càng về bên phải càng tốt: lượt rải đó vẫn phủ đoạn $i$ và phủ được xa nhất sang phải, giúp được nhiều đoạn phía sau nhất. Đây là một lập luận "đổi chỗ" quen thuộc: trong một cách rải tối ưu bất kỳ, thay một lượt bắt đầu ở $s$ bằng lượt bắt đầu ở $s^* \ge s$ thì không đoạn nào từ $i$ trở đi bị thiếu đi lớp nào.
Hình 1. Tham lam: lấp đoạn chưa đủ trái nhất bằng các lượt rải bắt đầu ở vị trí hợp lệ bên phải nhất.
Nếu trong khoảng $[i - L + 1,\ \min(i, N - L + 1)]$ không có vị trí hợp lệ nào thì đoạn $i$ không bao giờ được phủ: in $-1$. Khi đã chọn được vị trí $s$, ta phải rải đủ luôn số lớp còn thiếu của đoạn $i$ ở vị trí đó (thiếu bao nhiêu thì rải bấy nhiêu lượt), rồi chuyển sang đoạn tiếp theo.
Cách 1Mỗi lần rải đúng một lượt – O(ΣD · (N + L²)) · 20%
Làm đúng như lập luận ở trên nhưng "thật thà": lặp lại việc tìm đoạn chưa đủ trái nhất, tìm vị trí bắt đầu hợp lệ bên phải nhất (thử lùi dần từ $\min(i, N-L+1)$, mỗi vị trí kiểm tra $L$ đoạn xem có cống không), rồi rải một lượt (cộng $1$ vào $L$ ô của mảng phu). Số lượt rải tối đa $100 \cdot 100 = 10^4$, mỗi lượt tốn cỡ $N + L^2 \le 10^4$ phép: vừa đủ cho Subtask 1.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, L;
cin >> n >> L;
vector<long long> d(n + 1), phu(n + 1, 0); // phu[i] = so lop dat da rai len doan i
for (int i = 1; i <= n; i++) cin >> d[i];
long long ans = 0;
while (true) {
int i = 1; // tim doan chua du lop dau tien (tu trai sang)
while (i <= n && (d[i] == -1 || phu[i] >= d[i])) i++;
if (i > n) break; // moi doan deu du
int s = -1; // tim vi tri bat dau xa nhat ve ben phai ma van phu doan i
for (int t = min(i, n - L + 1); t >= max(1, i - L + 1); t--) {
bool ok = true;
for (int j = t; j < t + L; j++) if (d[j] == -1) ok = false;
if (ok) { s = t; break; }
}
if (s == -1) { cout << -1 << "\n"; return 0; }
for (int j = s; j < s + L; j++) phu[j]++; // rai MOT lop
ans++;
}
cout << ans << "\n";
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n, L = int(data[0]), int(data[1])
d = [0] + [int(x) for x in data[2:2 + n]]
phu = [0] * (n + 1) # phu[i] = so lop dat da rai len doan i
ans = 0
while True:
i = 1 # tim doan chua du lop dau tien (tu trai sang)
while i <= n and (d[i] == -1 or phu[i] >= d[i]):
i += 1
if i > n:
break # moi doan deu du
s = -1 # tim vi tri bat dau xa nhat ve ben phai ma van phu doan i
for t in range(min(i, n - L + 1), max(1, i - L + 1) - 1, -1):
if all(d[j] != -1 for j in range(t, t + L)):
s = t
break
if s == -1:
print(-1)
return
for j in range(s, s + L): # rai MOT lop
phu[j] += 1
ans += 1
print(ans)
main()Cách 2Rải cả loạt một lần – O(N · L) · 50%
Duyệt $i$ từ trái sang phải. Nếu đoạn $i$ còn thiếu $can = d_i - \text{phu}_i > 0$ lớp thì tìm vị trí $s$ hợp lệ bên phải nhất, cộng $can$ vào phu[s..s+L-1] và cộng $can$ vào đáp án. Để kiểm tra "$L$ đoạn từ $s$ không có cống" trong $O(1)$, dùng mảng đếm cống cộng dồn: cong[i] = số cống trong các đoạn $1..i$; đoạn $[s, s+L-1]$ không có cống khi cong[s+L-1] - cong[s-1] == 0. Mỗi đoạn $i$ tốn $O(L)$ để tìm $s$ và $O(L)$ để cộng.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, L;
cin >> n >> L;
vector<long long> d(n + 1), phu(n + 1, 0); // phu[i] = so lop dat da rai len doan i
vector<int> cong(n + 1, 0); // cong[i] = so cong trong cac doan 1..i
for (int i = 1; i <= n; i++) {
cin >> d[i];
cong[i] = cong[i - 1] + (d[i] == -1);
}
long long ans = 0;
for (int i = 1; i <= n; i++) {
if (d[i] == -1 || phu[i] >= d[i]) continue;
long long can = d[i] - phu[i]; // rai mot lan "can" lop
int s = -1;
for (int t = min(i, n - L + 1); t >= max(1, i - L + 1); t--)
if (cong[t + L - 1] - cong[t - 1] == 0) { s = t; break; }
if (s == -1) { cout << -1 << "\n"; return 0; }
for (int j = s; j < s + L; j++) phu[j] += can;
ans += can;
}
cout << ans << "\n";
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, L = int(data[0]), int(data[1])
d = [0] * (n + 1)
cong = [0] * (n + 1) # cong[i] = so cong trong cac doan 1..i
for i in range(1, n + 1):
d[i] = int(data[1 + i])
cong[i] = cong[i - 1] + (1 if d[i] == -1 else 0)
phu = [0] * (n + 1) # phu[i] = so lop dat da rai len doan i
ans = 0
for i in range(1, n + 1):
if d[i] == -1 or phu[i] >= d[i]:
continue
can = d[i] - phu[i] # rai mot lan "can" lop
s = -1
for t in range(min(i, n - L + 1), max(1, i - L + 1) - 1, -1):
if cong[t + L - 1] == cong[t - 1]:
s = t
break
if s == -1:
print(-1)
return
for j in range(s, s + L):
phu[j] += can
ans += can
print(ans)
main()Cách 3Mảng hiệu + vị trí hợp lệ gần nhất – O(N) · 100%
Thứ nhất – cộng cả đoạn trong O(1) bằng mảng hiệu. Ta chỉ cần biết số lớp đang phủ đoạn hiện tại $i$ (biến cur), vì ta đi từ trái sang phải. Khi rải $can$ lượt bắt đầu ở $s \le i$, các đoạn từ $i$ đến $s + L - 1$ được thêm $can$ lớp: tăng ngay cur += can, và ghi nhớ "đến đoạn $s + L$ thì $can$ lớp này hết tác dụng" bằng giam[s + L] += can. Đến mỗi đoạn $i$ mới, trừ cur -= giam[i].
Thứ hai – tìm vị trí hợp lệ bên phải nhất trong O(1). Tính trước mảng last[x] = vị trí bắt đầu hợp lệ lớn nhất $\le x$ (bằng $0$ nếu không có): last[s] = s nếu $s$ hợp lệ, ngược lại last[s] = last[s - 1]. Khi xét đoạn $i$, lấy $s$ = last[min(i, N - L + 1)]; nếu $s = 0$ hoặc $s + L - 1 < i$ (lượt rải không với tới đoạn $i$) thì in $-1$.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, L;
cin >> n >> L;
vector<long long> d(n + 1);
vector<int> cong(n + 1, 0); // cong[i] = so cong trong cac doan 1..i
for (int i = 1; i <= n; i++) {
cin >> d[i];
cong[i] = cong[i - 1] + (d[i] == -1);
}
int m = n - L + 1; // cac luot rai chi bat dau tu 1 den m
vector<int> last(m + 1, 0); // last[x] = vi tri bat dau hop le lon nhat <= x (0 neu khong co)
for (int s = 1; s <= m; s++) {
bool ok = (cong[s + L - 1] - cong[s - 1] == 0); // L doan tu s khong co cong
last[s] = ok ? s : last[s - 1];
}
vector<long long> giam(n + 2, 0); // mang hieu: giam[j] = so lop het tac dung tu doan j
long long cur = 0, ans = 0; // cur = so lop dang phu doan i
for (int i = 1; i <= n; i++) {
cur -= giam[i];
if (d[i] == -1 || cur >= d[i]) continue;
long long can = d[i] - cur; // con thieu bao nhieu lop
int s = last[min(i, m)]; // bat dau cang ve ben phai cang tot
if (s == 0 || s + L - 1 < i) { // khong luot rai hop le nao phu duoc doan i
cout << -1 << "\n";
return 0;
}
ans += can;
cur += can;
giam[s + L] += can;
}
cout << ans << "\n";
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); L = int(data[1])
d = [0] * (n + 1)
cong = [0] * (n + 1) # cong[i] = so cong trong cac doan 1..i
for i in range(1, n + 1):
v = int(data[1 + i])
d[i] = v
cong[i] = cong[i - 1] + (1 if v == -1 else 0)
m = n - L + 1 # cac luot rai chi bat dau tu 1 den m
last = [0] * (m + 1) # last[x] = vi tri bat dau hop le lon nhat <= x (0 neu khong co)
for s in range(1, m + 1):
last[s] = s if cong[s + L - 1] == cong[s - 1] else last[s - 1]
giam = [0] * (n + 2) # mang hieu: giam[j] = so lop het tac dung tu doan j
cur = 0; ans = 0 # cur = so lop dang phu doan i
for i in range(1, n + 1):
cur -= giam[i]
di = d[i]
if di == -1 or cur >= di:
continue
can = di - cur # con thieu bao nhieu lop
s = last[i if i < m else m] # bat dau cang ve ben phai cang tot
if s == 0 or s + L - 1 < i: # khong luot rai hop le nao phu duoc doan i
print(-1)
return
ans += can
cur += can
giam[s + L] += can
print(ans)
main()long long. (2) Thấy $L$ đoạn bắt đầu tại $\min(i, N-L+1)$ có cống là in $-1$ ngay, quên rằng có thể lùi về trái tìm vị trí hợp lệ khác vẫn phủ được đoạn $i$. (3) Cho lượt rải ở cuối đường bị "cắt cụt" (bắt đầu sau $N - L + 1$): sai khi có cống nằm trong $L - 1$ đoạn cuối — đề bắt mỗi lượt phải nằm trọn trong đường. (4) Chọn vị trí bắt đầu bên trái nhất (lượt rải kết thúc đúng tại $i$): phí phần lấn sang trái.Bộ test chấm "bắt" những lỗi nào?
Bộ test có 30 test: Subtask 1 có 10 test ($N \le 100$, $d_i \le 100$: ví dụ, $N = 1$, chỉ có một cống, toàn số $0$, $L = N$, hai test không thể làm được), Subtask 2 có 9 test ($N \approx 5000$, $d_i$ tới $10^9$, $L$ từ $1$ đến gần $N$, nhiều cống, đáp án tới cỡ $3,6 \cdot 10^{12}$), Subtask 3 có 11 test ($N \approx 2 \cdot 10^5$, $L$ từ $9 \cdot 10^4$ đến $1,2 \cdot 10^5$, độ sâu tăng dần dọc con đường nên gần như đoạn nào cũng phải rải thêm). Có các test "cống nằm trong $L - 1$ đoạn cuối", "hai cống sát nhau mà giữa cần đắp" (đáp án $-1$) và nhiều đoạn cần đắp nằm ngay trước cống. Điểm tính theo từng test (thang 100%).
| Cách làm | Sub 1 (10 test) | Sub 2 (9 test) | Sub 3 (11 test) | Điểm |
|---|---|---|---|---|
| Cách 1 – Rải từng lượt một | Đúng 10/10 | TLE 0/9 | TLE 0/11 | 20 |
| Cách 2 – Rải cả loạt, cộng từng ô | Đúng 10/10 | Đúng 9/9 | TLE 0/11 | 50 |
| Cách 3 – Mảng hiệu (chuẩn) | Đúng 10/10 | Đúng 9/9 | Đúng 11/11 | 100 |
Sai: đếm số lượt bằng int | Đúng 10/10 | WA 4/9 | WA 7/11 | 65,2 |
| Sai: cho lượt rải cuối đường bị cắt cụt | WA 9/10 | WA 7/9 | WA 8/11 | 77,7 |
| Sai: gặp cống là in $-1$, không lùi về trái | WA 7/10 | WA 5/9 | WA 6/11 | 57,9 |
| Sai: chọn vị trí bắt đầu bên trái nhất | WA 7/10 | WA 5/9 | WA 4/11 | 48,8 |
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 10/10 test Subtask 1 và quá thời gian (hơn 3 giây) ở toàn bộ 20 test còn lại; Cách 2 đúng 19/19 test của hai subtask đầu và quá thời gian cả 11 test Subtask 3 (có test cần tới gần 9 giây); Cách 3 đúng 30/30 test, test lâu nhất chạy khoảng 0,02 giây. Lời giải Python của Cách 3 cũng đúng 30/30 test, chạy tối đa khoảng 0,2 giây với CPython. Ví dụ của đề khá "hiền": đáp án nhỏ, không có cống ở cuối đường, không có đoạn cần đắp nằm sát trước cống — nên cả bốn lời giải sai ở bảng trên đều vẫn ra đúng $9$. 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