noip 2008 双栈排序

题目大意： 给定n和一串数字，这串数字是一个1~n的排列。现在要用两个栈给这些数字排序。首先先判断是否有解，有解的话再输出字典序最小的方案： 入栈1，输出a，出栈1，输出b 入栈2，输出c，出栈2，输出d 分析： 首先必然要先考虑是否有解。对于没有解的情况，必然是当到了某一个数x0时，栈1，栈2队首元素都不能弹出，并且x0要比栈1、2的队首元素都要大，这时就不能排序了。 所以考虑什么时候A、B不能在同一个栈中的情况： 当且仅当，A<B，并且存在C,使得A>C.并满足A位置在B前面，B位置在C前面。就是说，由于C的存在，A不能pop掉，但是B放进去，A就永远pop不了了。 这样就可以找到所有不能和x0在同一个栈里的所有位置上的数了。 判断无解时，将所有上述的A和B之间连一条无向边，用二分图染色或者带偏移量的并查集都可以。 输出时，因为要字典序最小，所以第一个元素必然要放进栈1，这样可以预处理出来所有数要进入哪一个栈。能进栈1的都进栈1. 然后模拟实现，每次先要判断是否可以pop掉栈顶元素，然后按照之前的预处理的方案放进数就可以了。 ```cpp #include<bits/stdc++.h> using namespace std; const int N=1010; int a[N],la[N],co[N]; int n; int head[N]; int cnt=1; bool flag=0; int sta[3][N];//记录栈1、栈2 int top[3];//记录栈顶 int go[N];//这个位置上的数要去哪一个栈 int has;//已经出栈到几号 struct node{ int to,nxt; }bian[2*N]; void add(int x,int y) { bian[++cnt].nxt=head[x]; bian[cnt].to=y; head[x]=cnt; }//建边 void dfs1(int x,int fa,int se)//1 black 2 white { if(flag) return; co[x]=se; for(int i=head[x];i;i=bian[i].nxt) { int y=bian[i].to; if(y==fa) continue; if(co[y]) { if(co[y]==co[x]) { flag=1;return; } } else{ dfs1(y,x,3-se); } } }//二分图染色判断 void dfs2(int x,int se) { go[x]=se; for(int i=head[x];i;i=bian[i].nxt) { int y=bian[i].to; if(!go[y]) { dfs2(y,3-se); } } }//预处理该去的栈（其实也可以在二分图染色时处理出来，就省了这步） void check(int now) { bool f=0; while(top[now]&&has+1==sta[now][top[now]]) { f=1; printf("%c ",now==1?'b':'d'); has++; top[now]--; } if(f)//成功pop才找另一个 check(3-now); } //检查能否pop int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) for(int j=n;j>=i+1;j--) { if(a[i]>a[j]) {la[i]=j;break;} }//找到A的最后面一个C的位置。 for(int i=1;i<=n;i++) for(int j=i+1;j<=la[i];j++) { if(a[i]<a[j]) { add(i,j); add(j,i); } }//A到C之间所有的B都要和A建边 for(int i=1;i<=n;i++) { if(flag==1) break; if(!co[i]) dfs1(i,0,1); } if(flag) { printf("0"); return 0; }//判断 go[1]=1; for(int x=1;x<=n;x++) { if(!go[x]) go[x]=1,dfs2(x,1); } for(int i=1;i<=n;i++) { check(1); check(2); sta[go[i]][++top[go[i]]]=a[i]; printf("%c ",go[i]==1?'a':'c'); } check(1); check(2);//最后也要判断，输出完。 return 0; } ```