Hướng dẫn giải của Cặp số hoàn hảo (đề Daknong 2021)
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 a1..an và số s. Đếm số cặp chỉ số (i, j) với i < j sao cho ai + aj = s. Số cặp có thể lên tới khoảng n^2/2 nên cần dùng long long.
Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 3000~
Xét mọi cặp (i, j) với i < j, nếu ai + aj = s thì tăng bộ đếm. Cách này đúng trực tiếp theo định nghĩa.
Chấm riêng sub này: đúng 17/20 test (các test có n <= 3000 đều đúng).
Sub 2: Bảng tần suất — ~O(n \log n)~, dùng cho mọi n
Không cần xét từng cặp chỉ số. Đếm số lần xuất hiện cnt[v] của mỗi giá trị v. Với một giá trị v, cặp (v, s - v) đóng góp cnt[v] · cnt[s-v] cặp chỉ số.
- Nếu v < s - v: cộng cnt[v] · cnt[s-v], mỗi cặp giá trị chỉ xét một lần.
- Nếu v = s - v (tức 2v = s): các số bằng nhau tự ghép với nhau, cộng cnt[v] · (cnt[v] - 1) / 2.
Ví dụ: n = 10, s = 7, dãy 5 2 5 3 4 3 1 6 4 0. Cặp giá trị (2, 5): cnt[2]·cnt[5] = 1·2 = 2; cặp (3, 4): cnt[3]·cnt[4] = 2·2 = 4; cặp (1, 6): cnt[1]·cnt[6] = 1·1 = 1. Tổng là 7.
Bẫy: giá trị âm vẫn đúng vì s - v vẫn là số nguyên; map xử lý được. Dùng long long cho cả số đếm.
Chương trình hoàn chỉnh
main đọc n, s và dãy a. Nếu n <= 3000 gọi sub1, còn lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
long long s;
long long a[100005]; // dãy số a_1..a_n
// Đếm số cặp chỉ số i < j sao cho a_i + a_j = s. Kết quả có thể lên tới khoảng n^2/2 nên dùng long long.
// Sub 1: vét cạn — xét mọi cặp (i, j) với i < j, đếm cặp có tổng bằng s. O(n^2). Dùng khi n <= 3000.
void sub1() {
long long cnt = 0;
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
if (a[i] + a[j] == s) cnt++;
cout << cnt << "\n";
}
// Sub 2: đếm bằng bảng tần suất. Với mỗi giá trị v, số cặp (v, s-v) là cnt[v] * cnt[s-v];
// nếu v = s-v thì số cặp là cnt[v]*(cnt[v]-1)/2. Mỗi cặp giá trị chỉ xét một lần (v < s-v). O(n log n).
void sub2() {
map<long long, long long> cnt;
for (int i = 1; i <= n; i++) cnt[a[i]]++;
long long ans = 0;
for (auto &p : cnt) {
long long v = p.first, w = s - v;
if (v == w) {
ans += p.second * (p.second - 1) / 2;
} else if (v < w) {
auto it = cnt.find(w);
if (it != cnt.end()) ans += p.second * it->second;
}
}
cout << ans << "\n";
}
int main() {
freopen("capso.inp", "r", stdin);
freopen("capso.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> s;
for (int i = 1; i <= n; i++) cin >> a[i];
if (n <= 3000) sub1(); // dữ liệu nhỏ: xét mọi cặp
else sub2(); // dữ liệu lớn: bảng tần suất
return 0;
}
Bình luận