Hướng dẫn giải của [KSCUM VT] CÂU 3
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. Đếm số cặp (i, j) với i < j mà Ai và Aj khác tính chẵn lẻ (một số chẵn, một số lẻ). Đề đọc từ CAU3.INP và ghi ra CAU3.OUT.
Sub 1: Vét cạn mọi cặp — ~O(n^2)~
Thử mọi cặp (i, j) với i < j và kiểm tra tính chẵn lẻ của hai số. Đúng nhưng chậm, đạt 12/20 test; các test n lớn bị TLE.
#include <bits/stdc++.h>
using namespace std;
int main() {
if (fopen("CAU3.INP", "r")) { freopen("CAU3.INP", "r", stdin); freopen("CAU3.OUT", "w", stdout); }
int n;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
// Sub 1: thu tung cap (i, j) voi i < j, dem cap co tinh chan-le khac nhau (O(n^2))
long long cnt = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (a[i] % 2 != a[j] % 2) cnt++;
cout << cnt << endl;
return 0;
}
Sub 2: Đếm số chẵn và số lẻ — ~O(n)~
Mỗi cặp gồm đúng một số chẵn và một số lẻ, nên số cặp bằng (số lẻ) × (số chẵn). Chỉ cần đếm hai loại rồi nhân. Với n ≤ 10^6, tích có thể lên tới khoảng 2.5·10^11 nên dùng long long. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
if (fopen("CAU3.INP", "r")) { freopen("CAU3.INP", "r", stdin); freopen("CAU3.OUT", "w", stdout); }
int n;
cin >> n;
long long odd = 0, even = 0;
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
if (x % 2 == 0) even++;
else odd++;
}
// Moi cap gom mot so chan va mot so le: so cap = odd * even
cout << odd * even << endl;
return 0;
}
Bình luận