Hướng dẫn giải của [Ninh Bình - TS10 - 2022] Bài 3: Dãy số
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.
Tác giả:
Subtask ~1~: ~3 \le N \le 5000~
Ở subtask này, ta sẽ duyệt tất cả các cặp phần tử tồn tại trong mảng ~a~ và tăng biến đếm nếu đó là cặp số khác nhau.
ĐPT: ~O~(~n^2~)
Subtask ~2 + 3~: ~10^4 \le N \le 10^6~
Để giải được subtask này, ta sẽ sử dụng nguyên lý bao hàm - loại trừ.
Ta có nhận xét như sau:
Số cặp phần tử trong mảng ~a~ chính là tổng các cặp số giống nhau và các cặp số khác nhau.
Vậy, thay vì ta tìm số cặp số khác nhau, ta chỉ cần tìm số cặp phần tử trong mảng và số cặp số giống nhau.
Dễ thấy:
- Số cặp phần tử trong mảng: ~\frac{N \times (N - 1)}{2}~.
- Số cặp số giống nhau:
- Do giới hạn ~a_i \le 10^6~, ta sử dụng mảng để đếm phân phối các phần tử trong mảng ~a~.
- Gọi số lần phần tử ~x~ xuất hiện trong mảng ~a~ là ~cnt_x~. Số cặp số giống nhau là ~\sum_{x=0}^{10^6}{\frac{cnt_x \times (cnt_x - 1)}{2}}~
Tất cả những công thức ở đây, mình sẽ để bạn đọc tự chứng minh
=> Kết quả bài toán là: ~\frac{N \times (N - 1)}{2} - \sum_{x=0}^{10^6}{\frac{cnt_x \times (cnt_x - 1)}{2}}~.
ĐPT: ~O~(~n~)
Code mẫu:
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 9;
int n;
int a[N];
namespace sub1 {
bool valid() {
return n <= 5000;
}
void solve() {
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int res = 0;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (a[i] != a[j]) {
++res;
}
}
}
cout << res;
exit(0);
}
}
namespace subfull {
int cnt[N];
void solve() {
for (int i = 1; i <= n; i++) {
cin >> a[i];
cnt[a[i]]++;
}
int res = 0;
for (int i = 0; i <= (int)1e6; i++) {
res += 1LL * (cnt[i] * (cnt[i] - 1)) / 2;
}
cout << 1LL * n * (n - 1) / 2 - res;
exit(0);
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
if (sub1::valid()) sub1::solve();
subfull::solve();
return 0;
}
// <33
Bình luận