Hướng dẫn giải của Bộ ba số (THCS KS3 VTT)
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
Bộ ba đẹp gồm ba số khác nhau trong đó tổng hai số bằng số thứ ba. Các số đều dương nên số được tạo ra luôn là số lớn nhất trong bộ. Mỗi cặp {i, j} có tổng ai + aj xuất hiện trong dãy tương ứng đúng một bộ ba, nên chỉ cần đếm số cặp {i, j} (i \ne j) có tổng nằm trong dãy.
Sub 1: Vét cạn ba số — ~O(n^3)~, dùng khi ~n \le 100~
Duyệt mọi cặp i < j và mọi k khác i, j, kiểm tra ai + aj = a_k. Nếu chỉ nộp sub này: đúng 6/20 test.
Sub 2: Sắp xếp và hai con trỏ — ~O(n^2)~
Sắp xếp dãy. Với mỗi i, cho j tăng dần từ i+1 thì tổng tăng dần, nên con trỏ q trên mảng đã sắp xếp chỉ tiến một chiều để kiểm tra tổng có trong dãy không. Mỗi cặp được đếm đúng một lần.
Bẫy: đáp án có thể lớn (khoảng n^2 / 2), dùng long long.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc dãy. Nếu n \le 100 gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> a; // a[0..n-1], cac gia tri doi mot khac nhau
// Sub 1: vet can. Voi moi bo (i, j, k) xet xem co a_i + a_j = a_k khong. O(n^3). Dung khi n <= 100
void sub1() {
long long cnt = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
for (int k = 0; k < n; k++)
if (k != i && k != j && a[i] + a[j] == a[k]) cnt++;
cout << cnt << "\n";
}
// Sub 2: dem cap {i, j} (i != j) co a_i + a_j xuat hien trong day. Moi cap xac dinh duy nhat bo ba.
// Sap xep day. Voi moi i, cho j tang dan thi tong a_i + a_j tang dan, nen con tro q tren mang da sap xep
// chi tien mot chieu, kiem tra tong co trong mang khong. O(n^2) tong.
void sub2() {
vector<long long> b = a;
sort(b.begin(), b.end());
long long cnt = 0;
for (int i = 0; i < n; i++) {
int q = 0;
for (int j = i + 1; j < n; j++) {
long long target = b[i] + b[j];
while (q < n && b[q] < target) q++;
if (q < n && b[q] == target) cnt++;
}
}
cout << cnt << "\n";
}
int main() {
freopen("BOBASO.INP", "r", stdin);
freopen("BOBASO.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
a.assign(n, 0);
for (int i = 0; i < n; i++) cin >> a[i];
if (n <= 100) sub1();
else sub2();
return 0;
}
Bình luận