Hướng dẫn giải của Cây cảnh (THCS KS1)
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
Đề yêu cầu in các loại cây (mã số khác nhau) theo thứ tự tăng dần, mỗi loại một lần.
Sub 1: Thêm dần có kiểm tra — ~O(n \cdot d)~, dùng khi ~n \le 1000~
Với mỗi mã, nếu chưa có trong danh sách kết quả thì thêm vào; cuối cùng sắp xếp.
Nếu chỉ nộp sub này: đúng 42/50 test.
Sub 2: Sắp xếp rồi loại trùng — ~O(n \log n)~
Sắp xếp toàn bộ dãy, dùng unique để loại các giá trị trùng.
Nếu chỉ nộp sub này: đúng 50/50 test.
Chương trình hoàn chỉnh
Dữ liệu ~n \le 1000~ dùng sub 1, còn lại dùng sub 2.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> a; // ma so cac cay canh
// Sub 1: vet can O(n^2). Moi cay them vao ket qua neu chua co, roi sap xep ket qua. Dung khi n <= 1000.
void sub1() {
vector<long long> res;
for (int i = 0; i < n; i++) {
bool found = false;
for (long long x : res)
if (x == a[i]) { found = true; break; }
if (!found) res.push_back(a[i]);
}
sort(res.begin(), res.end());
for (size_t i = 0; i < res.size(); i++)
cout << res[i] << (i + 1 == res.size() ? "\n" : " ");
}
// Sub 2: sap xep ca day roi lay cac gia tri khac nhau. O(n log n). Dung cho n lon.
void sub2() {
vector<long long> b = a;
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
for (size_t i = 0; i < b.size(); i++)
cout << b[i] << (i + 1 == b.size() ? "\n" : " ");
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
a.resize(n);
for (int i = 0; i < n; i++) cin >> a[i];
if (n <= 1000) sub1();
else sub2();
return 0;
}
Bình luận