$NOIP2008$双栈序列

\(NOIP2008\)双栈序列

考虑什么情况无法成立，这样就可以知道那些数不能在同一个栈中出现。

建图跑二分图染色，\(1\)的在一个栈中，\(0\)的在一个栈中即可。

最后模拟就好了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
    int f=1,w=0;char x=0;
    while(x<'0'||x>'9') {if(x=='-') f=-1; x=getchar();}
    while(x!=EOF&&x>='0'&&x<='9') {w=(w<<3)+(w<<1)+(x^48);x=getchar();}
    return w*f;
}
const int N=1e3+10;
const int M=1e6+10;
char ans[M];
stack<int> Stk1,Stk2;
int n,Cnt,Now,num_edge;
int A[N],Col[N],Las[N],head[M<<1];
struct Edge{int next,to;} edge[M<<1];
inline void Add(int from,int to)
{
    edge[++num_edge].next=head[from];
    edge[num_edge].to=to;
    head[from]=num_edge;
}
inline void Dfs(int pos,int fth)
{
    if(Col[pos]==-1&&Col[fth]==1) Col[pos]=0;
    if(Col[pos]==-1&&Col[fth]==0) Col[pos]=1;
    if(!(Col[pos]^Col[fth])) {puts("0");exit(0);}
    for(int i=head[pos];i;i=edge[i].next)
        if(edge[i].to!=fth) Dfs(edge[i].to,pos);
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("twostack.in","r",stdin);
    freopen("twostack.out","w",stdout);
#endif
    int k=1;n=read();
    for(int i=1;i<=n;i++) A[i]=read();
    for(int i=1;i<=n;i++)
        for(int j=n;j>=i+1;j--)
            if(A[i]>A[j]) {Las[i]=j;break;}
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=Las[i];j++)
            if(A[i]<A[j]) Add(i,j),Add(j,i);
    memset(Col,-1,sizeof(Col));Col[0]=0;
    for(int i=1;i<=n;i++) if(Col[i]==-1) Dfs(i,0);
    while(233)
    {
        if(k<=n&&Col[k]==1)
        {
            Stk1.push(A[k++]);ans[++Cnt]='a';
            while(Stk1.size()&&Stk1.top()==Now+1) ans[++Cnt]='b',Now++,Stk1.pop();
            continue;
        }
        while(Stk1.size()&&Stk1.top()==Now+1) ans[++Cnt]='b',Now++,Stk1.pop();
        if(k<=n&&Col[k]==0)
        {
            Stk2.push(A[k++]);ans[++Cnt]='c';
            while(Stk2.size()&&Stk2.top()==Now+1) ans[++Cnt]='d',Now++,Stk2.pop();
            continue;
        }
        while(Stk2.size()&&Stk2.top()==Now+1) ans[++Cnt]='d',Now++,Stk2.pop();
        if(Now==n) break;
    }
    
    for(int i=1;i<=Cnt;i++) printf("%c ",ans[i]);
}

$NOIP2008$双栈序列

原文：https://www.cnblogs.com/wo-shi-zhen-de-cai/p/11749333.html