题目链接在此
此题一开始写了个深搜，过了30%的数据，也就是n<=10的那一段。。。。
然后看了题解发现这是个二分图的判断。
我们先举例子找到不能放进一个栈里的规律。设有数列【2，3，1，4】
容易模拟得到这个数列单栈是搞不出来的。为什么搞不出来呢？
如果输入的序列是单调递减的，自然一个栈可以搞定。直接全部压栈再全部弹栈就可以了。
如果输入的序列不是单调递减，一个栈也有可能搞定。但是像我们举的这个例子，你压3的时候必须把2压在底下，那怎么先出2后出3呢？
继续模拟能够发现规律：若i、j不能单栈，当且仅当存在k使得i<j<k且que[k]<que[i]<que[j]
于是就可以把不能单栈的元素连一条无向边，剩下的工作就是判断这张图是否是二分图了。
二分图怎么判断呢？由于这张图中相连点只能属于不同的两个集合，要么A要么B，所以我们可以对点染色。比如A连着B，B连着C，我们就可以先给A染成-1，然后给B染成1，然后给C染成-1.如果发现染色有冲突那就连不成二分图。
随后模拟即可
代码如下
#include<iostream> #include<cctype> #include<cstdio> #include<cstring> int INF=0x7fffffff; inline long long min(long long a,long long b){ return a<b?a:b; } inline long long read(){ long long num=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)){ num=num*10+ch-'0'; ch=getchar(); } return num*f; } struct Edge{ int next,to; }edge[1000000]; int head[1000000],num; inline void add(int from,int to){ edge[++num]=(Edge){head[from],to}; head[from]=num; } int f[10000]; int que[10000]; int val[10000]; int stackA[10000],topA; int stackB[10000],topB; bool dfs(int x,int c){ val[x]=c; for(int i=head[x];i;i=edge[i].next){ int to=edge[i].to; if(val[to]&&val[to]==c) return 0; else if(!val[to]){ val[to]=-c; if(!dfs(to,-c)) return 0; } } return 1; } int main(){ int n=read(); for(int i=1;i<=n;++i) que[i]=read(); f[n+1]=INF; for(int i=n;i>=1;--i) f[i]=min(f[i+1],que[i]); for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j) if(f[j+1]<que[i]&&que[i]<que[j]){ add(i,j); add(j,i); } for(int i=1;i<=n;++i){ if(!val[i]){ bool flag=dfs(i,1); if(!flag){ printf("%d",0); return 0; } } } int cnt=1; for(int i=1;i<=n;++i){ if(val[i]==1){ printf("a "); stackA[++topA]=que[i]; } else{ printf("c "); stackB[++topB]=que[i]; } while((topA&&stackA[topA]==cnt)||(topB&&stackB[topB]==cnt)){ if(topA&&stackA[topA]==cnt){ printf("b "); topA--; } else{ printf("d "); topB--; } cnt++; } } return 0; }