P1155 双栈排序（二分图的染色判断+链式前向星）

Orianna ·

更新时间:2024-09-21

· 996 次阅读

P1155 双栈排序

在这里插入图片描述

让字典序最小，当然尽量进S1
那什么时候必须进S2呢？
a[i]和a[j] 不能压入同一个栈⇔存在一个k,使得i<j<k且a[k]<a[i]<a[j]
因为一个数只能进出一次，k要排在前面所以弹出k时i和j都在栈里，如果两者在同一个栈弹出后顺序就错误了
对于任意两个数t[i]和t[j],它们不能压入同一个栈中的充要条件: 存在一个k,使得i<j<k且t[k]<t[i]<t[j]。
证明：利用反证法，假设当这t[i]，t[j]压入了同一个栈，那么压入t[k]，因为t[k]<t[i]t[i]，矛盾，所以假设不成立。
由此，我们便可根据这些来解决此题了。
这样i和j连一条边然后二分图染色再用栈模拟就行了，因为数据是1…n维护cur表示当前该弹出哪个数字
PS：1.建图时先DP用f[i]表示i…n中最小元素
　　2.二分图染色可以解决一些有关系，分成两类的问题　
题解参考
本题中使用链式前向星存二分图
链式前向星

#include
using namespace std;
#define debug(x) cout<<"#  "<<x<<" "<=1;i--)f[i]=min(f[i+1],a[i]);
    for(int i=1;i<=n;++i)
        for(int j=i+1;j<=n;++j)
            //如果存在k,满足i<j<k&&a[k]<a[i]<a[j],那么i和j是不能存在一边的集合中的
            if(a[i]<a[j]&&f[j]<a[i])
                init(i,j);
}
ll col[N];
bool color(ll u,ll c)
{
    col[u]=c;
    for(int i=h[u];i;i=G[i].ne)
    {
        ll v=G[i].v;
        if(col[v]==col[u])return false;
        if(!col[v]&&!color(v,3-c))return false;
    }
    return true;
}
ll s1[N],s2[N],t1,t2;
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;++i)scanf("%lld",&a[i]);
    dp();
    for(int i=1;i<=n;++i)
        if(!col[i]&&!color(i,1))
        {
            puts("0");
            return 0;
        }
    ll cur=1;
    for(int i=1;i<=n;++i)
    {
        if(col[i]==1)
            s1[++t1]=a[i],cout<<"a ";
        else s2[++t2]=a[i],cout<<"c ";
        //输入的数是1~n 的
        while(s1[t1]==cur||s2[t2]==cur)//边入边出
        {
            if(s1[t1]==cur)cout<<"b ",t1--;
            else cout<<"d ",t2--;
            cur++;
        }
    }
    cout<<endl;
    return 0;
}

作者：繁凡さん

二分二分图 p1 排序

1024 个赞