Hướng dẫn giải của [VTT Q4 Contest 06] Bài 1: Dãy cơ sở [BASE]
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 xóa dần các "điểm lõm" (phần tử có số lớn hơn ở cả hai phía) cho đến khi không còn điểm lõm. Nhận xét quan trọng: xóa một điểm lõm không làm đổi max tiền tố/hậu tố của các phần tử còn lại, nên kết quả không phụ thuộc thứ tự xóa.
Sub 1: Mô phỏng — ~O(n^2)~ mỗi lần xóa, dùng khi ~n \le 100~
Lặp: duyệt dãy, với mỗi phần tử kiểm tra bên trái và bên phải có số lớn hơn không; gặp điểm lõm thì xóa rồi quét lại từ đầu, đến khi không xóa được nữa. Nếu chỉ nộp sub này: đúng 20/20 test (vì ~n \le 1000~ vẫn đủ nhanh).
Sub 2: Max tiền tố và hậu tố — ~O(n)~
Phần tử ~a_i~ bị xóa khi và chỉ khi trong dãy gốc, max của các phần tử trước nó ~> a_i~ và max của các phần tử sau nó ~> a_i~. Tính hai mảng max rồi in các phần tử không bị xóa. 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ữ liệu, ~n \le 100~ gọi sub1, còn lại gọi sub2. 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[1005];
// Sub 1: mô phỏng đúng đề — mỗi lần tìm một điểm lõm rồi xóa nó, lặp đến khi hết điểm lõm. ~O(n^2)~
void sub1() {
vector<long long> v(a + 1, a + n + 1);
bool changed = true;
while (changed) {
changed = false;
int sz = v.size();
for (int i = 1; i + 1 < sz; i++) {
bool left = false, right = false;
for (int k = 0; k < i; k++) if (v[k] > v[i]) left = true;
for (int l = i + 1; l < sz; l++) if (v[l] > v[i]) right = true;
if (left && right) {
v.erase(v.begin() + i);
changed = true;
break;
}
}
}
cout << v.size() << "\n";
for (size_t i = 0; i < v.size(); i++) cout << v[i] << " ";
cout << "\n";
}
// Sub 2: phần tử bị xóa khi và chỉ khi trước nó có số lớn hơn và sau nó có số lớn hơn (trong dãy gốc).
// Dùng max tiền tố và max hậu tố. ~O(n)~
void sub2() {
vector<long long> pre(n + 2, 0), suf(n + 2, 0), res;
for (int i = 1; i <= n; i++) pre[i] = max(pre[i - 1], a[i]);
for (int i = n; i >= 1; i--) suf[i] = max(suf[i + 1], a[i]);
for (int i = 1; i <= n; i++)
if (!(pre[i - 1] > a[i] && suf[i + 1] > a[i])) res.push_back(a[i]);
cout << res.size() << "\n";
for (size_t i = 0; i < res.size(); i++) cout << res[i] << " ";
cout << "\n";
}
int main() {
freopen("BASE.INP", "r", stdin);
freopen("BASE.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
if (n <= 100) sub1();
else sub2();
}
Bình luận