Hướng dẫn giải của [VT Thiếu nhi] BÀI 12: TRIAD
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 kiểm tra có tồn tại ba số ~x, x+1, x+2~ đều xuất hiện trong dãy hay không. "Liên tiếp" được hiểu theo giá trị (test mẫu có 5, 6, 7, 8 trong dãy), không theo vị trí. Đề ghi các số đôi một khác nhau nhưng test mẫu có số 8 và số 5 lặp lại; lời giải vẫn xử lý đúng khi có số lặp.
Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 1000~
Với mỗi ~A_i~, kiểm tra ~A_i + 1~ và ~A_i + 2~ có trong dãy bằng quét tuyến tính. Nếu chỉ nộp sub này: đúng 8/10 test.
Sub 2: Dùng tập hợp (set) — ~O(n \log n)~
Đưa dãy vào set. Với mỗi phần tử ~x~ của set, kiểm tra ~x+1~ và ~x+2~ có trong set không. Nếu chỉ nộp sub này: đúng 10/10 test.
Chương trình hoàn chỉnh
~main~ đọc dữ liệu. Nếu ~n \le 1000~ gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> A;
// Sub 1: vet can. Voi moi A[i], kiem tra A[i]+1 va A[i]+2 co trong day khong bang quet tuyen tinh. O(n^2).
// Dung khi n <= 1000.
void sub1() {
auto has = [&](long long x) {
for (int i = 0; i < n; i++)
if (A[i] == x) return true;
return false;
};
for (int i = 0; i < n; i++)
if (has(A[i] + 1) && has(A[i] + 2)) {
cout << "YES\n";
return;
}
cout << "NO\n";
}
// Sub 2: dua day vao set. Voi moi x trong set, kiem tra x+1 va x+2 co trong set. O(n log n).
void sub2() {
set<long long> S(A.begin(), A.end());
for (long long x : S)
if (S.count(x + 1) && S.count(x + 2)) {
cout << "YES\n";
return;
}
cout << "NO\n";
}
int main() {
freopen("TRIAD.INP", "r", stdin);
freopen("TRIAD.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
A.resize(n);
for (int i = 0; i < n; i++) cin >> A[i];
if (n <= 1000) sub1();
else sub2();
return 0;
}
Bình luận