思路:要使用2个栈操作使得序列升序,我们可以发现当2个数a[i] a[j]不能放入同一个栈中的时候,要满足条件 i<j<k && a[k]<a[i]<a[j]这里呢,我们用dp[i]表示从i开始到结尾的最小值,不能放到同一个栈中我们就把他分开,这样我们要求的就是能不能构成2个符合条件的独立集,我们根据这个条件去建图,当a[i] a[j]不能放入同一个栈中,我们将i,j建一条边,然后用染色法判断二分图,不能构成二分图答案就是0,能构成的话,我们先涂的色为1,后涂色为2,因为字典序最小我们吧先涂色的1视为压入栈1,涂色2视为压入栈2,之后我们看什么时候2个栈中出现1了那么就开始出栈。
#include <cstdio> #include <cstring> #include <algorithm> #include <set> #include<iostream> #include<vector> #include<queue> #include<stack> #include<bits/stdc++.h> using namespace std; typedef long long ll; #define SIS std::ios::sync_with_stdio(false) #define space putchar(' ') #define enter putchar('\n') #define lson root<<1 #define rson root<<1|1 typedef pair<int,int> PII; const int mod=998244353; const int N=2e6+10; const int M=2e3+10; const int inf=0x7f7f7f7f; const int maxx=2e5+7; ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); } ll lcm(ll a,ll b) { return a*(b/gcd(a,b)); } template <class T> void read(T &x) { char c; bool op = 0; while(c = getchar(), c < '0' || c > '9') if(c == '-') op = 1; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; if(op) x = -x; } template <class T> void write(T x) { if(x < 0) x = -x, putchar('-'); if(x >= 10) write(x / 10); putchar('0' + x % 10); } ll qsm(int a,int b,int p) { ll res=1%p; while(b) { if(b&1) res=res*a%p; a=1ll*a*a%p; b>>=1; } return res; } int n,m; vector<int> G[N]; int a[N]; int flag=0; int color[N]; int dp[N]; int dfs(int u,int c) { color[u]=c; for(int i=0;i<G[u].size();i++) { int j=G[u][i]; if(!color[j]) { if(!dfs(j,3-c)) return 0; } else if(color[j]==c) return 0; } return 1; } int main() { cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; dp[n+1]=n+1; for(int i=n;i;i--) dp[i]=min(dp[i+1],a[i]); for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) { if(a[i]<a[j]&&dp[j+1]<a[i]) { G[i].push_back(j); G[j].push_back(i); } } } for(int i=1;i<=n;i++) { if(!color[i]&&!dfs(i,1)) { flag=1;break; } } if(flag) { cout<<0<<endl; } else { int tp=1; stack<int> s1,s2; for(int i=1;i<=n;i++) { if(color[i]==1) { s1.push(a[i]); cout<<"a "; } else { s2.push(a[i]); cout<<"c "; } while(1) { if(s1.size()&&s1.top()==tp) { s1.pop(); cout<<"b "; tp++; } else if(s2.size()&&s2.top()==tp) { s2.pop(); cout<<"d "; tp++; } else break; } } } return 0; }