Hướng dẫn giải của [FRIENDNUM] Cặp số bạn bè
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 sao cho ai + aj chia hết cho 3. Đọc từ FRIENDNUM.INP, ghi ra FRIENDNUM.OUT.
Sub 1: Vét cạn trên mọi cặp — ~O(n^2)~
Xét mọi cặp i < j và kiểm tra tổng có chia hết cho 3 không. Cách này đúng nhưng với n lên đến 10^5 thì có tới 5·10^9 cặp, quá chậm.
Kết quả chấm: đạt 10/12 test (SUB ok 10/12, TLE 2, WA 0)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("FRIENDNUM.INP", "r")) {
freopen("FRIENDNUM.INP", "r", stdin);
freopen("FRIENDNUM.OUT", "w", stdout);
}
int n;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
// Vét cạn: xét mọi cặp i < j, đếm cặp có tổng chia hết cho 3
long long dem = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if ((a[i] + a[j]) % 3 == 0) dem++;
cout << dem << "\n";
return 0;
}
Sub 2: Đếm theo số dư khi chia cho 3 — ~O(n)~
Tổng chia hết cho 3 khi cả hai số có số dư 0, hoặc một số dư 1 và một số dư 2. Đếm số phần tử có số dư 0, 1, 2 là c0, c1, c2. Số cặp là c0·(c0-1)/2 + c1·c2. Kết quả có thể lên tới khoảng 5·10^9 nên dùng long long.
Kết quả chấm: đạt 12/12 test
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("FRIENDNUM.INP", "r")) {
freopen("FRIENDNUM.INP", "r", stdin);
freopen("FRIENDNUM.OUT", "w", stdout);
}
int n;
cin >> n;
long long dem[3] = {0, 0, 0}; // dem[r] = số phần tử có số dư r khi chia cho 3
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
dem[x % 3]++;
}
// Tổng chia hết cho 3 khi: cả hai số dư 0, hoặc một số dư 1 và một số dư 2
long long kq = dem[0] * (dem[0] - 1) / 2 + dem[1] * dem[2];
cout << kq << "\n";
return 0;
}
Bình luận