Hướng dẫn giải của [Free Contest 01] KINGDOMDEFENSE
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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
Tháp bảo vệ cả hàng lẫn cột của nó, nên hình chữ nhật không bị bảo vệ không được chứa cột nào có tháp và hàng nào có tháp. Đáp án là tích của khoảng trống lớn nhất giữa các cột và giữa các hàng.
Sub 1: Vét cạn trên lưới — ~O(w^2 h)~, dùng khi ~w, h \le 200~
Với mỗi cặp cột ~x_1 \le x_2~, đánh dấu các hàng bị chặn, rồi tìm đoạn hàng liên tiếp không bị chặn dài nhất. Diện tích là độ dài đoạn nhân số cột.
Nếu chỉ nộp sub này: đúng 35/48 test.
Sub 2: Khoảng trống lớn nhất — ~O(n\log n)~
Sắp xếp hoành độ các tháp, thêm mốc 0 và ~w+1~; khoảng trống lớn nhất là hiệu hai mốc liên tiếp trừ 1. Làm tương tự với tung độ. Đáp án là tích hai khoảng trống (có thể lên tới khoảng ~1.6\cdot 10^9~, dùng số 64 bit).
Nếu chỉ nộp sub này: đúng 48/48 test.
Chương trình hoàn chỉnh
Chương trình đọc w, h, n và các tháp. Nếu w, h \le 200 gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int w, h, n;
vector<int> tx, ty; // toa do x, y cua cac thap
// Nhan xet: thap o (x, y) bao ve ca cot x va ca hang y.
// Hinh chu nhat khong bi bao ve phai khong chua cot nao co thap, va khong chua hang nao co thap.
// Sub 1: duyet hai cot x1..x2, danh dau hang bi cham, tim doan hang lien tiep tot dai nhat. O(w^2 * h). Dung khi w, h <= 200
long long sub1() {
vector<char> colHas(w + 2, 0), rowHas(h + 2, 0);
for (int i = 0; i < n; i++) {
colHas[tx[i]] = 1;
rowHas[ty[i]] = 1;
}
long long best = 0;
for (int x1 = 1; x1 <= w; x1++) {
vector<char> bad(h + 2, 0);
for (int x2 = x1; x2 <= w; x2++) {
// cot x2 bi bao ve neu co thap o cot do; khi do moi o cot do deu bi bao ve
if (colHas[x2])
for (int y = 1; y <= h; y++) bad[y] = 1;
for (int y = 1; y <= h; y++) if (rowHas[y]) bad[y] = 1;
int run = 0;
for (int y = 1; y <= h; y++) {
if (!bad[y]) {
run++;
best = max(best, (long long)run * (x2 - x1 + 1));
} else {
run = 0;
}
}
}
}
return best;
}
// Sub 2: hinh chu nhat lon nhat = (khoang trong lon nhat giua cac cot co thap) * (khoang trong lon nhat giua cac hang co thap)
long long maxGap(vector<int> v, int len) {
v.push_back(0);
v.push_back(len + 1);
sort(v.begin(), v.end());
long long g = 0;
for (size_t i = 1; i < v.size(); i++)
g = max(g, (long long)(v[i] - v[i - 1] - 1));
return g;
}
long long sub2() {
return maxGap(tx, w) * maxGap(ty, h);
}
int main() {
cin >> w >> h >> n;
tx.resize(n);
ty.resize(n);
for (int i = 0; i < n; i++) cin >> tx[i] >> ty[i];
if (w <= 200 && h <= 200) cout << sub1() << "\n";
else cout << sub2() << "\n";
return 0;
}
Bình luận