Hướng dẫn giải của [200 đề thầy Đức] Bài 155: Bộ 3 có thứ tự
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 $A$ gồm $N$ số, cần kiểm tra có tồn tại ba chỉ số $i < j < k$ sao cho $A[i] < A[j] < A[k]$ hay không. Có $T$ bộ dữ liệu, $N \le 10^5$.
Sub 1: Vét cạn — ~O(N^3)~, dùng khi ~N \le 200~
Thử mọi bộ ba chỉ số $i < j < k$ và kiểm tra điều kiện. Đúng với mọi dãy, nhưng với $N$ lớn thì chậm.
Kết quả chạy riêng sub này: đúng 13/21 test (8 test còn lại quá giờ, đều có $N$ lớn hơn miền của sub này).
Sub 2: Tiền tố min và hậu tố max — ~O(N)~
Với một phần tử $A[j]$ làm phần tử giữa, cần tồn tại phần tử nhỏ hơn $A[j]$ đứng trước và phần tử lớn hơn $A[j]$ đứng sau. Gọi $\text{preMin}[j]$ là giá trị nhỏ nhất trong $A[1..j-1]$ và $\text{sufMax}[j]$ là giá trị lớn nhất trong $A[j+1..N]$. Bộ ba tồn tại khi và chỉ khi có $j$ với $\text{preMin}[j] < A[j] < \text{sufMax}[j]$.
Bẫy cần chú ý: với $j = 1$ hoặc $j = N$ không có phần tử ở một phía, nên cần khởi tạo giá trị "vô cực" phù hợp (LLONG_MAX cho min, LLONG_MIN cho max) để điều kiện luôn sai ở đó.
Chương trình hoàn chỉnh
Chương trình đọc $T$ bộ dữ liệu. Với mỗi bộ, nếu $N \le 200$ thì gọi sub1, ngược lại gọi sub2. Khi đi thi, sub1 vẫn ăn điểm các test nhỏ nếu chưa làm được sub2.
#include <bits/stdc++.h>
using namespace std;
int T;
vector<vector<long long>> arrs; // mỗi bộ dữ liệu là một dãy A, chỉ số từ 1 (A[0] không dùng)
// Sub 1: vét cạn — thử mọi bộ ba chỉ số i < j < k, kiểm tra A[i] < A[j] < A[k]
// Dùng khi mọi N <= 200
void sub1() {
for (int t = 0; t < T; t++) {
vector<long long> &A = arrs[t];
int N = A.size() - 1;
bool ok = false;
for (int i = 1; i <= N && !ok; i++)
for (int j = i + 1; j <= N && !ok; j++)
for (int k = j + 1; k <= N; k++)
if (A[i] < A[j] && A[j] < A[k]) { ok = true; break; }
cout << (ok ? "YES" : "NO") << "\n";
}
}
// Sub 2: với mỗi j, cần có i < j với A[i] < A[j] và k > j với A[k] > A[j].
// Lưu min của tiền tố và max của hậu tố để kiểm tra mỗi j trong O(1). Tổng O(N).
void sub2() {
for (int t = 0; t < T; t++) {
vector<long long> &A = arrs[t];
int N = A.size() - 1;
vector<long long> preMin(N + 2), sufMax(N + 2);
preMin[1] = LLONG_MAX; // chưa có phần tử nào trước vị trí 1
for (int j = 2; j <= N; j++) preMin[j] = min(preMin[j - 1], A[j - 1]);
sufMax[N] = LLONG_MIN; // chưa có phần tử nào sau vị trí N
for (int j = N - 1; j >= 1; j--) sufMax[j] = max(sufMax[j + 1], A[j + 1]);
bool ok = false;
for (int j = 1; j <= N; j++)
if (preMin[j] < A[j] && A[j] < sufMax[j]) { ok = true; break; }
cout << (ok ? "YES" : "NO") << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> T;
arrs.resize(T);
bool small = true;
for (int t = 0; t < T; t++) {
int N;
cin >> N;
arrs[t].assign(N + 1, 0);
for (int i = 1; i <= N; i++) cin >> arrs[t][i];
if (N > 200) small = false;
}
if (small) sub1(); // dãy ngắn: vét cạn
else sub2(); // có dãy dài: O(N)
return 0;
}
Bình luận