我其实只是想练一练二分图判定的，但是翻到了一个这么个题。。
双栈排序早有耳闻，非常欣赏当年的出题水平，堪称经典
这个题AC的人一定是个天才
废话不多说，双栈排序的思路我就不介绍了，没有那个水平，直接来说说怎么二分图染色
bool color(int x,int cl) { c[x]=cl; for(int tmp=g[x];tmp;tmp=e[tmp].next) { if(!c[e[tmp].t]) {if(!color(e[tmp].t,3-cl)) return 0;} else if(c[e[tmp].t]==cl) return 0; } return 1; }
这个方法，14年的时候练了很多次，当时习惯写BFS的，可能是因为所有点都要跑所以无所谓了吧
每个点都调用一次color，初始cl传1，进来的时候如果这个点没有染过色，就给它染上cl这个颜色
然后判断所有出边所连接的点，如果有相邻且同色的，直接GG
否则，染色为3-cl,这是一个小技巧，cl这时取值为1或2，十分方便
好了，二分图判定说完了，贴上双栈排序的代码跑路了
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int INF=1000000000; 5 const int maxn=1005; 6 int cnt,n,t1,t2; 7 int a[maxn],g[maxn],c[maxn],f[maxn],s1[maxn],s2[maxn]; 8 struct Edge{int t,next;}e[maxn*maxn]; 9 void addedge(int u,int v) 10 { 11 e[++cnt].t=v;e[cnt].next=g[u]; 12 g[u]=cnt; 13 } 14 bool color(int x,int cl) 15 { 16 c[x]=cl; 17 for(int tmp=g[x];tmp;tmp=e[tmp].next) 18 { 19 if(!c[e[tmp].t]) 20 {if(!color(e[tmp].t,3-cl)) return 0;} 21 else if(c[e[tmp].t]==cl) return 0; 22 } 23 return 1; 24 } 25 int read() 26 { 27 int x=0,f=1;char ch=getchar(); 28 while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();} 29 while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();} 30 return x*f; 31 } 32 int main() 33 { 34 n=read(); 35 for(int i=1;i<=n;i++) a[i]=read(); 36 f[n+1]=INF; 37 for(int i=n;i;i--) f[i]=min(f[i+1],a[i]); 38 for(int i=1;i<=n;i++) 39 for(int j=i+1;j<=n;j++) 40 if(a[i]<a[j]&&f[j+1]<a[i]) addedge(i,j),addedge(j,i); 41 for(int i=1;i<=n;i++) 42 if(!c[i]) 43 if(!color(i,1)) {puts("0");return 0;} 44 int now=1; 45 for(int i=1;i<=n;i++) 46 { 47 if(c[i]==1) printf("a "),s1[++t1]=a[i]; 48 else printf("c "),s2[++t2]=a[i]; 49 while(s1[t1]==now||s2[t2]==now) 50 { 51 if(s1[t1]==now) printf("b "),t1--; 52 else printf("d "),t2--; 53 now++; 54 } 55 } 56 return 0; 57 }