Hướng dẫn giải của Đếm cặp (THCS KS2)
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
Cho dãy N số nguyên dương A1..AN (N ≤ 10^6). Đếm số cặp (i, j), i < j, có tổng Ai + Aj là số chẵn.
Sub 1: Vét cạn, thử mọi cặp — ~O(N^2)~
Với mỗi cặp chỉ số (i, j) với i < j, kiểm tra tổng có chẵn không rồi đếm. Đúng nhưng số cặp lên tới khoảng 5·10^11 khi N = 10^6 nên chỉ đạt các test nhỏ.
Kết quả chấm: 10/20 (SUB ok 10/20, TLE 10, WA 0)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
long long dem = 0;
// Vet can: thu moi cap (i, j) voi i < j, kiem tra tong co chan khong
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if ((a[i] + a[j]) % 2 == 0) dem++;
cout << dem << "\n";
return 0;
}
Sub 2: Đếm chẵn, lẻ — ~O(N)~
Tổng hai số là chẵn khi cả hai cùng chẵn hoặc cùng lẻ. Đếm số phần tử chẵn (c) và lẻ (l), số cặp cần tìm là C(c, 2) + C(l, 2) = c(c-1)/2 + l(l-1)/2.
Bẫy: c và l có thể lên tới 10^6, tích c(c-1) có thể khoảng 10^12 nên dùng long long.
Kết quả chấm: 20/20
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
long long chan = 0, le = 0;
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
if (x % 2 == 0) chan++;
else le++;
}
// Tong hai so chan la chan, tong hai so le la chan, tong chan + le la le
// Vay so cap co tong chan = C(chan, 2) + C(le, 2)
long long ans = chan * (chan - 1) / 2 + le * (le - 1) / 2;
cout << ans << "\n";
return 0;
}
Bình luận