Dựng rạp cưới (Đề tự luyện HSG Tin 9 – Bài 3) – Tổng tiền tố 2 chiều hai lớp: ô vướng và góc rạp hợp lệ
Đề bài
Dựng rạp cưới. Sân là lưới $N \times M$ gồm ô trống . và ô vướng #. Rạp phủ kín $a$ hàng liên tiếp $\times$ $b$ cột liên tiếp, hoặc xoay thành $b$ hàng $\times$ $a$ cột; rạp phải nằm trọn trong sân và không phủ ô vướng. Hai cách dựng khác nhau nếu tập ô được phủ khác nhau (khi $a = b$ xoay không tạo cách mới). Với mỗi câu hỏi $(x, y)$: có bao nhiêu cách dựng rạp phủ ô $(x, y)$?
Dữ liệu vào: $N, M, a, b$ $(1 \le N, M, a, b \le 1000)$; $N$ dòng mô tả sân; $Q$ $(1 \le Q \le 2 \cdot 10^5)$; $Q$ dòng $x, y$.
Kết quả: $Q$ dòng, mỗi dòng là số cách dựng rạp phủ ô được hỏi.
- Subtask 1 (20%): $N, M \le 20$, $Q \le 100$.
- Subtask 2 (30%): $N, M \le 300$, $Q \le 1000$.
- Subtask 3 (50%): không ràng buộc thêm.
4 6 2 3
.....#
.##..#
......
......
3
4 2
3 1
3 32
1
3Có 6 cách dựng hợp lệ: bốn cách $2 \times 3$ trên hàng 3–4 (cột 1–3, 2–4, 3–5, 4–6) và hai cách $3 \times 2$ trên cột 4–5 (hàng 1–3, 2–4). Ô $(4,2)$ nằm dưới 2 cách, ô $(3,1)$ dưới 1 cách, ô $(3,3)$ dưới 3 cách.
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 Dựng rạp cướiLời mở đầu
Đặt tên cho một cách dựng rạp: chọn hướng ($h$ hàng $\times$ $w$ cột, với $(h, w) = (a, b)$ hoặc $(b, a)$) và góc trên-trái $(i, j)$. Rạp phủ các hàng $i..i+h-1$ và các cột $j..j+w-1$. Khi đó
rạp phủ ô $(x, y)$ $\iff$ $x - h + 1 \le i \le x$ và $y - w + 1 \le j \le y$.
Nghĩa là: các góc trên-trái của những cái rạp phủ ô $(x, y)$ nằm gọn trong một hình chữ nhật $h \times w$ có góc dưới-phải chính là $(x, y)$! Bài toán biến thành: đếm số góc hợp lệ trong một hình chữ nhật — đúng sở trường của tổng tiền tố 2 chiều.
Hình 1. Ví dụ với $h = 2$, $w = 3$: các góc của rạp phủ ô X là một hình chữ nhật $2 \times 3$ kết thúc tại X.
Còn "góc $(i, j)$ hợp lệ" nghĩa là rạp nằm trong sân ($i + h - 1 \le N$, $j + w - 1 \le M$) và hình chữ nhật nó phủ có $0$ ô vướng — cũng đếm bằng tổng tiền tố 2 chiều. Bài này dùng tổng tiền tố 2 chiều hai lớp. Lộ trình:
Cách 1Thử mọi góc, soi từng ô dưới rạp – O(Q · h²w²) · 20%
Với mỗi câu hỏi và mỗi hướng, duyệt mọi góc $(i, j)$ trong vùng $[x-h+1, x] \times [y-w+1, y]$; bỏ qua nếu rạp ra ngoài sân; còn lại thì soi từng ô dưới rạp xem có # không. Nhớ: khi $a = b$ chỉ xét một hướng.
#include <bits/stdc++.h>
using namespace std;
int main() {
int N, M, a, b;
cin >> N >> M >> a >> b;
vector<string> g(N + 1);
for (int i = 1; i <= N; i++) {
cin >> g[i];
g[i] = " " + g[i]; // danh so cot tu 1
}
int soHuong = (a == b) ? 1 : 2;
int H[2] = {a, b}, W[2] = {b, a};
int q;
cin >> q;
while (q--) {
int x, y;
cin >> x >> y;
int ans = 0;
for (int k = 0; k < soHuong; k++) {
int h = H[k], w = W[k];
for (int i = x - h + 1; i <= x; i++) // goc tren-trai (i, j) cua rap phu o (x, y)
for (int j = y - w + 1; j <= y; j++) {
if (i < 1 || j < 1 || i + h - 1 > N || j + w - 1 > M) continue; // rap ra ngoai san
bool ok = true;
for (int u = i; u <= i + h - 1; u++) // kiem tra tung o duoi rap
for (int v = j; v <= j + w - 1; v++)
if (g[u][v] == '#') ok = false;
if (ok) ans++;
}
}
cout << ans << "\n";
}
return 0;
}import sys
def main():
data = sys.stdin.read().split()
N, M, a, b = int(data[0]), int(data[1]), int(data[2]), int(data[3])
g = [" " * (M + 1)] + [" " + data[4 + i] for i in range(N)] # danh so tu 1
p = 4 + N
huong = [(a, b)] if a == b else [(a, b), (b, a)]
q = int(data[p]); p += 1
out = []
for _ in range(q):
x = int(data[p]); y = int(data[p + 1]); p += 2
ans = 0
for h, w in huong:
for i in range(x - h + 1, x + 1): # goc tren-trai (i, j) cua rap phu o (x, y)
for j in range(y - w + 1, y + 1):
if i < 1 or j < 1 or i + h - 1 > N or j + w - 1 > M:
continue # rap ra ngoai san
ok = True
for u in range(i, i + h): # kiem tra tung o duoi rap
if '#' in g[u][j:j + w]:
ok = False
break
if ok:
ans += 1
out.append(ans)
print("\n".join(map(str, out)))
main()Với sân $20 \times 20$ thì $h \cdot w \le 400$, mỗi câu hỏi tối đa $2 \cdot 400 \cdot 400$ phép — ổn. Sân $300 \times 300$ với rạp $100 \times 100$ thì một câu hỏi đã $10^8$ phép: quá chậm.
Cách 2Tổng tiền tố của ô vướng – O(NM + Q · hw) · 50%
Lập $B[i][j]$ = số ô vướng trong hình chữ nhật $(1,1)$–$(i,j)$:
$B[i][j] = B[i-1][j] + B[i][j-1] - B[i-1][j-1] + [\text{ô }(i,j)\text{ vướng}]$.
Số ô vướng trong hình chữ nhật $(x_1, y_1)$–$(x_2, y_2)$ là $B[x_2][y_2] - B[x_1-1][y_2] - B[x_2][y_1-1] + B[x_1-1][y_1-1]$ — kiểm tra một cái rạp chỉ còn $O(1)$. Mỗi câu hỏi vẫn duyệt mọi góc trong vùng $h \times w$.
#include <bits/stdc++.h>
using namespace std;
int N, M;
vector<vector<int>> B; // B[i][j] = so o vuong trong hinh chu nhat (1,1)-(i,j)
int demVuong(int x1, int y1, int x2, int y2) {
return B[x2][y2] - B[x1 - 1][y2] - B[x2][y1 - 1] + B[x1 - 1][y1 - 1];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int a, b;
cin >> N >> M >> a >> b;
B.assign(N + 1, vector<int>(M + 1, 0));
for (int i = 1; i <= N; i++) {
string row;
cin >> row;
for (int j = 1; j <= M; j++)
B[i][j] = B[i - 1][j] + B[i][j - 1] - B[i - 1][j - 1] + (row[j - 1] == '#');
}
int soHuong = (a == b) ? 1 : 2;
int H[2] = {a, b}, W[2] = {b, a};
int q;
cin >> q;
while (q--) {
int x, y;
cin >> x >> y;
int ans = 0;
for (int k = 0; k < soHuong; k++) {
int h = H[k], w = W[k];
for (int i = max(1, x - h + 1); i <= x && i + h - 1 <= N; i++) // goc (i, j) phu o (x, y)
for (int j = max(1, y - w + 1); j <= y && j + w - 1 <= M; j++)
if (demVuong(i, j, i + h - 1, j + w - 1) == 0) ans++; // kiem tra O(1)
}
cout << ans << "\n";
}
return 0;
}import sys
from itertools import accumulate
from operator import add
def main():
data = sys.stdin.buffer.read().split()
N = int(data[0]); M = int(data[1]); a = int(data[2]); b = int(data[3])
bang = bytes.maketrans(b".#", b"\x00\x01")
B = [[0] * (M + 1)] # B[i][j] = so o vuong trong hinh chu nhat (1,1)-(i,j)
for i in range(N):
hang = data[4 + i].translate(bang)
B.append(list(map(add, B[i], accumulate(hang, initial=0))))
p = 4 + N
huong = [(a, b)] if a == b else [(a, b), (b, a)]
q = int(data[p]); p += 1
out = []
for _ in range(q):
x = int(data[p]); y = int(data[p + 1]); p += 2
ans = 0
for h, w in huong:
for i in range(max(1, x - h + 1), min(x, N - h + 1) + 1): # goc (i, j) phu o (x, y)
Bt = B[i - 1]; Bd = B[i + h - 1]
for j in range(max(1, y - w + 1), min(y, M - w + 1) + 1):
if Bd[j + w - 1] - Bt[j + w - 1] - Bd[j - 1] + Bt[j - 1] == 0:
ans += 1 # kiem tra O(1)
out.append(ans)
sys.stdout.write("\n".join(map(str, out)) + "\n")
main()$Q \le 1000$ và $hw \le 9 \cdot 10^4$: khoảng $1{,}8 \cdot 10^8$ phép, chạy kịp. Nhưng $Q = 2 \cdot 10^5$ câu hỏi với rạp $300 \times 400$ thì lên tới $10^{10}$ phép.
Cách 3Tổng tiền tố hai lớp – O(NM + Q) · 100%
Cách 2 lặp lại cùng một việc: góc $(i, j)$ có hợp lệ hay không thì không phụ thuộc câu hỏi! Ta tính sẵn cho từng hướng $(h, w)$:
- $ok[i][j] = 1$ nếu rạp $h \times w$ góc $(i, j)$ nằm trong sân và không phủ ô vướng (dùng $B$), ngược lại $0$;
- $V[i][j]$ = tổng tiền tố 2 chiều của $ok$.
Câu hỏi $(x, y)$ = tổng của $ok$ trên hình chữ nhật góc $[\max(1, x-h+1), x] \times [\max(1, y-w+1), y]$, lấy từ $V$ trong $O(1)$. Không cần chặn thêm phía dưới-phải: các góc làm rạp tràn ra ngoài sân đã có $ok = 0$. Cộng kết quả của hai hướng (chỉ một hướng nếu $a = b$).
Mô phỏng dưới đây vẽ bảng $ok$ của từng hướng cho ví dụ, rồi tô vùng góc của từng câu hỏi.
#include <bits/stdc++.h>
using namespace std;
int N, M;
vector<vector<int>> B; // B[i][j] = so o vuong trong hinh chu nhat (1,1)-(i,j)
int demVuong(int x1, int y1, int x2, int y2) {
return B[x2][y2] - B[x1 - 1][y2] - B[x2][y1 - 1] + B[x1 - 1][y1 - 1];
}
// V[i][j] = so goc tren-trai hop le (cho rap h hang x w cot) trong hinh chu nhat (1,1)-(i,j)
vector<vector<int>> lamV(int h, int w) {
vector<vector<int>> V(N + 1, vector<int>(M + 1, 0));
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++) {
int ok = 0;
if (i + h - 1 <= N && j + w - 1 <= M && demVuong(i, j, i + h - 1, j + w - 1) == 0) ok = 1;
V[i][j] = V[i - 1][j] + V[i][j - 1] - V[i - 1][j - 1] + ok;
}
return V;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int a, b;
cin >> N >> M >> a >> b;
B.assign(N + 1, vector<int>(M + 1, 0));
for (int i = 1; i <= N; i++) {
string row;
cin >> row;
for (int j = 1; j <= M; j++)
B[i][j] = B[i - 1][j] + B[i][j - 1] - B[i - 1][j - 1] + (row[j - 1] == '#');
}
int soHuong = (a == b) ? 1 : 2; // a = b thi xoay rap cung nhu cu
int H[2] = {a, b}, W[2] = {b, a};
vector<vector<int>> V[2];
for (int k = 0; k < soHuong; k++) V[k] = lamV(H[k], W[k]);
int q;
cin >> q;
while (q--) {
int x, y;
cin >> x >> y;
long long ans = 0;
for (int k = 0; k < soHuong; k++) {
// goc (i, j) phu o (x, y) khi x-h+1 <= i <= x va y-w+1 <= j <= y
int i1 = max(1, x - H[k] + 1), j1 = max(1, y - W[k] + 1);
int i2 = x, j2 = y;
ans += V[k][i2][j2] - V[k][i1 - 1][j2] - V[k][i2][j1 - 1] + V[k][i1 - 1][j1 - 1];
}
cout << ans << "\n";
}
return 0;
}import sys
from itertools import accumulate
from operator import add, sub, not_
def main():
data = sys.stdin.buffer.read().split()
N = int(data[0]); M = int(data[1]); a = int(data[2]); b = int(data[3])
bang = bytes.maketrans(b".#", b"\x00\x01")
B = [[0] * (M + 1)] # B[i][j] = so o vuong trong hinh chu nhat (1,1)-(i,j)
for i in range(N):
hang = data[4 + i].translate(bang) # '.' -> 0, '#' -> 1
B.append(list(map(add, B[i], accumulate(hang, initial=0))))
p = 4 + N
huong = [(a, b)] if a == b else [(a, b), (b, a)]
Vs = []
for h, w in huong:
# V[i][j] = so goc tren-trai hop le (rap h x w) trong hinh chu nhat (1,1)-(i,j)
V = [[0] * (M + 1)]
for i in range(1, N + 1):
if i + h - 1 <= N and w <= M:
D = list(map(sub, B[i + h - 1], B[i - 1])) # D[j] = so o vuong cua hang i..i+h-1, cot 1..j
ok = list(map(not_, map(sub, D[w:], D[:M - w + 1]))) # ok[j-1]: goc (i, j) khong phu o vuong nao
ok += [False] * (w - 1)
else:
ok = [False] * M
V.append(list(map(add, V[i - 1], accumulate(ok, initial=0))))
Vs.append((h, w, V))
q = int(data[p]); p += 1
out = []
for _ in range(q):
x = int(data[p]); y = int(data[p + 1]); p += 2
ans = 0
for h, w, V in Vs:
# goc (i, j) phu o (x, y) khi x-h+1 <= i <= x va y-w+1 <= j <= y
i1 = x - h if x > h else 0
j1 = y - w if y > w else 0
Vx = V[x]; Vi = V[i1]
ans += Vx[y] - Vi[y] - Vx[j1] + Vi[j1]
out.append(ans)
sys.stdout.write("\n".join(map(str, out)) + "\n")
main()accumulate (cộng dồn một hàng), map(add, ...) (cộng hai hàng), map(sub, D[w:], D[:M-w+1]) (số ô vướng của mọi rạp bắt đầu trong hàng). Ý tưởng vẫn y hệt bản C++.Bộ test chấm "bắt" những lỗi nào?
Bộ test có 28 test: Subtask 1 có 10 test ($N, M \le 20$: ví dụ, sân $1 \times 1$, rạp không vừa sân theo cả hai hướng, rạp vuông $a = b$, chỉ một hướng vừa sân, …), Subtask 2 có 8 test ($N, M \approx 300$, $1000$ câu hỏi), Subtask 3 có 10 test ($N, M \approx 1000$, $2 \cdot 10^5$ câu hỏi). Rạp luôn khá lớn ($h \cdot w$ từ vài nghìn tới hơn $10^5$ ô) để cách duyệt mọi góc bị quá thời gian; sân có nhiều kiểu: trống, rất ít ô vướng, vài khối vướng lớn, hàng rào ngắn; câu hỏi ngẫu nhiên, sát biên hoặc rơi đúng vào ô vướng. Điểm tính theo từng test (thang 100%).
| Cách làm | Sub 1 (10 test) | Sub 2 (8 test) | Sub 3 (10 test) | Điểm |
|---|---|---|---|---|
| Cách 1 – Thử mọi góc, soi từng ô | Đúng 10/10 | TLE 0/8 | TLE 0/10 | 20 |
| Cách 2 – Tiền tố ô vướng, duyệt mọi góc | Đúng 10/10 | Đúng 8/8 | TLE 0/10 | 50 |
| Cách 3 – Tiền tố hai lớp (chuẩn) | Đúng 10/10 | Đúng 8/8 | Đúng 10/10 | 100 |
| Sai: quên xoay rạp | WA 7/10 | WA 3/8 | WA 3/10 | 40,2 |
| Sai: $a = b$ vẫn đếm hai hướng | WA 7/10 | WA 6/8 | WA 8/10 | 76,5 |
| Sai: vùng góc từ $x - h$ (lệch một) | WA 4/10 | WA 0/8 | WA 0/10 | 8,0 |
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ộ 18 test còn lại; Cách 2 đúng 18/18 test của hai subtask đầu và quá thời gian cả 10 test Subtask 3; Cách 3 đúng 28/28 test, test lâu nhất chạy khoảng 0,11 giây. Lời giải Python của Cách 3 cũng đúng 28/28 test, chạy tối đa khoảng 0,85 giây với CPython. Ví dụ của đề khá "hiền": hai cách dựng rạp xoay không che ô nào được hỏi, các góc "lệch một" đều không hợp lệ, và $a \ne b$ — nên cả ba lời giải sai ở bảng trên đều vẫn ra đúng 2 1 3. 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