Hướng dẫn giải của [VTT Q4 Contest 13] Bài 2: Bộ ba số [BOBASO]
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
Đếm số cặp vị trí không có thứ tự ~\{i, j\}~ sao cho ~a_i + a_j~ bằng một phần tử khác trong dãy (các phần tử đôi một khác nhau, nên ~k~ khác ~i, j~ là tự nhiên vì ~a_i, a_j \ge 1~).
Sub 1: Vét cạn — ~O(n^3)~, dùng khi ~n \le 100~
Duyệt mọi cặp ~(i, j)~ với ~i < j~ và mọi ~k~, kiểm tra ~a_i + a_j = a_k~. Nếu chỉ nộp sub này: đúng 6/20 test.
Sub 2: Chặt nhị phân — ~O(n^2 \log n)~, dùng khi ~n \le 3000~
Sắp xếp dãy, với mỗi cặp ~(i, j)~ chặt nhị phân xem tổng có trong dãy không. Nếu chỉ nộp sub này: đúng 20/20 test trên máy chấm cục bộ (dễ dãi hơn máy chấm thật với ~n = 10^4~).
Sub 3: Hai con trỏ — ~O(n^2)~
Sau khi sắp xếp, cố định ~a_k~ rồi tìm các cặp ~l < r < k~ có ~a_l + a_r = a_k~ bằng hai con trỏ từ hai đầu: tổng nhỏ thì tăng ~l~, lớn thì giảm ~r~, bằng thì đếm và dịch cả hai (vì các giá trị khác nhau). Chỉ cần xét ~r < k~ vì số hạng dương nên tổng lớn hơn cả hai số hạng. 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, ~n \le 100~ gọi sub1, ~n \le 3000~ gọi sub2, còn lại gọi sub3. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
int n;
long long a[10005];
// Sub 1: vét cạn cặp (i,j) và k — O(n^3), dùng khi n <= 100
void sub1() {
long long res = 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]) res++;
cout << res << "\n";
}
// Sub 2: duyệt cặp (i,j), chặt nhị phân tìm tổng — O(n^2 log n), dùng khi n <= 3000
void sub2() {
sort(a, a + n);
long long res = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (binary_search(a, a + n, a[i] + a[j])) res++;
cout << res << "\n";
}
// Sub 3: sắp xếp, với mỗi k dùng hai con trỏ tìm cặp có tổng a[k] — O(n^2)
void sub3() {
sort(a, a + n);
long long res = 0;
for (int k = 2; k < n; k++) {
int l = 0, r = k - 1;
while (l < r) {
long long s = a[l] + a[r];
if (s == a[k]) { res++; l++; r--; }
else if (s < a[k]) l++;
else r--;
}
}
cout << res << "\n";
}
int main() {
freopen("BOBASO.INP", "r", stdin);
freopen("BOBASO.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
if (n <= 100) sub1();
else if (n <= 3000) sub2();
else sub3();
}
Bình luận