Hướng dẫn giải của Ghép dây
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
Cần đếm số bộ $(i, j, k, t)$ sao cho $Ai + Bj + Ck + Dt = L$. Kết quả có thể lên tới khoảng $10^{12}$ nên dùng long long.
Sub 1: Vét cạn bốn vòng lặp — ~O(N^4)~, dùng khi ~N \le 50~
Thử mọi bộ bốn số, đếm những bộ có tổng bằng $L$.
Nếu chỉ nộp sub này: đúng 9/20 test (11 test lớn quá giờ).
Sub 2: Ghép hai nửa — ~O(N^2 \log N)~
Gom $Ai + Bj$ thành $N^2$ tổng rồi sắp xếp. Với mỗi cặp $(Ck, Dt)$ có tổng $x$, số cách chọn $A$ và $B$ là số tổng $A + B$ bằng $L - x$, đếm bằng equal_range.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
main đọc dữ liệu từ file MATCH.INP, ghi ra MATCH.OUT. Nếu $N \le 50$ thì gọi sub 1, còn lại gọi sub 2.
#include <bits/stdc++.h>
using namespace std;
int N;
long long L;
vector<long long> A, B, C, D; // A[0..N-1], B, C, D: do dai N soi day moi loai
// Sub 1: vet can, bon vong lap long nhau O(N^4), dung khi N <= 50.
void sub1() {
long long cnt = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
for (int k = 0; k < N; k++)
for (int t = 0; t < N; t++)
if (A[i] + B[j] + C[k] + D[t] == L) cnt++;
cout << cnt << "\n";
}
// Sub 2: O(N^2 log N). Liet ke N^2 tong A+B, sap xep. Voi moi cap (C, D) co tong x,
// dem so tong A+B bang L - x bang equal_range.
void sub2() {
vector<long long> ab;
ab.reserve((size_t)N * N);
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++) ab.push_back(A[i] + B[j]);
sort(ab.begin(), ab.end());
long long cnt = 0;
for (int k = 0; k < N; k++)
for (int t = 0; t < N; t++) {
long long need = L - (C[k] + D[t]);
auto r = equal_range(ab.begin(), ab.end(), need);
cnt += r.second - r.first;
}
cout << cnt << "\n";
}
int main() {
freopen("MATCH.INP", "r", stdin);
freopen("MATCH.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> L;
A.resize(N); B.resize(N); C.resize(N); D.resize(N);
for (auto &x : A) cin >> x;
for (auto &x : B) cin >> x;
for (auto &x : C) cin >> x;
for (auto &x : D) cin >> x;
if (N <= 50) sub1();
else sub2();
return 0;
}
Bình luận