Hướng dẫn giải của [VT Thiếu nhi] BÀI 02: EQUAL
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
Đếm số cặp chỉ số ~(i, j)~ với ~i < j~ và ~a_i = a_j~. Đáp số có thể lớn nên dùng số nguyên 64 bit.
Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 5000~
Thử mọi cặp ~(i, j)~ và đếm cặp bằng nhau. Bộ test chấm đều có ~n \ge 21000~ nên sub này không ăn được test nào (0/20), nhưng đúng với ví dụ trong đề.
Sub 2: Đếm theo giá trị — ~O(n)~
Duyệt từng số, cộng vào đáp số số lần giá trị đó đã xuất hiện trước đó, rồi tăng bộ đếm. Đúng với mọi test (20/20).
Chương trình hoàn chỉnh
Chương trình đọc ~n~ và dãy; nếu ~n \le 5000~ gọi sub1, còn lại gọi sub2.
Chương trình đầy đủ đúng 20/20 test; vì mọi test đều lớn hơn miền của sub 1 nên sub 1 được kiểm tra bằng ví dụ trong đề.
#include <bits/stdc++.h>
using namespace std;
int n;
int a[100005];
int cnt[1000005]; // cnt[v] = so lan gia tri v da xuat hien (a_i <= 10^6)
// Sub 1: vet can. Thu moi cap (i, j) voi i < j, dem cac cap co a_i = a_j. O(n^2)
// Dung khi n <= 5000
void sub1() {
long long ans = 0;
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
if (a[i] == a[j]) ans++;
cout << ans << "\n";
}
// Sub 2: day du. Duyet tung so: so cap moi tao ra voi cac vi tri truoc do chinh la so lan
// gia tri do da xuat hien. O(n).
void sub2() {
long long ans = 0;
for (int i = 1; i <= n; i++) {
ans += cnt[a[i]];
cnt[a[i]]++;
}
cout << ans << "\n";
}
int main() {
freopen("EQUAL.INP", "r", stdin);
freopen("EQUAL.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
if (n <= 5000) sub1();
else sub2();
return 0;
}
Bình luận