LOJ P1155 双栈排序二分图染色图论

https://www.luogu.org/problem/show?pid=P1155

题解： https://www.byvoid.com/zhs/blog/noip2008-twostack

结论P: S[i],S[j]两个元素不能进入同一个栈 <=> 存在k,满足i<j<k,使得S[k]<S[i]<S[j].

二分图染色判断两个数能不能在同一个栈里，确定了每个数应该进入的栈之后直接模拟就好了。

开始我忘了把f[n+1]设成极大值，wa了无数次，mdzz。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 using namespace std;
 7 const int maxn=1010;
 8 int n;
 9 int a[maxn]={},f[maxn]={};
10 struct nod{
11     int y,next;
12 }e[maxn*maxn];
13 int head[maxn]={},c[maxn]={},tot=0;
14 int s1[maxn]={},s2[maxn]={},t1=0,t2=0;
15 inline void init(int x,int y){e[++tot].y=y;e[tot].next=head[x];head[x]=tot;}
16 bool dfs(int x,int v){
17     c[x]=v;
18     for(int i=head[x];i;i=e[i].next){
19         if(!c[e[i].y]){
20             if(!dfs(e[i].y,3-v))return 0;
21         }
22         else if(c[x]==c[e[i].y]){
23             return 0;
24         }
25     }return 1;
26 }
27 int main(){
28     scanf("%d",&n);
29     for(int i=1;i<=n;i++)scanf("%d",&a[i]);
30     f[n+1]=(int)1e9;
31     f[n]=a[n];
32     for(int i=n-1;i;i--)f[i]=min(f[i+1],a[i]);
33     for(int i=1;i<=n;i++){
34         for(int j=i+1;j<=n;j++){
35             if(a[i]<a[j]&&f[j+1]<a[i]){init(i,j);init(j,i);}
36         }
37     }
38     for(int i=1;i<=n;i++){
39         if(!c[i]){
40             if(!dfs(i,1)){
41                 printf("0");
42                 return 0;
43             }
44         }
45     }
46     int now=1;
47     for(int i=1;i<=n;i++){
48         if(i!=1)printf(" ");
49         if(c[i]==1){printf("a");s1[++t1]=a[i];}
50         else {printf("c");s2[++t2]=a[i];}
51         while(s1[t1]==now||s2[t2]==now){
52             printf(" ");
53             if(s1[t1]==now){printf("b");t1--;}
54             else{printf("d");t2--;}
55             ++now;
56         }
57     }
58     return 0;
59 }

View Code

LOJ P1155 双栈排序 二分图染色 图论

LOJ P1155 双栈排序二分图染色图论