Hướng dẫn giải của Rừng cây sồ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.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhậpTác giả: , , ,
Hiểu bài toán
Bài toán yêu cầu đếm số lượng cây sồi bị chặt hạ khi xây dựng một đường đi hình chữ nhật. Chỉ những cây nằm trên bốn cạnh của hình chữ nhật (cạnh trên, cạnh dưới, cạnh trái, cạnh phải) mới bị chặt. Hình chữ nhật được đặc tả bởi tọa độ hai góc (X1, Y1) là góc dưới bên trái và (X2, Y2) là góc trên bên phải, với điều kiện X1 < X2 và Y1 < Y2. Với mỗi truy vấn, ta cần xuất ra số cây nằm trên đường biên của hình chữ nhật đó.
Quy tắc xác định cây bị chặt:
- Cây nằm trên cạnh dưới (y = Y1 và X1 <= x <= X2).
- Cây nằm trên cạnh trên (y = Y2 và X1 <= x <= X2).
- Cây nằm trên cạnh trái (x = X1 và Y1 <= y <= Y2).
- Cây nằm trên cạnh phải (x = X2 và Y1 <= y <= Y2).
Lưu ý: Các góc của hình chữ nhật (nếu có cây) sẽ được tính vào cả hai cạnh kề nhau. Tuy nhiên, trong các giải pháp accepted, việc xử lý thường tập trung vào các cạnh riêng biệt.
Các cách tiếp cận
Cách Brute Force
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<pair<int, int>> trees(n);
for(int i = 0; i < n; i++) {
cin >> trees[i].first >> trees[i].second;
}
int p;
cin >> p;
while(p--) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
int cnt = 0;
for(int i = 0; i < n; i++) {
int x = trees[i].first;
int y = trees[i].second;
// Kiểm tra xem cây có nằm trên 4 cạnh không
bool on_bottom = (y == y1 && x >= x1 && x <= x2);
bool on_top = (y == y2 && x >= x1 && x <= x2);
bool on_left = (x == x1 && y >= y1 && y <= y2);
bool on_right = (x == x2 && y >= y1 && y <= y2);
if (on_bottom || on_top || on_left || on_right) {
cnt++;
}
}
cout << cnt << "\n";
}
return 0;
}
- Time Complexity: O(N * P)
- Space Complexity: O(N)
Đây là cách tiếp cận trực quan nhất. Với mỗi truy vấn, ta duyệt qua tất cả N cây và kiểm tra xem cây đó có nằm trên bất kỳ cạnh nào của hình chữ nhật hay không. Phương pháp này rất dễ hiểu và dễ cài đặt. Tuy nhiên, do N và P có thể lên tới 300,000 và 100,000 tương ứng, độ phức tạp O(N * P) sẽ khiến chương trình chạy quá thời gian (Time Limit Exceeded). Nó chỉ khả thi với các test có N và P rất nhỏ (khoảng 1000).
Cách Hash Map theo Tọa độ
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
// Sử dụng map để lưu trữ các cây theo tọa độ x và y
unordered_map<int, vector<int>> rows, cols;
for(int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
rows[y].push_back(x);
cols[x].push_back(y);
}
// Sắp xếp các tọa độ để có thể dùng binary search
for(auto &p : rows) sort(p.second.begin(), p.second.end());
for(auto &p : cols) sort(p.second.begin(), p.second.end());
int p;
cin >> p;
while(p--) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
long long cnt = 0;
// Cạnh dưới (y = y1, x từ x1 đến x2)
if (rows.count(y1)) {
const auto &v = rows[y1];
cnt += upper_bound(v.begin(), v.end(), x2) - lower_bound(v.begin(), v.end(), x1);
}
// Cạnh trên (y = y2, x từ x1 đến x2)
if (rows.count(y2)) {
const auto &v = rows[y2];
cnt += upper_bound(v.begin(), v.end(), x2) - lower_bound(v.begin(), v.end(), x1);
}
// Cạnh trái (x = x1, y từ y1 đến y2)
if (cols.count(x1)) {
const auto &v = cols[x1];
cnt += upper_bound(v.begin(), v.end(), y2) - lower_bound(v.begin(), v.end(), y1);
}
// Cạnh phải (x = x2, y từ y1 đến y2)
if (cols.count(x2)) {
const auto &v = cols[x2];
cnt += upper_bound(v.begin(), v.end(), y2) - lower_bound(v.begin(), v.end(), y1);
}
cout << cnt << "\n";
}
return 0;
}
- Time Complexity: O(N log N + P log N)
- Space Complexity: O(N)
Cách tiếp cận này tối ưu hóa bằng cách phân nhóm các cây.
- Tạo hai bảng băm (hash map):
rowslưu các tọa độ x của cây cho mỗi y, vàcolslưu các tọa độ y của cây cho mỗi x. - Sau khi nhập xong N cây, ta sắp xếp các vector bên trong map để chuẩn bị cho việc tìm kiếm nhị phân.
- Với mỗi truy vấn:
- Cạnh dưới: Kiểm tra xem có cây nào ở tọa độ y = Y1 không. Nếu có, dùng binary search để đếm số cây có x nằm trong [X1, X2].
- Tương tự cho cạnh trên (y = Y2).
- Cạnh trái: Kiểm tra xem có cây nào ở x = X1 không. Đếm số cây có y trong [Y1, Y2].
- Cạnh phải: Tương tự. Độ phức tạp là O(N log N) để sort và O(log N) cho mỗi truy vấn (với 4 lần binary search). Tổng cộng O(P log N). Với N=300,000 và P=100,000, phương pháp này chạy khá nhanh (khoảng 10^6 - 10^7 thao tác).
Cách Binary Search trên Mảng Toàn cục (Global Sorted Array)
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
// Hàm đếm số điểm có tọa độ x cố định và y trong khoảng [y1, y2]
// Sử dụng cho cạnh trái và phải
int count_on_vertical(const vector<ii>& points, int x, int y1, int y2) {
// Tạo phantom point để tìm kiếm
// lower_bound tìm điểm đầu tiên >= (x, y1)
auto it1 = lower_bound(points.begin(), points.end(), make_pair(x, y1));
// upper_bound tìm điểm đầu tiên > (x, y2)
auto it2 = upper_bound(points.begin(), points.end(), make_pair(x, y2));
// Chỉ tính các điểm thực sự có tọa độ x
// lower_bound đã đảm bảo x >= x. Ta cần kiểm tra x == x
// Tuy nhiên, do sắp xếp theo pair, các điểm cùng x sẽ nằm cạnh nhau.
// Hàm này được viết để đếm chính xác.
// Nhưng trong sol1, tác giả dùng Q_rev.
// Để đơn giản và đúng với logic sol1:
return it2 - it1;
}
// Hàm đếm số điểm có tọa độ y cố định và x trong khoảng [x1, x2]
int count_on_horizontal(vector<ii>& points, int y, int x1, int x2) {
// Tạo vector chứa (y, x) để query
// Hoặc đơn giản là sort points theo (y, x)
// Để giải quyết tổng quát, ta có thể dùng 2 mảng: một sort theo (x,y), một sort theo (y,x)
return 0; // Placeholder
}
int main() {
int n;
cin >> n;
vector<ii> X(n); // Sort by x, then y
vector<ii> Y(n); // Sort by y, then x
for(int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
X[i] = {x, y};
Y[i] = {y, x};
}
sort(X.begin(), X.end());
sort(Y.begin(), Y.end());
int p;
cin >> p;
while(p--) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
long long cnt = 0;
// 1. Cạnh dưới (y = y1, x từ x1 -> x2)
// Dùng mảng Y (sort by y)
// Tìm đoạn trong Y có y = y1 và x trong [x1, x2]
auto it_low_y1 = lower_bound(Y.begin(), Y.end(), make_pair(y1, x1));
auto it_high_y1 = upper_bound(Y.begin(), Y.end(), make_pair(y1, x2));
// Lọc ra các điểm có y == y1 là việc của lower/upper bound
// Nhưng upper_bound(make_pair(y1, x2)) sẽ dừng ở điểm có y > y1 hoặc y==y1 và x > x2
// Vậy:
cnt += it_high_y1 - it_low_y1;
// 2. Cạnh trên (y = y2, x từ x1 -> x2)
auto it_low_y2 = lower_bound(Y.begin(), Y.end(), make_pair(y2, x1));
auto it_high_y2 = upper_bound(Y.begin(), Y.end(), make_pair(y2, x2));
cnt += it_high_y2 - it_low_y2;
// 3. Cạnh trái (x = x1, y từ y1 -> y2)
// Dùng mảng X (sort by x)
auto it_low_x1 = lower_bound(X.begin(), X.end(), make_pair(x1, y1));
auto it_high_x1 = upper_bound(X.begin(), X.end(), make_pair(x1, y2));
cnt += it_high_x1 - it_low_x1;
// 4. Cạnh phải (x = x2, y từ y1 -> y2)
auto it_low_x2 = lower_bound(X.begin(), X.end(), make_pair(x2, y1));
auto it_high_x2 = upper_bound(X.begin(), X.end(), make_pair(x2, y2));
cnt += it_high_x2 - it_low_x2;
cout << cnt << "\n";
}
return 0;
}
- Time Complexity: O(N log N + P log N)
- Space Complexity: O(N)
Đây là phiên bản khá tương đồng với Solution 1 của Yukino.
- Tạo hai mảng chứa tọa độ các cây: một mảng sort theo (x, y) và một mảng sort theo (y, x).
- Với mỗi truy vấn, ta thực hiện 4 câu hỏi range count:
- Cạnh dưới: Tìm trong mảng sort theo (y, x) các điểm có y = Y1 và x nằm trong [X1, X2].
- Cạnh trên: Tìm trong mảng sort theo (y, x) các điểm có y = Y2 và x nằm trong [X1, X2].
- Cạnh trái: Tìm trong mảng sort theo (x, y) các điểm có x = X1 và y nằm trong [Y1, Y2].
- Cạnh phải: Tìm trong mảng sort theo (x, y) các điểm có x = X2 và y nằm trong [Y1, Y2].
Việc tìm kiếm được thực hiện bằng
lower_boundvàupper_bound. Ví dụ cho cạnh dưới:lower_boundtìm điểm đầu tiên có (y, x) >= (Y1, X1).upper_boundtìm điểm đầu tiên có (y, x) > (Y1, X2). Khoảng cách giữa chúng chính là số điểm thỏa mãn. Độ phức tạp tương tự cách Hash Map, nhưng tránh được overhead của Hash Map và thường chạy ổn định hơn. Đây là phương pháp tối ưu được chấp nhận (Accepted) trong kỳ thi.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(N * P) | O(N) | Brute Force |
| 2 | O(N log N + P log N) | O(N) | Hash Map theo Tọa độ |
| 3 | O(N log N + P log N) | O(N) | Binary Search trên Mảng Toàn cục (Global Sorted Array) |
Bài học kinh nghiệm
- Bài toán quy về bài toán đếm số lượng điểm (cây) nằm trên các đoạn thẳng nằm ngang hoặc dọc (cạnh của hình chữ nhật).
- Sử dụng Binary Search (lowerbound, upperbound) trên mảng đã được sắp xếp để đếm số lượng phần tử trong một khoảng giá trị là chìa khóa để đạt hiệu năng cao.
- Cần tách biệt các truy vấn theo hai chiều (X và Y) để tận dụng tối đa việc sắp xếp.
Lỗi thường gặp
- Lỗi logic khi tính toán các cạnh: Ví dụ, nhầm lẫn giữa 'lớn hơn hoặc bằng' và 'lớn hơn', dẫn đến đếm thiếu hoặc đếm thừa các điểm ở biên.
- Hiệu năng: Sử dụng
unordered_mapvới dữ liệu lớn có thể gây tràn bộ nhớ hoặc chậm do va chạm hash (hash collision) nếu không tối ưu tốt. Sử dụng mảng và sort thường an toàn hơn. - Xử lý truy vấn quá chậm: Nếu không dùng binary search mà dùng scanline hoặc duyệt mảng, sẽ bị TLE.
Bình luận