Hướng dẫn giải của LIST18: Dãy đã sắp xếp theo số ước
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
Sắp xếp dãy theo số ước của mỗi số (tăng dần). Với số âm, đếm ước của trị tuyệt đối. Hai số cùng số ước thì giữ nguyên thứ tự ban đầu (sắp xếp ổn định).
Sub 1: Đếm ước từng số — ~O(n \sqrt{M} + n \log n)~, dùng khi ~n \le 1000~
Đếm số ước của mỗi số bằng thử chia, ghép thành cặp (số ước, giá trị), rồi sắp xếp ổn định (stable_sort) chỉ theo số ước.
Sub 2: Sàng số ước — ~O(M \log M + n \log n)~, dùng khi các trường hợp còn lại
Sàng số ước đến ~M = \max|A_i|~ rồi stable_sort theo số ước như trên.
Chương trình hoàn chỉnh
Đề không chia subtask. Lưu ý: khi hai số có cùng số ước thì phải giữ nguyên thứ tự như trong dãy ban đầu, nên dùng stable_sort (sắp xếp ổn định) chứ không dùng sort thường.
Chương trình đọc ~n~ và dãy. Nếu ~n \le 1000~ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> a;
// So uoc duong cua |x| (bang thu chia). Dung cho sub 1.
long long demUoc(long long x) {
if (x < 0) x = -x;
if (x == 0) return 0;
long long c = 0;
for (long long d = 1; d * d <= x; d++)
if (x % d == 0) {
c++;
if (d * d != x) c++;
}
return c;
}
// Sub 1: tinh so uoc tung so bang thu chia, roi sap xep. Dung khi n <= 1000
void sub1() {
vector<pair<long long, long long>> v(n); // (so uoc, gia tri)
for (int i = 0; i < n; i++) v[i] = make_pair(demUoc(a[i]), a[i]);
stable_sort(v.begin(), v.end(), [](const pair<long long,long long>& x, const pair<long long,long long>& y) { return x.first < y.first; }); // theo so uoc tang dan, bang nhau giu nguyen thu tu (theo de)
for (int i = 0; i < n; i++) a[i] = v[i].second;
}
// Sub 2: sang so uoc den max|A| roi sap xep
void sub2() {
long long M = 1;
for (int i = 0; i < n; i++) M = max(M, llabs(a[i]));
vector<int> cnt(M + 1, 0);
for (long long d = 1; d <= M; d++)
for (long long m = d; m <= M; m += d) cnt[m]++;
vector<pair<long long, long long>> v(n);
for (int i = 0; i < n; i++) {
long long x = llabs(a[i]);
v[i] = make_pair(x == 0 ? 0 : (long long)cnt[x], a[i]);
}
stable_sort(v.begin(), v.end(), [](const pair<long long,long long>& x, const pair<long long,long long>& y) { return x.first < y.first; }); // theo so uoc tang dan, bang nhau giu nguyen thu tu (theo de)
for (int i = 0; i < n; i++) a[i] = v[i].second;
}
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();
for (int i = 0; i < n; i++) cout << a[i] << (i + 1 < n ? ' ' : '\n');
return 0;
}
Bình luận