Hướng dẫn cho Cắt bánh
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Tóm tắt đề bài
Cho một chiếc bánh hình chữ nhật kích thước \(M \times N\). Có \(K\) người thực hiện các nhát cắt, mỗi nhát cắt xác định một hình chữ nhật con bên trong chiếc bánh. Sau khi thực hiện xong tất cả \(K\) nhát cắt, hãy đếm xem chiếc bánh ban đầu bị chia thành bao nhiêu phần riêng biệt. Hai điểm thuộc cùng một phần nếu chúng không bị ngăn cách bởi bất kỳ đường biên nào của các nhát cắt.
Phân tích
- Kích thước: \(M, N\) có thể lên tới \(10^6\), nhưng số lượng nhát cắt \(K\) rất nhỏ (\(K \le 50\)).
- Bản chất bài toán: Mỗi nhát cắt tạo ra một vùng hình chữ nhật. Một điểm \((x, y)\) trên chiếc bánh sẽ bị ảnh hưởng bởi một tập hợp các nhát cắt nào đó. Hai điểm thuộc cùng một phần nếu chúng cùng nằm trong (hoặc cùng nằm ngoài) cùng một tập hợp các nhát cắt.
- Rời rạc hóa: Vì tọa độ \(M, N\) lớn nhưng số lượng các đường thẳng tạo nên các nhát cắt là ít (\(2K\) đường dọc và \(2K\) đường ngang), ta có thể sử dụng kỹ thuật rời rạc hóa tọa độ (Coordinate Compression) để đưa bài toán về lưới kích thước nhỏ (tối đa khoảng \(2K \times 2K\)).
Hướng giải quyết
1. Rời rạc hóa tọa độ
- Thu thập tất cả các tọa độ \(x\) từ các nhát cắt và các biên \(0, N\). Sắp xếp chúng và loại bỏ các giá trị trùng lặp. Tương tự với tọa độ \(y\) và các biên \(0, M\).
- Sau khi rời rạc hóa, ta có một lưới mới với số hàng và số cột tỉ lệ thuận với \(K\). Mỗi ô trong lưới mới này đại diện cho một vùng diện tích trên chiếc bánh ban đầu.
2. Biểu diễn trạng thái của mỗi ô
- Với mỗi ô \((i, j)\) trong lưới sau khi rời rạc hóa, ta cần biết nó thuộc những nhát cắt nào.
- Vì \(K \le 50\), ta có thể dùng một số nguyên 64-bit (
long longtrong C++) để làm một mặt nạ bit (bitmask). Bit thứ \(t\) được bật nếu ô đó nằm trong hình chữ nhật thứ \(t\). - Duyệt qua từng nhát cắt \(t \in [1, K]\), xác định phạm vi các ô trong lưới rời rạc bị bao phủ bởi nhát cắt này và cập nhật bitmask cho các ô đó:
a[i][j] |= (1LL << t).
3. Đếm số thành phần liên thông
- Sau khi đã có bitmask cho mọi ô, bài toán trở thành đếm số thành phần liên thông trên lưới.
- Hai ô kề cạnh nhau thuộc cùng một phần nếu và chỉ nếu chúng có cùng giá trị bitmask (nghĩa là chúng cùng nằm trong một tập hợp các nhát cắt giống hệt nhau).
- Sử dụng thuật toán tìm kiếm theo chiều rộng (BFS) hoặc chiều sâu (DFS) để duyệt qua các ô và đếm số vùng liên thông.
Độ phức tạp
- Rời rạc hóa: \(O(K \log K)\).
- Xây dựng lưới: \(O(K^2 \cdot K) = O(K^3)\) do duyệt qua \(K\) nhát cắt, mỗi nhát cắt phủ một vùng tối đa \((2K) \times (2K)\).
- BFS/DFS: \(O(K^2)\).
- Tổng quát: \(O(K^3)\), với \(K=50\) thì \(K^3 = 125,000\), hoàn toàn đáp ứng thời gian yêu cầu.
Code tham khảo
C++
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int N_MAX = 205; // Tối đa 2*K + biên
int m, n, k;
ll a[N_MAX][N_MAX];
bool visited[N_MAX][N_MAX];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};
struct Rect {
int x1, y1, x2, y2;
} rects[55];
void solve() {
vector<int> vx, vy;
vx.push_back(0); vx.push_back(n);
vy.push_back(0); vy.push_back(m);
for (int i = 1; i <= k; i++) {
cin >> rects[i].x1 >> rects[i].y1 >> rects[i].x2 >> rects[i].y2;
vx.push_back(rects[i].x1); vx.push_back(rects[i].x2);
vy.push_back(rects[i].y1); vy.push_back(rects[i].y2);
}
// Rời rạc hóa tọa độ
sort(vx.begin(), vx.end());
vx.erase(unique(vx.begin(), vx.end()), vx.end());
sort(vy.begin(), vy.end());
vy.erase(unique(vy.begin(), vy.end()), vy.end());
int nx = vx.size();
int ny = vy.size();
// Reset dữ liệu
for (int i = 0; i < nx; i++) {
for (int j = 0; j < ny; j++) {
a[i][j] = 0;
visited[i][j] = false;
}
}
// Đánh dấu bitmask cho từng ô trong lưới rời rạc
for (int t = 1; t <= k; t++) {
int x_start = lower_bound(vx.begin(), vx.end(), min(rects[t].x1, rects[t].x2)) - vx.begin();
int x_end = lower_bound(vx.begin(), vx.end(), max(rects[t].x1, rects[t].x2)) - vx.begin();
int y_start = lower_bound(vy.begin(), vy.end(), min(rects[t].y1, rects[t].y2)) - vy.begin();
int y_end = lower_bound(vy.begin(), vy.end(), max(rects[t].y1, rects[t].y2)) - vy.begin();
for (int i = x_start; i < x_end; i++) {
for (int j = y_start; j < y_end; j++) {
a[i][j] |= (1LL << (t - 1));
}
}
}
// BFS đếm số thành phần liên thông
int count = 0;
for (int i = 0; i < nx - 1; i++) {
for (int j = 0; j < ny - 1; j++) {
if (!visited[i][j]) {
count++;
queue<ii> q;
q.push({i, j});
visited[i][j] = true;
ll current_mask = a[i][j];
while (!q.empty()) {
ii u = q.front(); q.pop();
for (int step = 0; step < 4; step++) {
int ni = u.first + dx[step];
int nj = u.second + dy[step];
if (ni >= 0 && ni < nx - 1 && nj >= 0 && nj < ny - 1) {
if (!visited[ni][nj] && a[ni][nj] == current_mask) {
visited[ni][nj] = true;
q.push({ni, nj});
}
}
}
}
}
}
}
cout << count << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
while (cin >> m >> n && (m != 0 || n != 0)) {
cin >> k;
solve();
}
return 0;
}
Bình luận