noip2008 双栈排序题解 二分图染色

双栈排序

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

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

把每个元素按照输入序列中的顺序编号,看作一个图中的每个顶点.这时,我们对所有的(i,j)满足i<j,判断是否满足结论P,即S[i],S[j]两个元素能否进入同一个栈.

如果满足P,则在i,j之间连接一条边.

我们对图染色,由于只有两个栈,我们得到的图必须是二分图才能满足条件.

由于要求字典序最小,即尽量要进入栈1，贪心，我们按编号递增的顺序从每个未染色的顶点开始染色,相邻的顶点染上不同的色,

如果发生冲突,则是无解的.否则我们可以得到每个顶点颜色,即应该进入的栈.

接下来就是输出序列了,知道了每个元素的决策,直接模拟了；

在判断数对(i,j)是否满足P时,枚举检查是否存在k的时间复杂度是O(n),则总的时间复杂度是O(n^3),对于n=1000是太大了.这原因在于过多得枚举了k,我们可以用动态规划把枚举k变为O(1)的算法.

设F[i]为Min{S[i],S[i+1],S[i+2]..S[n-1],S[n]},状态转移方程为F[i]=Min{ S[i] , F[i+1] }.边界为F[N+1]=极大的值.

判断数对(i,j)是否满足P,只需判断(S[i]<S[j] 并且 F[j+1]<S[i])即可.时间复杂度为O(n^2).

#include<bits/stdc++.h>
using namespace std;

template<typename T>inline void read(T &x)
{
    x=0;T f=1,ch=getchar();
    while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
    while(isdigit(ch))  {x=(x<<1)+(x<<3)+(ch^48);  ch=getchar();}
    x*=f;
}
const int N=1010;
int n,v[N],f[N],lin[N],s[N],tot;
int s1[N],s2[N],cnt1,cnt2;
struct gg {
    int y,next;
}a[2000005];

inline void add(int x,int y) {
    a[++tot].y=y; a[tot].next=lin[x]; lin[x]=tot;
    a[++tot].y=x; a[tot].next=lin[y]; lin[y]=tot;
}

bool color(int x,int cl)
{
    v[x]=cl;
    for(int i=lin[x];i;i=a[i].next)
    {
        if(!v[a[i].y])
        {
            if(!color(a[i].y,3-cl)) return 0;
        }
        else if(v[a[i].y]==cl)return 0; 
    } 
    return 1;
}

int main() {
    read(n);
    for(int i=1;i<=n;i++) read(s[i]);
    f[n+1]=1000000000;
    for(int i=n;i;i--) f[i]=min(f[i+1],s[i]);
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++) {
            if(s[i]<s[j]&&f[j+1]<s[i]) {
                add(i,j);
            }
        }
     for(int i=1;i<=n;i++)
        if(!v[i])
            if(!color(i,1)){puts("0");return 0;}
    int now=1;
    for(int i=1;i<=n;i++) {
        if(v[i]==1) printf("a "),s1[++cnt1]=s[i];
        else printf("c "),s2[++cnt2]=s[i];
        while(s1[cnt1]==now||s2[cnt2]==now) {
            if(s1[cnt1]==now) printf("b "),cnt1--;
            else printf("d "),cnt2--;
            now++;
        }
    }
    return 0;
}