Hướng dẫn giải của Hình chữ nhật (đề Hà Nội 2021)
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Trong lưới ~N \times M~ có ~K~ ô 'X', tìm hình chữ nhật có diện tích lớn nhất chứa đúng một ô 'X'.
Sub 1: Vét cạn — ~O(N^2 M^2)~, dùng khi ~N, M \le 50~
Duyệt mọi hình chữ nhật, đếm số 'X' bên trong bằng tổng tiền tố 2 chiều, lấy diện tích lớn nhất trong những hình có đúng 1 'X'. Nếu chỉ nộp sub này: đúng 11/20 test.
Sub 2: Cố định cặp dòng — ~O(N^2 M)~, dùng khi ~N, M \le 500~
Cố định dòng trên ~t~ và dòng dưới ~b~, đếm số 'X' của mỗi cột trong các dòng ~t..b~. Với mỗi cột có đúng một 'X', hình chữ nhật rộng nhất chứa cột đó bị chặn bởi hai cột có 'X' gần nhất ở hai bên, nên chiều rộng là hiệu hai cột đó trừ 1. Nếu chỉ nộp sub này: đúng 15/20 test.
Sub 3: Duyệt theo từng ô X — phụ thuộc ~K~, không phụ thuộc ~N \cdot M~
Với mỗi ô 'X' tại ~(r, c)~ cần tìm hình chữ nhật lớn nhất chứa nó mà không chứa ô 'X' khác. 'X' khác cùng dòng đặt giới hạn cột cố định; 'X' khác cùng cột chặn mép trên và mép dưới; 'X' phía trên chỉ ảnh hưởng khi mép trên ~t~ không lớn hơn dòng của nó (thu hẹp cột trái hoặc phải), tương tự với phía dưới. Mép ~t~ chỉ cần thử các giá trị (dòng của một ô X phía trên) + 1, mép ~b~ chỉ cần thử (dòng của một ô X phía dưới) - 1; với mỗi cặp tính diện tích. Nộp riêng sub này đúng 20/20 test (trường hợp xấu nhất có thể tới ~O(K^3)~ phép tính rất nhẹ nên vẫn chạy kịp ~K \le 1000~).
Chương trình hoàn chỉnh
Hàm ~main~ đọc dữ liệu từ file; ~N, M \le 50~ gọi sub1, ~N, M \le 500~ gọi sub2, còn lại gọi sub3. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước. Chương trình đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int N, M, K;
vector<pair<int,int>> pts; // các ô 'X' dạng (dòng, cột), đã sắp theo dòng
// Sub 1: vét cạn mọi hình chữ nhật, đếm số X bằng tổng tiền tố 2 chiều, O(N^2 M^2), dùng khi N, M <= 50
void sub1() {
vector<vector<int>> s(N + 1, vector<int>(M + 1, 0));
for (auto &p : pts) s[p.first][p.second]++;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++)
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
long long best = 0;
for (int r1 = 1; r1 <= N; r1++)
for (int r2 = r1; r2 <= N; r2++)
for (int c1 = 1; c1 <= M; c1++)
for (int c2 = c1; c2 <= M; c2++) {
int x = s[r2][c2] - s[r1 - 1][c2] - s[r2][c1 - 1] + s[r1 - 1][c1 - 1];
if (x == 1) best = max(best, (long long)(r2 - r1 + 1) * (c2 - c1 + 1));
}
cout << best << "\n";
}
// Sub 2: cố định cặp dòng (t, b), đếm số X mỗi cột, rồi tìm đoạn cột rộng nhất chứa đúng 1 X trong O(M).
// Tổng O(N^2 M), dùng khi N, M <= 500
void sub2() {
vector<vector<int>> byRow(N + 1);
for (auto &p : pts) byRow[p.first].push_back(p.second);
long long best = 0;
vector<int> cnt(M + 2);
for (int t = 1; t <= N; t++) {
fill(cnt.begin(), cnt.end(), 0);
for (int b = t; b <= N; b++) {
for (int c : byRow[b]) cnt[c]++;
// gom các cột có X (thêm biên 0 và M+1); cột có đúng 1 X được chọn, biên là cột có X gần nhất hai bên
vector<int> cols;
cols.push_back(0);
for (int c = 1; c <= M; c++) if (cnt[c]) cols.push_back(c);
cols.push_back(M + 1);
for (size_t i = 1; i + 1 < cols.size(); i++)
if (cnt[cols[i]] == 1)
best = max(best, (long long)(b - t + 1) * (cols[i + 1] - cols[i - 1] - 1));
}
}
cout << best << "\n";
}
// Sub 3: theo từng ô X (K <= 1000). Với mỗi X tại (r, c), ta mở rộng hình chữ nhật chứa nó:
// - X cùng dòng tạo giới hạn cột cố định; X cùng cột chặn mép trên/dưới.
// - X ở phía trên (dòng < r) chỉ ảnh hưởng khi mép trên t <= dòng đó, thu hẹp cột trái/phải.
// - Tương tự X ở phía dưới với mép dưới b.
// Thử các mép t là các giá trị (dòng X phía trên + 1) và b là (dòng X phía dưới - 1).
void sub3() {
int K2 = pts.size();
long long best = 0;
for (int p = 0; p < K2; p++) {
int r = pts[p].first, c = pts[p].second;
int L0 = 0, R0 = M + 1, tmin = 1, bmax = N;
vector<pair<int,int>> up, down; // (dòng, cột); up sắp giảm dần theo dòng, down tăng dần
for (int q = 0; q < K2; q++) {
if (q == p) continue;
int x = pts[q].first, y = pts[q].second;
if (x == r) {
if (y < c) L0 = max(L0, y); else R0 = min(R0, y);
} else if (y == c) {
if (x < r) tmin = max(tmin, x + 1); else bmax = min(bmax, x - 1);
}
}
for (int q = 0; q < K2; q++) {
if (q == p) continue;
int x = pts[q].first, y = pts[q].second;
if (y == c || x == r) continue;
if (x < r && x >= tmin) up.push_back({x, y});
if (x > r && x <= bmax) down.push_back({x, y});
}
sort(up.begin(), up.end(), [](auto &u, auto &v) { return u.first > v.first; });
sort(down.begin(), down.end());
// các giá trị t ứng viên giảm dần: r (nếu cần), x+1 cho mỗi X phía trên, và tmin
vector<int> ts, bs;
for (auto &u : up) ts.push_back(u.first + 1);
ts.push_back(tmin);
for (auto &d : down) bs.push_back(d.first - 1);
bs.push_back(bmax);
// ts giảm dần (có thể lặp), bs tăng dần
int iu = 0;
int Lu = L0, Ru = R0;
for (int t : ts) {
// nạp các X phía trên có dòng >= t
while (iu < (int)up.size() && up[iu].first >= t) {
if (up[iu].second < c) Lu = max(Lu, up[iu].second);
else Ru = min(Ru, up[iu].second);
iu++;
}
if (t > r) continue;
int id = 0, Ld = Lu, Rd = Ru;
for (int b : bs) {
if (b < r) continue;
while (id < (int)down.size() && down[id].first <= b) {
if (down[id].second < c) Ld = max(Ld, down[id].second);
else Rd = min(Rd, down[id].second);
id++;
}
best = max(best, (long long)(b - t + 1) * (Rd - Ld - 1));
}
}
}
cout << best << "\n";
}
int main() {
freopen("hcn.inp", "r", stdin);
freopen("hcn.out", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> N >> M >> K;
pts.resize(K);
for (auto &p : pts) cin >> p.first >> p.second;
sort(pts.begin(), pts.end());
if (N <= 50 && M <= 50) sub1();
else if (N <= 500 && M <= 500) sub2();
else sub3();
return 0;
}
Bình luận