Hướng dẫn giải của [Beginner Free Contest 07] TRICOUNT
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
Yêu cầu: đếm số bộ ba thanh sắt (theo chỉ số ~i < j < k~) có thể tạo thành tam giác không suy biến.
Sub 1: Thử mọi bộ ba — ~O(N^3)~, dùng khi ~N \le 500~
Với mỗi bộ ba, sắp xếp ba độ dài ~t_0 \le t_1 \le t_2~ và kiểm tra ~t_0 + t_1 > t_2~.
Nếu chỉ nộp sub này: đúng 4/20 test.
Sub 2: Sắp xếp và hai con trỏ — ~O(N^2)~
Sắp xếp tăng dần. Với chỉ số lớn nhất ~k~, đếm cặp ~i < j < k~ có ~A_i + A_j > A_k~ bằng con trỏ ~i~ chỉ tiến lên khi ~j~ giảm dần.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Với ~N \le 500~ gọi sub 1, còn lại gọi sub 2. 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;
vector<long long> A; // A[0..N-1]
// Sub 1: thử mọi bộ ba O(N^3) — dùng khi N <= 500
// Ba cạnh x, y, z tạo tam giác khi sau khi sắp xếp t0 + t1 > t2.
void sub1() {
long long ans = 0;
for (int i = 0; i < N; i++)
for (int j = i + 1; j < N; j++)
for (int k = j + 1; k < N; k++) {
long long t[3] = {A[i], A[j], A[k]};
sort(t, t + 3);
if (t[0] + t[1] > t[2]) ans++;
}
cout << ans << "\n";
}
// Sub 2: sắp xếp rồi hai con trỏ O(N^2) — lời giải đầy đủ
// Sau khi sắp xếp tăng dần, với chỉ số lớn nhất k, bộ (i<j<k) là tam giác khi A[i] + A[j] > A[k].
void sub2() {
sort(A.begin(), A.end());
long long ans = 0;
for (int k = 2; k < N; k++) {
int i = 0;
// j giảm dần thì ngưỡng cho i tăng dần, nên con trỏ i chỉ tiến lên
for (int j = k - 1; j >= 1; j--) {
while (i < j && A[i] + A[j] <= A[k]) i++;
if (i < j) ans += j - i;
}
}
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
A.resize(N);
for (auto &v : A) cin >> v;
if (N <= 500) sub1();
else sub2();
return 0;
}
Bình luận