Hướng dẫn giải của [Beginner Free Contest 11] HCN
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
Cho mảng 0/1 kích thước n × m (n, m ≤ 1000). Đếm số hình chữ nhật toàn số 1. Các hình không nghiêng và không chạm nhau, nên mỗi hình là một thành phần liên thông và chỉ có một góc trên-trái.
Sub 1: Tìm thành phần liên thông — ~O(n · m)~
Mỗi hình chữ nhật toàn số 1 là một thành phần liên thông, nên đếm số thành phần liên thông của các ô bằng 1. Duyệt từng ô chưa thăm; nếu là ô 1 thì tăng đếm và loang (DFS) để đánh dấu cả hình đó.
Kết quả chấm: 50/50 (SUB ok 50/50, TLE 0, WA 0)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m, 0));
for (auto &row : a)
for (auto &x : row) cin >> x;
// Moi hinh chu nhat toan so 1 la mot thanh phan lien thong (vi cac hinh khong cham nhau).
// Dem so thanh phan lien thong bang tim kiem theo chieu sau (DFS) tu moi o chua duoc tham.
vector<vector<int>> vis(n, vector<int>(m, 0));
int dem = 0;
int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
if (a[i][j] != 1 || vis[i][j]) continue;
dem++;
stack<pair<int, int>> st;
st.push({i, j});
vis[i][j] = 1;
while (!st.empty()) {
auto [r, c] = st.top(); st.pop();
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nc < 0 || nr >= n || nc >= m) continue;
if (a[nr][nc] == 1 && !vis[nr][nc]) {
vis[nr][nc] = 1;
st.push({nr, nc});
}
}
}
}
cout << dem << "\n";
return 0;
}
Sub 2: Đếm góc trên-trái — ~O(n · m)~
Vì các hình không chạm nhau nên mỗi hình có đúng một ô góc trên-trái có ô phía trên và ô bên trái đều bằng 0. Chỉ cần đếm các ô 1 thỏa mãn điều kiện này. Cách này không cần đánh dấu và ngắn gọn hơn.
Kết quả chấm: 50/50 (PASS 50/50)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m, 0));
for (auto &row : a)
for (auto &x : row) cin >> x;
// Cac hinh chu nhat khong cham nhau nen moi hinh co dung mot o goc tren-trai,
// va o do co o phia tren va o ben trai deu bang 0. Dem cac o 1 thoa dieu kien do.
long long dem = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
if (a[i][j] != 1) continue;
bool tren = (i == 0) || a[i - 1][j] == 0;
bool trai = (j == 0) || a[i][j - 1] == 0;
if (tren && trai) dem++;
}
cout << dem << "\n";
return 0;
}
Bình luận