Hướng dẫn giải của [Beginner Free Contest 14] ART
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ỗi màu chỉ được dùng một lượt và chỉ tô một đoạn liên tiếp, nên mỗi màu ~c~ tương ứng một đoạn ~[L_c, R_c]~ (từ lần xuất hiện đầu đến lần cuối). Các màu tô sau đè lên các màu tô trước, nên các đoạn phải lồng nhau hoặc rời nhau; các đoạn rời nhau (cùng độ sâu) tô được trong cùng một lượt. Đáp án là độ sâu lồng nhau lớn nhất. Test có trường hợp vô nghiệm (đề không nêu rõ) và đáp án khi đó là ~-1~: hai đoạn cắt nhau, hoặc có ô 0 nằm giữa một đoạn màu.
Sub 1: Xét từng cặp màu — ~O(n^2)~, dùng khi ~n \le 5000~
Với mỗi màu, kiểm tra không có ô 0 trong đoạn, không có đoạn nào cắt nó, và đếm số đoạn bao nó (kể cả chính nó). Nếu chỉ nộp sub này: đúng 6/10 test (các test lớn bị TLE).
Sub 2: Ngăn xếp — ~O(n)~
Duyệt dãy từ trái sang phải, giữ ngăn xếp các màu đang mở: gặp màu lần đầu thì đẩy vào, gặp lần cuối thì lấy ra; nếu gặp màu không nằm ở đỉnh ngăn xếp hoặc gặp ô 0 khi ngăn xếp khác rỗng thì in ~-1~. Đáp án là kích thước lớn nhất của ngăn xếp. Nếu chỉ nộp sub này: đúng 10/10 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu, tính ~L, R~ của từng màu; ~n \le 5000~ gọi sub1 (4 test), lớn hơn gọi sub2 (6 test). 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;
int a[100005], L[100005], R[100005];
// Sub 1: xét từng cặp màu — O(n^2), dùng khi n <= 5000
// Mỗi màu c chỉ được tô một lần thành một đoạn [L,R]; hai đoạn phải lồng nhau hoặc rời nhau,
// và trong đoạn không được có ô 0. Đáp án = độ sâu lồng nhau lớn nhất, nếu vô nghiệm in -1.
void sub1() {
int best = 0;
for (int c = 1; c <= n; c++) {
if (!L[c]) continue;
int depth = 0;
for (int i = L[c]; i <= R[c]; i++)
if (a[i] == 0) { cout << -1 << "\n"; return; } // ô trống nằm giữa đoạn màu
for (int d = 1; d <= n; d++) {
if (!L[d]) continue;
if (L[d] < L[c] && L[c] < R[d] && R[d] < R[c]) { cout << -1 << "\n"; return; } // hai đoạn cắt nhau
if (L[d] <= L[c] && R[c] <= R[d]) depth++; // màu d bao màu c (kể cả chính nó)
}
best = max(best, depth);
}
cout << best << "\n";
}
// Sub 2: duyệt một lần với ngăn xếp các màu đang "mở" — O(n)
void sub2() {
vector<int> st;
int best = 0;
for (int i = 1; i <= n; i++) {
int c = a[i];
if (c == 0) {
if (!st.empty()) { cout << -1 << "\n"; return; }
continue;
}
if (i == L[c]) st.push_back(c); // gặp lần đầu: mở màu c
else if (st.empty() || st.back() != c) { cout << -1 << "\n"; return; } // c bị màu khác chen vào
best = max(best, (int)st.size());
if (i == R[c]) st.pop_back(); // gặp lần cuối: đóng màu c
}
cout << best << "\n";
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (a[i]) {
if (!L[a[i]]) L[a[i]] = i;
R[a[i]] = i;
}
}
if (n <= 5000) sub1();
else sub2();
return 0;
}
Bình luận