Bãi bồi (Đề tự luyện HSG Tin 9 – Bài 3)
Đề bài
Bãi bồi. Dải bãi bồi gồm $N$ ô liên tiếp, ô $i$ có độ cao $h_i$. Khi mực nước là $w$, ô có $h_i > w$ là ô khô, ô có $h_i \le w$ bị ngập. Một doi đất là một dãy ô khô liên tiếp không kéo dài thêm được (hai bên đều là ô ngập hoặc hết dải). Với mỗi mực nước $w_1, \dots, w_Q$ (không theo thứ tự), đếm số doi đất.
Dữ liệu vào: dòng 1 là $N$ $(N \le 2\cdot 10^5)$; dòng 2 là $h_1, \dots, h_N$ $(0 \le h_i \le 10^9)$; dòng 3 là $Q$ $(Q \le 2\cdot 10^5)$; dòng 4 là $w_1, \dots, w_Q$ $(0 \le w_k \le 10^9)$.
Kết quả: $Q$ dòng, dòng $k$ là số doi đất khi mực nước là $w_k$.
- Subtask 1 (20%): $N \le 1000$ và $Q \le 1000$.
- Subtask 2 (30%): $h_i \le 10^6$ với mọi $i$.
- Subtask 3 (50%): không ràng buộc thêm.
10
1 5 3 8 9 1 6 3 6 0
4
2 4 7 102
4
1
0Mực nước $2$: khô các ô $2..5$ và $7..9$ → 2 doi. Mực nước $4$: khô các ô $2$; $4, 5$; $7$; $9$ → 4 doi. Mực nước $7$: chỉ còn ô $4, 5$ → 1 doi. Mực nước $10$: ngập hết → 0.
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 Bãi bồiLời mở đầu
Với một mực nước, đếm số doi đất rất dễ: đi từ trái sang phải, mỗi lần gặp một ô khô mà ô bên trái nó bị ngập (hoặc nó là ô đầu tiên) thì đó là chỗ bắt đầu một doi mới. Cái khó là có tới $2\cdot 10^5$ mực nước trên dải $2\cdot 10^5$ ô — làm lại từ đầu cho mỗi mực nước là $4\cdot 10^{10}$ phép so sánh, quá chậm.
Nhận xét then chốt. Nhìn một doi gồm $L$ ô khô liên tiếp: nó có $L$ ô và đúng $L - 1$ cặp ô kề nhau cùng khô (cặp $(i, i+1)$ nằm bên trong doi). Lấy số ô trừ số cặp thì mỗi doi đóng góp đúng $L - (L - 1) = 1$. Cộng tất cả các doi lại:
số doi $=$ (số ô khô) $-$ (số cặp ô kề nhau cùng khô).
Mà cặp $(i, i+1)$ cùng khô khi và chỉ khi cả hai ô đều cao hơn $w$, tức là $\min(h_i, h_{i+1}) > w$. Đặt $cap_i = \min(h_i, h_{i+1})$ thì bài toán trở thành: đếm trong mảng $h$ có bao nhiêu số lớn hơn $w$, trong mảng $cap$ có bao nhiêu số lớn hơn $w$, rồi lấy hiệu. Không còn phải quan tâm đến vị trí các ô nữa!
Hình 1. Ví dụ của đề với mực nước 2: mỗi doi có số ô hơn số cặp ô kề nhau cùng khô đúng 1, nên số doi = 7 − 5 = 2.
Cách 1Đếm trực tiếp cho mỗi mực nước – O(N · Q) · 20%
Với mỗi mực nước $w$, duyệt các ô từ trái sang phải. Ô $i$ là ô đầu của một doi khi nó khô ($h_i > w$) và: hoặc $i$ là ô đầu tiên của dải, hoặc ô bên trái bị ngập ($h_{i-1} \le w$). Số doi chính là số ô đầu doi. Với $N, Q \le 1000$ chỉ khoảng $10^6$ phép so sánh.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> h(n);
for (int i = 0; i < n; i++) cin >> h[i];
int q;
cin >> q;
for (int k = 0; k < q; k++) {
int w;
cin >> w;
int soDoi = 0;
for (int i = 0; i < n; i++)
// o i kho va (o i la o dau tien hoac o ben trai bi ngap): mot doi dat moi bat dau
if (h[i] > w && (i == 0 || h[i - 1] <= w)) soDoi++;
cout << soDoi << '\n';
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
h = list(map(int, data[1:1 + n]))
q = int(data[1 + n])
out = []
for k in range(2 + n, 2 + n + q):
w = int(data[k])
soDoi = 0
for i in range(n):
# o i kho va (o i la o dau tien hoac o ben trai bi ngap): mot doi dat moi bat dau
if h[i] > w and (i == 0 or h[i - 1] <= w):
soDoi += 1
out.append(soDoi)
sys.stdout.write("\n".join(map(str, out)) + "\n")
main()Cách 2Mảng đếm + cộng dồn theo độ cao – O(N + Q + H) · 50%
Dùng nhận xét ở Lời mở đầu: đáp án $=$ (số ô có $h_i > w$) $-$ (số cặp có $cap_i > w$). Khi mọi độ cao không vượt quá $H = 10^6$, ta chuẩn bị sẵn hai mảng theo độ cao:
soO[v]$=$ số ô có độ cao $\ge v$;soCap[v]$=$ số cặp ô kề nhau có $\min$ độ cao $\ge v$.
Cách làm: đếm tần suất trước (soO[h[i]]++, soCap[min(h[i], h[i+1])]++), rồi cộng dồn từ độ cao lớn xuống: soO[v] += soO[v + 1]. Ô khô khi $h_i > w$, tức là $h_i \ge w + 1$, nên đáp án là soO[w + 1] - soCap[w + 1]. Nếu $w \ge 10^6$ thì mọi ô đều ngập, đáp án là $0$ (và cũng tránh truy cập ra ngoài mảng).
Chạy tay với ví dụ của đề: $h = [1, 5, 3, 8, 9, 1, 6, 3, 6, 0]$, $cap = [1, 3, 3, 8, 1, 1, 3, 3, 0]$.
| $v$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| soO[$v$] (ô cao $\ge v$) | 10 | 9 | 7 | 7 | 5 | 5 | 4 | 2 | 2 | 1 | 0 |
| soCap[$v$] (cặp có min $\ge v$) | 9 | 8 | 5 | 5 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
Mực nước $2$ → xem cột $v = 3$: $7 - 5 = 2$. Mực nước $4$ → cột $5$: $5 - 1 = 4$. Mực nước $7$ → cột $8$: $2 - 1 = 1$. Mực nước $10$ → cột $11$ (ngoài bảng, bằng $0$): $0 - 0 = 0$. Đúng như đề!
Khi có ô cao hơn $10^6$ (Subtask 3), mảng theo độ cao phải dài tới $10^9$ phần tử — không đủ bộ nhớ. Code dưới đây khi đó quay về Cách 1 (nên vẫn đúng Subtask 1).
#include <bits/stdc++.h>
using namespace std;
const int LIM = 1000000; // Subtask 2: moi do cao <= 10^6
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> h(n);
for (int i = 0; i < n; i++) cin >> h[i];
int q;
cin >> q;
vector<int> w(q);
for (int k = 0; k < q; k++) cin >> w[k];
if (*max_element(h.begin(), h.end()) > LIM) { // khong thuoc Subtask 2: dung Cach 1
for (int k = 0; k < q; k++) {
int soDoi = 0;
for (int i = 0; i < n; i++)
if (h[i] > w[k] && (i == 0 || h[i - 1] <= w[k])) soDoi++;
cout << soDoi << '\n';
}
return 0;
}
// soO[v] = so o co do cao >= v, soCap[v] = so cap o ke nhau co min(do cao) >= v
vector<int> soO(LIM + 2, 0), soCap(LIM + 2, 0);
for (int i = 0; i < n; i++) soO[h[i]]++;
for (int i = 0; i + 1 < n; i++) soCap[min(h[i], h[i + 1])]++;
for (int v = LIM; v >= 0; v--) { // cong don tu do cao lon xuong
soO[v] += soO[v + 1];
soCap[v] += soCap[v + 1];
}
for (int k = 0; k < q; k++) {
if (w[k] >= LIM) { cout << 0 << '\n'; continue; } // nuoc cao hon moi o
// o kho khi do cao > w, tuc la >= w + 1
cout << soO[w[k] + 1] - soCap[w[k] + 1] << '\n';
}
return 0;
}import sys
LIM = 1000000 # Subtask 2: moi do cao <= 10^6
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
h = list(map(int, data[1:1 + n]))
q = int(data[1 + n])
w = list(map(int, data[2 + n:2 + n + q]))
out = []
if max(h) > LIM: # khong thuoc Subtask 2: dung Cach 1
for x in w:
soDoi = 0
for i in range(n):
if h[i] > x and (i == 0 or h[i - 1] <= x):
soDoi += 1
out.append(soDoi)
sys.stdout.write("\n".join(map(str, out)) + "\n")
return
# soO[v] = so o co do cao >= v, soCap[v] = so cap o ke nhau co min(do cao) >= v
soO = [0] * (LIM + 2)
soCap = [0] * (LIM + 2)
for i in range(n):
soO[h[i]] += 1
for i in range(n - 1):
soCap[min(h[i], h[i + 1])] += 1
for v in range(LIM, -1, -1): # cong don tu do cao lon xuong
soO[v] += soO[v + 1]
soCap[v] += soCap[v + 1]
for x in w:
if x >= LIM: # nuoc cao hon moi o
out.append(0)
else: # o kho khi do cao > w, tuc la >= w + 1
out.append(soO[x + 1] - soCap[x + 1])
sys.stdout.write("\n".join(map(str, out)) + "\n")
main()Cách 3Sắp xếp + tìm kiếm nhị phân – O((N + Q) log N) · 100%
Ta chỉ cần trả lời câu hỏi "trong một mảng có bao nhiêu số lớn hơn $w$?" thật nhanh mà không cần mảng theo độ cao. Câu trả lời quen thuộc: sắp xếp tăng dần mảng đó một lần, rồi với mỗi $w$ tìm vị trí của số đầu tiên lớn hơn $w$ bằng tìm kiếm nhị phân (upper_bound trong C++, bisect_right trong Python). Nếu vị trí đó là $p$ thì có đúng $N - p$ số lớn hơn $w$.
- Tạo mảng $cap$ gồm $N - 1$ số $cap_i = \min(h_i, h_{i+1})$ trước khi sắp xếp $h$ (sắp xếp xong thì thứ tự các ô mất).
- Sắp xếp $h$ và $cap$.
- Mỗi mực nước $w$: đáp án $= (N - \text{upper\_bound}(h, w)) - ((N - 1) - \text{upper\_bound}(cap, w))$.
Mỗi truy vấn chỉ tốn $O(\log N)$ và được trả lời ngay khi đọc vào, nên cũng không lo sai thứ tự in.
Code đầy đủ:
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> h(n);
for (int i = 0; i < n; i++) cin >> h[i];
vector<int> cap(n - 1); // cap o (i, i+1) cung kho khi w < min(h[i], h[i+1])
for (int i = 0; i + 1 < n; i++) cap[i] = min(h[i], h[i + 1]);
sort(h.begin(), h.end());
sort(cap.begin(), cap.end());
int q;
cin >> q;
for (int k = 0; k < q; k++) {
int w;
cin >> w;
int soO = h.end() - upper_bound(h.begin(), h.end(), w); // so o co do cao > w
int soCap = cap.end() - upper_bound(cap.begin(), cap.end(), w); // so cap ke nhau cung kho
cout << soO - soCap << '\n';
}
return 0;
}import sys
from bisect import bisect_right
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
h = list(map(int, data[1:1 + n]))
# cap o (i, i+1) cung kho khi w < min(h[i], h[i+1])
cap = list(map(min, h[:-1], h[1:]))
h.sort()
cap.sort()
q = int(data[1 + n])
out = []
for k in range(2 + n, 2 + n + q):
w = int(data[k])
soO = n - bisect_right(h, w) # so o co do cao > w
soCap = n - 1 - bisect_right(cap, w) # so cap ke nhau cung kho
out.append(soO - soCap)
sys.stdout.write("\n".join(map(str, out)) + "\n")
main()upper_bound, không phải lower_bound — hơn một phần ba số mực nước trong bộ test bằng đúng độ cao một ô, nhầm chỉ còn 1,8%. (2) Tự viết tìm kiếm nhị phân thì khoảng tìm phải là $[0, N]$ (vị trí $N$ nghĩa là "không có số nào lớn hơn $w$"); khởi tạo hi = N - 1 thì khi chỉ còn vài đỉnh lẻ khô sẽ bị đếm thừa một cặp — còn 23,9%. (3) Đếm "ô đầu doi" thì đừng quên ô $1$ — còn 3,6%. (4) Sắp xếp truy vấn thì phải trả lại thứ tự — còn 5,5%.Bộ test chấm "bắt" những lỗi nào?
Bộ test có 30 test: Subtask 1 có 11 test ($N, Q \le 1000$; gồm ví dụ, $N = 1$, dải ngập hết, dải toàn ô cao $10^9$, cao thấp xen kẽ), Subtask 2 có 9 test ($h \le 10^6$, $N, Q \approx 2\cdot 10^5$; có test độ cao đúng bằng $10^6$), Subtask 3 có 10 test ($N, Q \approx 2\cdot 10^5$, mọi test đều có ô cao hơn $10^6$, phần lớn tới $10^9$). Địa hình gồm: ngẫu nhiên, đi ngẫu nhiên (doi dài), nhiều ô liền nhau bằng nhau, cao thấp xen kẽ (khoảng $10^5$ doi), nhiều ngọn đồi, răng cưa. Mực nước: hơn một phần ba bằng đúng độ cao một ô, một phần nằm ở mức chỉ còn vài đỉnh lẻ khô, thứ tự xáo trộn. Điểm tính theo từng test (thang 100%).
| Cách làm | Sub 1 (11) | Sub 2 (9) | Sub 3 (10) | Điểm |
|---|---|---|---|---|
| Cách 1 – Đếm trực tiếp | Đúng 11/11 | TLE 0/9 | TLE 0/10 | 20 |
| Cách 2 – Mảng đếm + cộng dồn | Đúng 11/11 | Đúng 9/9 | TLE 0/10 | 50 |
| Cách 3 – Sắp xếp + upper_bound (chuẩn) | Đúng 11/11 | Đúng 9/9 | Đúng 10/10 | 100 |
Sai: tự viết tìm nhị phân với hi = N - 1 | WA 4/11 | WA 2/9 | WA 2/10 | 23,9 |
| Sai: quên trả lại thứ tự truy vấn | WA 3/11 | WA 0/9 | WA 0/10 | 5,5 |
| Sai: đếm ô đầu doi nhưng quên ô 1 | WA 2/11 | WA 0/9 | WA 0/10 | 3,6 |
Sai: ô khô khi $h \ge w$ (dùng lower_bound) | WA 1/11 | WA 0/9 | WA 0/10 | 1,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 11/11 test Subtask 1 và quá thời gian (chạy hơn 100 giây) ở toàn bộ 19 test còn lại; Cách 2 đúng 20/20 test của hai subtask đầu và quá thời gian ở cả 10 test Subtask 3; Cách 3 đúng 30/30 test, test lâu nhất chạy khoảng 0,13 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,5 giây ngay cả với CPython. Ví dụ của đề khá "hiền": không mực nước nào bằng độ cao một ô, ô $1$ luôn ngập, hai ô cao nhất lại nằm cạnh nhau, và các mực nước được cho sẵn theo thứ tự tăng dần — cả bốn lời giải sai trong bảng đều vẫn ra đúng ví dụ, 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