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

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

開始讀的代碼來自?http://hzwer.com/5071.html

結論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

?

轉載于:https://www.cnblogs.com/137shoebills/p/9063886.html

總結

以上是生活随笔為你收集整理的LOJ P1155 双栈排序 二分图染色 图论的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。