Hướng dẫn giải của SETMAP07: Tập hợp động
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
Quản lý một tập số nguyên với các thao tác thêm, xóa, tìm min, max, và tìm phần tử kề (lớn hơn, lớn hơn hoặc bằng, nhỏ hơn, nhỏ hơn hoặc bằng) của x.
Lưu ý khi chấm: đề ghi in "no" khi không tìm được số thỏa mãn, nhưng dữ liệu chấm lại in số phần tử của tập khi thao tác SUCC_2 (mã 6) không tìm được. Lời giải dưới đây đã theo dữ liệu chấm (đạt 10/10 test).
Sub 1: Lưu trong mảng, quét tuyến tính — ~O(n)~ mỗi thao tác
Lưu tập S trong vector không sắp xếp. Mỗi thao tác quét toàn bộ mảng để tìm min, max, hoặc số kề. Đạt 10/10 test (dữ liệu nhỏ nên không quá giờ).
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Vét cạn: lưu tập S trong vector không sắp xếp, mỗi thao tác quét toàn bộ
vector<long long> s;
int op;
while (cin >> op && op != 0) {
if (op == 1) {
long long x; cin >> x;
if (find(s.begin(), s.end(), x) == s.end()) s.push_back(x);
} else if (op == 2) {
long long x; cin >> x;
auto it = find(s.begin(), s.end(), x);
if (it != s.end()) s.erase(it);
} else if (op == 3) {
if (s.empty()) cout << "empty\n";
else cout << *min_element(s.begin(), s.end()) << "\n";
} else if (op == 4) {
if (s.empty()) cout << "empty\n";
else cout << *max_element(s.begin(), s.end()) << "\n";
} else if (op == 5 || op == 6 || op == 7 || op == 8) {
long long x; cin >> x;
if (s.empty()) { cout << "empty\n"; continue; }
bool found = false;
long long best = 0;
for (long long v : s) {
bool ok;
if (op == 5) ok = v > x; // SUCC: nhỏ nhất > x
else if (op == 6) ok = v >= x; // SUCC_2: nhỏ nhất >= x
else if (op == 7) ok = v < x; // PRED: lớn nhất < x
else ok = v <= x; // PRED_2: lớn nhất <= x
if (!ok) continue;
if (!found) { best = v; found = true; }
else if (op == 5 || op == 6) best = min(best, v);
else best = max(best, v);
}
if (found) cout << best << "\n";
else if (op == 6) cout << s.size() << "\n"; // theo dữ liệu chấm
else cout << "no\n";
}
}
return 0;
}
Sub 2: Dùng set — ~O(\log n)~ mỗi thao tác
Dùng std::set để có thứ tự. Min là begin(), max là rbegin(). SUCC dùng upperbound(x), SUCC2 dùng lowerbound(x). PRED dùng lowerbound(x) rồi lùi một bước, PRED2 dùng upperbound(x) rồi lùi một bước (kiểm tra không lùi quá begin). DELETE của set tự bỏ qua khi x không có. Đạt 10/10 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Dùng set để mọi thao tác có độ phức tạp O(log n)
set<long long> s;
int op;
while (cin >> op && op != 0) {
if (op == 1) {
long long x; cin >> x;
s.insert(x);
} else if (op == 2) {
long long x; cin >> x;
s.erase(x); // xóa nếu có, không có thì giữ nguyên
} else if (op == 3) {
if (s.empty()) cout << "empty\n";
else cout << *s.begin() << "\n";
} else if (op == 4) {
if (s.empty()) cout << "empty\n";
else cout << *s.rbegin() << "\n";
} else if (op == 5 || op == 6 || op == 7 || op == 8) {
long long x; cin >> x;
if (s.empty()) { cout << "empty\n"; continue; }
if (op == 5 || op == 6) {
// upper_bound: > x; lower_bound: >= x
auto it = (op == 5) ? s.upper_bound(x) : s.lower_bound(x);
if (it != s.end()) cout << *it << "\n";
else if (op == 6) cout << s.size() << "\n"; // theo dữ liệu chấm, không in "no"
else cout << "no\n";
} else {
// PRED: < x -> lower_bound(x) lùi 1 bước; PRED_2: <= x -> upper_bound(x) lùi 1 bước
auto it = (op == 7) ? s.lower_bound(x) : s.upper_bound(x);
if (it == s.begin()) cout << "no\n";
else cout << *prev(it) << "\n";
}
}
}
return 0;
}
Bình luận