Hình chữ nhật 0 1 ver 1
Đề bài
Cho một bảng $a$ gồm $N$ hàng, $M$ cột. Ô ở hàng thứ $i$ và cột thứ $j$ được gọi là ô $(i, j)$, các ô trong bảng nhận giá trị $0$ hoặc $1$. Hình chữ nhật $(x_1, y_1, x_2, y_2)$ bao gồm các ô $(i, j)$ mà $x_1 \le i \le x_2$ và $y_1 \le j \le y_2$.
Yêu cầu: Hãy tính diện tích của hình chữ nhật lớn nhất bao gồm toàn số 0.
Dữ liệu:
- Dòng đầu tiên gồm hai số nguyên dương $N, M$ $(1 \le N, M \le 1000)$ là số hàng và số cột của bảng $a$.
- $N$ dòng tiếp theo, mỗi dòng chứa $M$ số $0$ hoặc $1$ biểu diễn giá trị của các ô trong bảng.
Kết quả: Gồm một dòng duy nhất là diện tích của hình chữ nhật thỏa mãn.
Ràng buộc: $1 \le N \le 1000$; $1 \le M \le 1000$; các ô của bảng có giá trị $0$ hoặc $1$.
Chấm điểm:
| Subtask | Ràng buộc thêm | % số điểm |
|---|---|---|
| 1 | $N, M \le 100$ | 50 |
| 2 | Không có | 50 |
Hạn chế thời gian: 1 giây. Hạn chế bộ nhớ: 256 MB.
5 4
1 0 0 1
0 0 0 0
0 1 1 0
1 1 0 0
1 0 0 04Giải thích ví dụ: có nhiều hình chữ nhật toàn số 0 diện tích $4$, ví dụ cả hàng 2 (các ô $(2, 1)$ – $(2, 4)$), hay khối $2 \times 2$ ở góc dưới phải (hàng 4–5, cột 3–4). Không có hình toàn 0 nào diện tích $5$ trở lên.
Lời mở đầu
Đây là bài "2 chiều" của bài Hình chữ nhật lớn nhất (histogram): thay vì một dãy cột, ta có một bảng 0/1 và cần tìm hình chữ nhật toàn số 0 lớn nhất. Mẹo then chốt là biến mỗi hàng của bảng thành một biểu đồ cột rồi dùng lại nguyên code ngăn xếp của bài trước. Bài này còn có "người anh em" ver 2 – vừa tìm diện tích vừa đếm số hình – mình viết riêng ở bài sau.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
| Test | N | M | Tỉ lệ số 0 | Diện tích lớn nhất |
|---|---|---|---|---|
| 1 – 20 | 2 … 10 | 2 … 10 | 39% … 69% | 3 … 10 |
| 21 – 50 | 10 … 98 | 11 … 96 | 48% … 51% | 8 … 16 |
| 51 – 80 | 113 … 943 | 101 … 966 | 49% … 50% | 14 … 24 |
| 81 – 100 | 1.000 | 1.000 | 49% … 49% | 20 … 24 |
- Bộ test có 100 test: test 1–50 thuộc subtask 1 ($N, M \le 100$), test 51–100 thuộc subtask 2 (test 81–100 đều là bảng $1000 \times 1000$ – một triệu ô).
- Mọi bảng đều sinh ngẫu nhiên với khoảng một nửa số ô là 0, nên hình chữ nhật toàn 0 lớn nhất rất nhỏ (không quá 24 ô). Bộ test không có bảng toàn 0 hay các khối 0 lớn.
| Subtask | Điều kiện | Các test | Cách 1 C++ | Cách 2 C++ | Cách 1 Python | Cách 2 Python |
|---|---|---|---|---|---|---|
| 1 (50%) | $N, M \le 100$ | 1 – 50 | 50/50 | 50/50 | 40/50 | 50/50 |
| 2 (50%) | Không có | 51 – 100 | 3/50 | 50/50 | 0/50 | 50/50 |
Ý tưởngMỗi hàng là một bài "Hình chữ nhật lớn nhất"
Bước 1 – biến bảng thành các biểu đồ cột. Cố định hàng đáy $i$ của hình chữ nhật. Với mỗi cột $j$, gọi
$h[j]$ = số ô 0 liên tiếp tính từ ô $(i, j)$ đi lên trên
(nếu $a[i][j] = 1$ thì $h[j] = 0$). Một hình chữ nhật toàn 0 có đáy ở hàng $i$, trải từ cột $l$ tới cột $r$, thì chiều cao của nó không vượt quá $\min(h[l..r])$ – y hệt bài Hình chữ nhật lớn nhất với $M$ cột cao $h[1..M]$!
Bước 2 – cập nhật $h$ từ hàng trước. Đi từ hàng $i - 1$ xuống hàng $i$ rất đơn giản:
$h[j] = \begin{cases} h[j] + 1 & \text{nếu } a[i][j] = 0 \\ 0 & \text{nếu } a[i][j] = 1 \end{cases}$
Hình chữ nhật toàn 0 lớn nhất có hàng đáy là một hàng $i$ nào đó, nên nó được tính tới khi ta xét hàng $i$ – không bỏ sót.
Em nhập bảng (các hàng cách nhau bởi dấu /) rồi bấm Tiếp để xem từng hàng biến thành biểu đồ cột thế nào:
Cách 1Vét mọi hình chữ nhật – O(N²M²)
Một hình chữ nhật được xác định bởi hàng trên $x_1$, hàng dưới $x_2$, cột trái $y_1$, cột phải $y_2$. Để biết nó có toàn 0 hay không, ta đếm số ô 1 bên trong bằng tổng tiền tố 2 chiều: $s[i][j]$ = số ô 1 trong hình $(1, 1)$ – $(i, j)$, khi đó số ô 1 của hình $(x_1, y_1, x_2, y_2)$ là
$s[x_2][y_2] - s[x_1 - 1][y_2] - s[x_2][y_1 - 1]$ $+ s[x_1 - 1][y_1 - 1]$
Hình toàn 0 khi và chỉ khi con số này bằng 0.
- Tính
s[i][j]ngay khi đọc, dùng công thức "trên + trái − chéo + ô hiện tại". - Mảng
a,skích thước $1005 \times 1005$ khai báo toàn cục (khoảng 8 MB) – để trong hàmmainsẽ dễ tràn bộ nhớ ngăn xếp.
Kết quả chạy thật: bản C++ đúng 53/100 test (quá 1 giây ở các test 51–58, 60–65, 67–75, 77–100), test đúng chạy lâu nhất 0.571s; bản Python đúng 40/100 test (quá thời gian ở các test 21–23, 25, 28, 38, 42, 44, 49–100), lâu nhất 0.52s.
Với $N = M = 100$ có khoảng $(100 \cdot 101 / 2)^2 \approx 2{,}5 \cdot 10^7$ hình – C++ chạy kịp. Với $N = M = 1000$ thì con số này là $2{,}5 \cdot 10^{11}$ – không thể.
Cách 2Chiều cao cột + ngăn xếp – O(N·M)
Cài đặt đúng ý tưởng ở trên. Đoạn giữa (tìm L, R bằng ngăn xếp rồi lấy max) chép gần y nguyên từ Cách 3 của bài Hình chữ nhật lớn nhất, chỉ đổi i thành j, n thành m.
- Không cần lưu cả bảng: đọc hàng nào xử lý hàng đó, mảng
hmang thông tin của các hàng phía trên. h[j] = (a == 0) ? h[j] + 1 : 0;– gặp số 1 thì "cột 0" bị cắt đứt, chiều cao về 0.- Mỗi hàng: mỗi cột được
push1 lần vàpopnhiều nhất 1 lần trong mỗi lần duyệt → $O(M)$ mỗi hàng, $O(N \cdot M)$ cả bài. Diện tích tối đa $10^6$ nên dùngintlà đủ. - Đọc $10^6$ số bằng
cincần cóios::sync_with_stdio(0); cin.tie(0);cho nhanh.
Kết quả chạy thật: bản C++ đúng 100/100 test, test đúng chạy lâu nhất 0.083s; bản Python đúng 100/100 test, lâu nhất 0.74s.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Đúng | Lâu nhất (test đúng) | Ghi chú |
|---|---|---|---|---|
| 1. Vét mọi hình + tổng tiền tố – $O(N^2 M^2)$ | C++ | 53/100 | 0.571s | Quá thời gian ở test 51–58, 60–65, 67–75, 77–100 |
| Python | 40/100 | 0.522s | Quá thời gian ở test 21–23, 25, 28, 38, 42, 44, 49–100 | |
| 2. Chiều cao cột + ngăn xếp – $O(N \cdot M)$ | C++ | 100/100 | 0.083s | Full điểm |
| Python | 100/100 | 0.739s | Full điểm |
Nhận xét
Đăng nhận xét