这真是道神奇的题目:
原题链接
首先我们要证明以下的性质:
若原序列为\(\{a_n\}\),\(a_i\)和\(a_j\)不能同时放入一个栈中,当且仅当\(i<j,a_i<a_j\),且存在\(k\),\(s.t. \ k>j\)的同时有\(a_k<a_i\)。
原因很显然,因为有比\(a_i\)还小的元素在后面,若放入同一个栈中,必须先压栈压到\(a_k\),再弹出,但又因为会先弹出\(a_j\),序列的单调性就被破坏了。
所以对于每一对\(a_i\)和\(a_j\),我们都可以用上述性质来判断它们是否能在同一个栈中,再用后缀最大值优化一下,复杂度\(O(n^2)\)。
然后我们就有了这样的一些关系,我们该如何利用这些关系来判断序列是否合法呢?
二分图染色,对于不能在同一个栈中的两个位置,我们连一条无向边,然后dfs判断所有点能否二染色。如果能,序列就是合法的,否则不合法。
对于染色后的图,其实我们已经知道操作顺序了,又因为题目要求字典序最小,所以我们只用模拟一下,优先在栈\(S1\)上操作就行了。
上代码:
#include <bits/stdc++.h>
using namespace std;
#define wrap cout << endl
const int N = 1000;
int n, a[N+5], color[N+5], f[N+5], flag;
vector<int> G[N+5];
void addEdge(int u, int v) {
G[u].push_back(v);
G[v].push_back(u);
}
void dfs(int u) {
for(int i = 0; i < G[u].size(); ++i) {
int v = G[u][i];
if(color[v]) {
if(color[v] == color[u])
flag = 1;
}
else {
color[v] = 3-color[u];
dfs(v);
}
}
}
void solve() {
int cur = 1;
stack<int> s1, s2;
for(int i = 1; i <= n; ++i) { //模拟
if(color[i] == 1) s1.push(a[i]), cout << 'a' << " ";
if(color[i] == 2) s2.push(a[i]), cout << 'c' << " ";
while((!s1.empty() && s1.top() == cur) || (!s2.empty() && s2.top() == cur)) {
if(!s1.empty() && s1.top() == cur) s1.pop(), cout << 'b' << " ";
if(!s2.empty() && s2.top() == cur) s2.pop(), cout << 'd' << " ";
++cur;
}
}
}
int main() {
cin >> n;
for(int i = 1; i <= n; ++i) cin >> a[i];
f[n+1] = 0x3f3f3f3f;
for(int i = n; i >= 1; --i) f[i] = min(f[i+1], a[i]);
for(int i = 1; i <= n; ++i)
for(int j = i+1; j <= n; ++j)
if(a[i] < a[j] && f[j+1] < a[i]) addEdge(i, j); //判断是否加边
for(int i = 1; i <= n; ++i)
if(!color[i])
color[i] = 1, dfs(i);
if(flag) {
cout << "0" << endl;
return 0;
}
solve();
return 0;
}