Hướng dẫn giải của [Beginner Free Contest 08] TABLEDEL
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
Ô đen không bao giờ bị xóa, nên hàng và cột chứa ô đen luôn còn lại. Một hàng (cột) chỉ bị xóa khi không có ô đen nào. Đáp án là số hàng có ô đen nhân với số cột có ô đen.
Sub 1: Mô phỏng — dùng khi ~n, m \le 100~
Lưới được lưu trực tiếp. Lặp lại việc xóa mọi hàng và cột toàn trắng cho đến khi không còn xóa được. Đáp án là số hàng nhân số cột còn lại.
Nếu chỉ nộp sub này: đúng 5/10 test.
Sub 2: Đếm hàng và cột — ~O(k\log k)~
Đếm số hàng khác nhau và số cột khác nhau trong các ô đen, rồi nhân lại.
Nếu chỉ nộp sub này: đúng 10/10 test.
Chương trình hoàn chỉnh
Chương trình đọc n, m, k và các ô đen. Nếu n, m \le 100 gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n, m, k;
vector<pair<int, int>> blk; // cac o den
// Nhan xet: o den khong bao gio bi xoa, nen hang co o den va cot co o den luon con.
// Hang khong co o den la hang trang, co the xoa; cot tuong tu. Dap an = (so hang co den) * (so cot co den).
// Sub 1: mo phong truc tiep (n, m <= 100): xoa lien tuc cac hang / cot trang cho den khi khong xoa duoc nua
long long sub1() {
vector<vector<int>> g(n, vector<int>(m, 0));
for (auto &p : blk) g[p.first - 1][p.second - 1] = 1;
bool changed = true;
while (changed) {
changed = false;
for (int i = (int)g.size() - 1; i >= 0; i--) {
bool white = true;
for (int v : g[i]) if (v) { white = false; break; }
if (white) {
g.erase(g.begin() + i);
changed = true;
}
}
int cols = g.empty() ? 0 : (int)g[0].size();
for (int j = cols - 1; j >= 0; j--) {
bool white = true;
for (auto &row : g) if (row[j]) { white = false; break; }
if (white) {
for (auto &row : g) row.erase(row.begin() + j);
changed = true;
}
}
}
long long r = (long long)g.size();
long long c = g.empty() ? 0 : (long long)g[0].size();
return r * c;
}
// Sub 2: dem so hang va so cot co it nhat mot o den, dap an la tich. O(k log k)
long long sub2() {
set<int> rows, cols;
for (auto &p : blk) {
rows.insert(p.first);
cols.insert(p.second);
}
return (long long)rows.size() * (long long)cols.size();
}
int main() {
cin >> n >> m >> k;
blk.resize(k);
for (int i = 0; i < k; i++) cin >> blk[i].first >> blk[i].second;
if (n <= 100 && m <= 100) cout << sub1() << "\n";
else cout << sub2() << "\n";
return 0;
}
Bình luận