Hướng dẫn giải của Dãy số (TS 10 chuyên Ninh Bình 2022)
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
Cần đếm số cặp vị trí ~(i, j)~ với ~i < j~ mà ~A_i \ne A_j~. Dữ liệu có ~N \le 10^6~ nên kết quả có thể lên tới khoảng ~5 \cdot 10^{11}~, phải dùng long long.
Sub 1: Vét cạn — ~O(N^2)~, dùng khi ~N \le 5000~
Xét mọi cặp ~(i, j)~ với ~i < j~, nếu ~A_i \ne A_j~ thì tăng bộ đếm. Nếu chỉ nộp sub này: đúng 31/40 test (đúng hết các test trong miền, 9 test lớn bị quá giờ).
Sub 2: Đếm tần suất — ~O(N + V)~ với ~V = 10^6~
Ý tưởng: tổng số cặp là ~N(N-1)/2~. Từ tổng này, trừ đi số cặp có giá trị giống nhau. Nếu một giá trị xuất hiện ~c~ lần thì có ~c(c-1)/2~ cặp giống nhau.
Bẫy cần chú ý: không dùng map vì với gần ~10^6~ giá trị khác nhau nó bị quá giờ; dùng mảng đếm vì giá trị không quá ~10^6~. Tính ~N(N-1)/2~ bằng long long để tránh tràn số.
Nếu chỉ nộp sub này: đúng 40/40 test.
Chương trình hoàn chỉnh
main đọc dãy. Nếu ~N \le 5000~ thì gọi sub1, còn lại gọi sub2. Đầu main có freopen vì máy chấm đọc/ghi file DS.INP, DS.OUT.
#include <bits/stdc++.h>
using namespace std;
int n;
long long a[1000005]; // day A dung chung cho cac sub
// Sub 1: vet can O(N^2) - xet moi cap (i, j) va dem cap co gia tri khac nhau
void sub1() {
long long cnt = 0;
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
if (a[i] != a[j]) cnt++;
cout << cnt << "\n";
}
// Sub 2: dem tan suat moi gia tri. Tong so cap = N(N-1)/2, tru di cac cap giong nhau.
// Cap giong nhau trong nhom co c phan tu la c(c-1)/2.
void sub2() {
static int freq[1000005]; // gia tri <= 10^6 nen dung mang dem, nhanh hon map
for (int i = 1; i <= n; i++) freq[a[i]]++;
long long total = (long long)n * (n - 1) / 2; // dung long long de khong tran so
for (int v = 0; v <= 1000000; v++) {
long long c = freq[v];
total -= c * (c - 1) / 2;
}
cout << total << "\n";
}
int main() {
freopen("DS.INP", "r", stdin); // may cham doc/ghi file
freopen("DS.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
// Du lieu nho (N <= 5000): sub1 vet can; du lieu lon: sub2 dem tan suat
if (n <= 5000) sub1();
else sub2();
return 0;
}
Bình luận