Tưới vườn cam (Đề tự luyện HSG Tin 9 – Bài 3)
Đề bài
Tưới vườn cam. Vườn cam của thầy Sơn là lưới $M \times N$ cây. Thầy tưới $P$ lần, mỗi lần tưới mọi cây trong một khu hình chữ nhật cho bởi hai góc đối diện $(r_1, c_1), (r_2, c_2)$ — không đảm bảo $r_1 \le r_2$ hay $c_1 \le c_2$. Mỗi lần, mỗi cây trong khu nhận thêm $1$ lượt nước. Cây nhận ít nhất $K$ lượt là cây đủ nước. Có $Q$ câu hỏi, mỗi câu cho một khu hình chữ nhật (cũng bằng hai góc đối diện bất kỳ): khu đó có bao nhiêu cây đủ nước?
Dữ liệu vào: dòng 1 là $M, N, K$ $(M \cdot N \le 10^6,\ 0 \le K \le 10^5)$; dòng 2 là $P$ $(1 \le P \le 10^5)$; $P$ dòng mỗi dòng $r_1\ c_1\ r_2\ c_2$; tiếp theo là $Q$ $(1 \le Q \le 10^5)$ và $Q$ dòng mỗi dòng $x_1\ y_1\ x_2\ y_2$.
Kết quả: $Q$ dòng, mỗi dòng là đáp án một câu hỏi.
- Subtask 1 (20%): $M, N \le 100$ và $P, Q \le 100$.
- Subtask 2 (30%): $Q \le 10$.
- Subtask 3 (50%): không ràng buộc thêm (vườn có thể "dài" $1 \times 10^6$ hoặc $10^6 \times 1$).
3 4 2
3
1 1 2 3
3 4 2 2
2 1 2 1
2
1 1 3 4
3 3 1 23
2Số lượt nước sau 3 lần tưới:
1 1 1 0
2 2 2 1
0 1 1 1Cây đủ nước ($\ge 2$) là $(2,1), (2,2), (2,3)$. Câu 2 hỏi khu hàng $1..3$, cột $2..3$: có $2$ cây.
2 3 0
1
1 1 1 1
1
2 3 1 24$K = 0$ nên mọi cây đều đủ nước, kể cả cây chưa được tưới. Khu hàng $1..2$, cột $2..3$ có $4$ cây.
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 Tưới vườn camLời mở đầu
Bài này có hai giai đoạn nối tiếp nhau, và mỗi giai đoạn cần một kỹ thuật "cộng dồn" riêng:
- Cập nhật: sau $P$ lần tưới, mỗi cây nhận bao nhiêu lượt nước? Đây là bài toán "cộng $1$ vào cả một hình chữ nhật" rất nhiều lần — dùng mảng hiệu 2 chiều.
- Truy vấn: đánh dấu cây đủ nước là $1$, cây thiếu nước là $0$; mỗi câu hỏi là "tính tổng các số trong một hình chữ nhật" — dùng mảng cộng dồn 2 chiều.
Hình 1. Trái: muốn cộng 1 vào cả khu hàng 2..3, cột 2..4, ta chỉ ghi 4 con số ở 4 góc; cộng dồn 2 chiều sẽ "lan" chúng ra đúng khu đó. Phải: số cây trong khu hỏi tính bằng 4 giá trị của bảng cộng dồn S.
Và ba cái bẫy thầy cài sẵn trong đề:
- Hai góc đối diện bất kỳ: phải đổi chỗ để có $r_1 \le r_2$ và $c_1 \le c_2$ trước khi dùng (cả lúc tưới lẫn lúc hỏi). Ở lần tưới 2 của ví dụ, góc được ghi là $(3,4)$ rồi mới tới $(2,2)$. Cẩn thận: phải đổi riêng hàng và riêng cột. Code chỉ "đổi chỗ hai điểm khi $r_1 > r_2$" vẫn qua cả hai ví dụ của đề, nhưng sai với cặp góc kiểu $(1, 4)$ và $(3, 2)$ (trên-phải và dưới-trái).
- $K = 0$: mọi cây đều đủ nước, kể cả cây chưa được tưới lần nào. Code "chỉ xét cây đã được tưới" sẽ sai.
- Vườn dài: chỉ có $M \cdot N \le 10^6$, nên có thể $M = 1, N = 10^6$. Khai báo mảng cố định
int a[1005][1005]là "toang". Ta dùng mảng một chiều: ô $(r, c)$ nằm ở vị trí $r \cdot W + c$ với $W = N + 2$.
Cách 1Tưới và đếm trực tiếp – O((P + Q)·M·N) · 20%
Làm đúng như đề kể: dùng mảng g[r][c] đếm số lượt nước. Mỗi lần tưới, duyệt mọi ô trong khu và tăng $1$. Mỗi câu hỏi, duyệt mọi ô trong khu và đếm ô có g[r][c] >= K. Nhớ đổi chỗ hai góc nếu cần.
Mỗi lần tưới hoặc hỏi tốn tối đa $M \cdot N$ bước. Subtask 1 có $M \cdot N \le 10^4$ và $P + Q \le 200$, tổng khoảng $2 \cdot 10^6$ — quá nhẹ. Nhưng với $M \cdot N = 10^6$ và $P = 10^5$ lần tưới khu lớn thì lên tới cỡ $10^{10}$ bước.
#include <bits/stdc++.h>
using namespace std;
int main() {
int m, n, K, p;
cin >> m >> n >> K >> p;
vector<vector<int>> g(m + 1, vector<int>(n + 1, 0)); // g[r][c] = so lan tuoi
for (int i = 0; i < p; i++) {
int r1, c1, r2, c2;
cin >> r1 >> c1 >> r2 >> c2;
if (r1 > r2) swap(r1, r2);
if (c1 > c2) swap(c1, c2);
for (int r = r1; r <= r2; r++)
for (int c = c1; c <= c2; c++) g[r][c]++;
}
int q;
cin >> q;
while (q--) {
int r1, c1, r2, c2;
cin >> r1 >> c1 >> r2 >> c2;
if (r1 > r2) swap(r1, r2);
if (c1 > c2) swap(c1, c2);
int dem = 0;
for (int r = r1; r <= r2; r++)
for (int c = c1; c <= c2; c++)
if (g[r][c] >= K) dem++;
cout << dem << '\n';
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
m = int(data[0]); n = int(data[1]); K = int(data[2]); p = int(data[3])
g = [[0] * (n + 1) for _ in range(m + 1)] # g[r][c] = so lan tuoi
pos = 4
for _ in range(p):
r1, c1, r2, c2 = map(int, data[pos:pos + 4]); pos += 4
if r1 > r2: r1, r2 = r2, r1
if c1 > c2: c1, c2 = c2, c1
for r in range(r1, r2 + 1):
row = g[r]
for c in range(c1, c2 + 1):
row[c] += 1
q = int(data[pos]); pos += 1
out = []
for _ in range(q):
r1, c1, r2, c2 = map(int, data[pos:pos + 4]); pos += 4
if r1 > r2: r1, r2 = r2, r1
if c1 > c2: c1, c2 = c2, c1
dem = 0
for r in range(r1, r2 + 1):
row = g[r]
for c in range(c1, c2 + 1):
if row[c] >= K:
dem += 1
out.append(dem)
print('\n'.join(map(str, out)))
main()Cách 2Mảng hiệu 2 chiều – O(M·N + P + Q·M·N) · 50%
Nhắc lại mảng hiệu 1 chiều
Trên một hàng cây, muốn cộng $1$ vào đoạn $[c_1, c_2]$, ta chỉ ghi $d[c_1] \mathrel{+}= 1$ và $d[c_2 + 1] \mathrel{-}= 1$. Sau khi ghi hết các lần tưới, cộng dồn $d$ từ trái sang phải: dấu $+1$ "bật" từ $c_1$, dấu $-1$ "tắt" từ $c_2 + 1$, nên mỗi ô nhận đúng số đoạn chứa nó.
Lên 2 chiều: bốn góc
Để cộng $1$ vào cả khu $[r_1..r_2] \times [c_1..c_2]$ ta ghi bốn số:
$$d[r_1][c_1] \mathrel{+}= 1,\quad d[r_1][c_2+1] \mathrel{-}= 1,\quad d[r_2+1][c_1] \mathrel{-}= 1,\quad d[r_2+1][c_2+1] \mathrel{+}= 1.$$Sau đó lấy cộng dồn 2 chiều: giá trị thật ở ô $(r, c)$ là tổng của mọi $d[i][j]$ với $i \le r, j \le c$. Tính lần lượt theo hàng, từ trái sang phải:
$$v[r][c] = d[r][c] + v[r-1][c] + v[r][c-1] - v[r-1][c-1].$$(Ô $(r-1, c-1)$ bị cộng hai lần, qua $v[r-1][c]$ và qua $v[r][c-1]$, nên phải trừ đi một lần.) Kiểm tra: ô nằm trong khu thì "thấy" đúng góc $+1$ ở $(r_1, c_1)$ → giá trị $1$; ô nằm bên phải khu thấy $+1$ và $-1$ ở cột $c_2+1$ → $0$; ô nằm dưới-phải thấy cả bốn góc $+1 - 1 - 1 + 1 = 0$. Đúng như Hình 1.
Mô phỏng dưới đây cho các bạn xem từng bước: ghi bốn góc cho mỗi lần tưới, cộng dồn từng hàng, rồi trả lời câu hỏi bằng bảng $S$ (phần của Cách 3).
Ở Cách 2, sau khi có bảng số lượt nước, mỗi câu hỏi ta vẫn đếm trực tiếp. Với Subtask 2 chỉ có $Q \le 10$ câu nên tổng chi phí khoảng $10 \cdot 10^6$, rất ổn.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int m, n, K, p;
cin >> m >> n >> K >> p;
int W = n + 2; // o (r, c) nam o vi tri r * W + c
vector<int> d((m + 2) * W, 0); // mang hieu 2 chieu
for (int i = 0; i < p; i++) {
int r1, c1, r2, c2;
cin >> r1 >> c1 >> r2 >> c2;
if (r1 > r2) swap(r1, r2);
if (c1 > c2) swap(c1, c2);
d[r1 * W + c1]++;
d[r1 * W + c2 + 1]--;
d[(r2 + 1) * W + c1]--;
d[(r2 + 1) * W + c2 + 1]++;
}
for (int r = 1; r <= m; r++)
for (int c = 1; c <= n; c++) {
int i = r * W + c;
d[i] += d[i - W] + d[i - 1] - d[i - W - 1]; // d[i] = so lan tuoi o (r, c)
}
int q;
cin >> q;
while (q--) { // dem truc tiep: chi dung khi Q nho
int r1, c1, r2, c2;
cin >> r1 >> c1 >> r2 >> c2;
if (r1 > r2) swap(r1, r2);
if (c1 > c2) swap(c1, c2);
int dem = 0;
for (int r = r1; r <= r2; r++)
for (int c = c1; c <= c2; c++)
if (d[r * W + c] >= K) dem++;
cout << dem << '\n';
}
return 0;
}import sys
from itertools import accumulate
def main():
data = sys.stdin.buffer.read().split()
m = int(data[0]); n = int(data[1]); K = int(data[2]); p = int(data[3])
W = n + 2 # o (r, c) nam o vi tri r * W + c
d = [0] * ((m + 2) * W) # mang hieu 2 chieu
pos = 4
for _ in range(p):
r1 = int(data[pos]); c1 = int(data[pos + 1]); r2 = int(data[pos + 2]); c2 = int(data[pos + 3])
pos += 4
if r1 > r2: r1, r2 = r2, r1
if c1 > c2: c1, c2 = c2, c1
d[r1 * W + c1] += 1
d[r1 * W + c2 + 1] -= 1
d[(r2 + 1) * W + c1] -= 1
d[(r2 + 1) * W + c2 + 1] += 1
prev_v = [0] * W
for r in range(1, m + 1):
row = list(accumulate(d[r * W:(r + 1) * W])) # cong don theo hang
v = [x + y for x, y in zip(row, prev_v)] # = so lan tuoi o (r, c)
d[r * W:(r + 1) * W] = v
prev_v = v
q = int(data[pos]); pos += 1
out = []
for _ in range(q): # dem truc tiep: chi dung khi Q nho
r1 = int(data[pos]); c1 = int(data[pos + 1]); r2 = int(data[pos + 2]); c2 = int(data[pos + 3])
pos += 4
if r1 > r2: r1, r2 = r2, r1
if c1 > c2: c1, c2 = c2, c1
dem = 0
for r in range(r1, r2 + 1):
for x in d[r * W + c1:r * W + c2 + 1]:
if x >= K:
dem += 1
out.append(dem)
print('\n'.join(map(str, out)))
main()Cách 3Thêm cộng dồn 2 chiều – O(M·N + P + Q) · 100%
Đặt $ok[r][c] = 1$ nếu cây $(r, c)$ đủ nước (tức $v[r][c] \ge K$), ngược lại bằng $0$. Câu hỏi trở thành: tổng các $ok$ trong một hình chữ nhật. Đây đúng là việc của mảng cộng dồn 2 chiều:
$$S[r][c] = ok[r][c] + S[r-1][c] + S[r][c-1] - S[r-1][c-1],$$với $S[r][c]$ là số cây đủ nước trong khu từ $(1,1)$ tới $(r,c)$. Khi đó khu $[r_1..r_2] \times [c_1..c_2]$ có số cây đủ nước là
$$S[r_2][c_2] - S[r_1-1][c_2] - S[r_2][c_1-1] + S[r_1-1][c_1-1].$$Hai phép trừ bỏ đi phần phía trên và phần bên trái khu hỏi; góc trên-trái bị trừ hai lần nên cộng lại một lần (Hình 1, bên phải). Mỗi câu hỏi chỉ còn $O(1)$.
Điều thú vị là ta tính được cả $v$ và $S$ trong cùng một vòng lặp: khi đi tới ô $(r, c)$ theo thứ tự hàng, mọi ô phía trên và bên trái đã có giá trị cuối cùng. Code dưới đây tận dụng luôn mảng d để chứa $v$ (ghi đè lên chính nó) cho đỡ tốn bộ nhớ.
d[i] >= K đúng với mọi cây, nên $ok = 1$ ở khắp vườn — đúng như đề yêu cầu. Nếu bạn viết d[i] > K (nhầm "ít nhất" thành "nhiều hơn") thì sai gần như mọi test.itertools.accumulate và zip để nhanh hơn. Nếu vườn "cao" ($M > N$, ví dụ $10^6 \times 1$), ta xoay vườn (đổi vai trò hàng và cột của mọi toạ độ) để vòng lặp theo hàng chỉ chạy ít lần — số cây đủ nước trong mỗi khu không đổi khi xoay.#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int m, n, K, p;
cin >> m >> n >> K >> p;
int W = n + 2; // o (r, c) nam o vi tri r * W + c
vector<int> d((m + 2) * W, 0); // mang hieu 2 chieu
for (int i = 0; i < p; i++) {
int r1, c1, r2, c2;
cin >> r1 >> c1 >> r2 >> c2;
if (r1 > r2) swap(r1, r2); // hai goc doi dien: co the nguoc
if (c1 > c2) swap(c1, c2);
d[r1 * W + c1]++;
d[r1 * W + c2 + 1]--;
d[(r2 + 1) * W + c1]--;
d[(r2 + 1) * W + c2 + 1]++;
}
vector<int> S((m + 2) * W, 0); // S = cong don cua "du nuoc"
for (int r = 1; r <= m; r++)
for (int c = 1; c <= n; c++) {
int i = r * W + c;
d[i] += d[i - W] + d[i - 1] - d[i - W - 1]; // d[i] = so lan tuoi o (r, c)
int ok = (d[i] >= K) ? 1 : 0;
S[i] = ok + S[i - W] + S[i - 1] - S[i - W - 1];
}
int q;
cin >> q;
while (q--) {
int r1, c1, r2, c2;
cin >> r1 >> c1 >> r2 >> c2;
if (r1 > r2) swap(r1, r2);
if (c1 > c2) swap(c1, c2);
int ans = S[r2 * W + c2] - S[(r1 - 1) * W + c2] - S[r2 * W + c1 - 1] + S[(r1 - 1) * W + c1 - 1];
cout << ans << '\n';
}
return 0;
}import sys
from itertools import accumulate
def main():
data = sys.stdin.buffer.read().split()
m = int(data[0]); n = int(data[1]); K = int(data[2]); p = int(data[3])
tr = m > n # vuon "cao": doi vai tro hang/cot cho nhanh
if tr: m, n = n, m # (so cay du nuoc khong doi khi xoay vuon)
W = n + 2 # o (r, c) nam o vi tri r * W + c
d = [0] * ((m + 2) * W) # mang hieu 2 chieu
pos = 4
for _ in range(p):
r1 = int(data[pos]); c1 = int(data[pos + 1]); r2 = int(data[pos + 2]); c2 = int(data[pos + 3])
pos += 4
if tr: r1, c1, r2, c2 = c1, r1, c2, r2
if r1 > r2: r1, r2 = r2, r1 # hai goc doi dien: co the nguoc
if c1 > c2: c1, c2 = c2, c1
d[r1 * W + c1] += 1
d[r1 * W + c2 + 1] -= 1
d[(r2 + 1) * W + c1] -= 1
d[(r2 + 1) * W + c2 + 1] += 1
S = [0] * ((m + 2) * W) # S = cong don cua "du nuoc"
prev_v = [0] * W # hang tren cua so lan tuoi
prev_s = [0] * W # hang tren cua S
for r in range(1, m + 1):
row = list(accumulate(d[r * W:(r + 1) * W])) # cong don theo hang
v = [x + y for x, y in zip(row, prev_v)] # = so lan tuoi o (r, c)
ok = [1 if x >= K else 0 for x in v] # 1 neu o (r, c) du nuoc
ok[0] = 0 # cot 0 la vien, khong phai cay
s = [x + y for x, y in zip(accumulate(ok), prev_s)]
S[r * W:(r + 1) * W] = s
prev_v = v; prev_s = s
q = int(data[pos]); pos += 1
out = []
for _ in range(q):
r1 = int(data[pos]); c1 = int(data[pos + 1]); r2 = int(data[pos + 2]); c2 = int(data[pos + 3])
pos += 4
if tr: r1, c1, r2, c2 = c1, r1, c2, r2
if r1 > r2: r1, r2 = r2, r1
if c1 > c2: c1, c2 = c2, c1
out.append(S[r2 * W + c2] - S[(r1 - 1) * W + c2] - S[r2 * W + c1 - 1] + S[(r1 - 1) * W + c1 - 1])
sys.stdout.write('\n'.join(map(str, out)) + '\n')
main()Bộ test chấm "bắt" những lỗi nào?
Bộ test có 32 test: Subtask 1 có 10 test (gồm hai ví dụ, vườn $1 \times 1$, $K = 0$, $K > P$, vườn $1 \times 100$ và $100 \times 1$), Subtask 2 có 10 test ($P = 8 \cdot 10^4$ – $10^5$ lần tưới khu lớn, $Q = 10$), Subtask 3 có 12 test ($P, Q$ cỡ $10^5$, khu hỏi lớn). Hai subtask sau có đủ các hình dạng vườn $1000 \times 1000$, $1 \times 10^6$, $10^6 \times 1$, $100000 \times 10$, $250 \times 4000$... và hai góc luôn được ghi theo thứ tự ngẫu nhiên. Điểm tính theo từng test (thang 100%).
| Cách làm | Sub 1 (10 test) | Sub 2 (10 test) | Sub 3 (12 test) | Điểm |
|---|---|---|---|---|
| Cách 1 – Tưới và đếm trực tiếp | Đúng 10/10 | TLE 0/10 | TLE 0/12 | 20 |
| Cách 2 – Mảng hiệu 2 chiều, đếm trực tiếp | Đúng 10/10 | Đúng 10/10 | TLE 0/12 | 50 |
| Cách 3 – Mảng hiệu + cộng dồn 2 chiều (chuẩn) | Đúng 10/10 | Đúng 10/10 | Đúng 12/12 | 100 |
| Sai: không đổi chỗ hai góc | WA 2/10 | WA 0/10 | WA 1/12 | 8,2 |
Sai: dùng > K thay vì >= K | WA 2/10 | WA 1/10 | WA 1/12 | 11,2 |
Sai: mảng cố định [1005][1005] | Đúng 10/10 | 5/10 (RTE/WA) | 5/12 (RTE/WA) | 55,8 |
| Kém một bậc: mảng hiệu 1 chiều trên từng hàng, $O(P \cdot M)$ | Đúng 10/10 | TLE 2, đúng 8/10 | TLE 2, đúng 10/12 | 85,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 10/10 test Subtask 1 và quá thời gian (hơn 3 giây) ở toàn bộ 22 test còn lại; Cách 2 đúng 20/20 test của hai subtask đầu và quá thời gian ở cả 12 test Subtask 3; Cách 3 đúng 32/32 test, test lâu nhất chạy khoảng 0,15 giây. Lời giải Python của Cách 3 cũng đúng 32/32 test, chạy tối đa khoảng 1,7 giây với CPython (PyPy còn nhanh hơn nhiều). Lỗi "mảng hiệu 1 chiều trên từng hàng" chỉ bị lộ ở các vườn rất cao như $10^6 \times 1$ hay $100000 \times 10$, nơi mỗi lần tưới phải đi qua hàng trăm nghìn hàng.
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