[NOIP2008]双栈排序

NOIP 解题记录 二分图

参考资料：[NOIp2008] 双栈排序 (二分图染色 + 贪心) 题解
题目链接：[NOIP2008]双栈排序

题目大意：

有一个长度为 $n$ 的序列（是 $1-n$ 的排列），现在有 $2$ 个栈 $S_1$，$S_2$，$4$ 个操作。

操作 $a$：如果输入序列不为空，将第一个元素压入栈 $S_1$
操作 $b$：如果栈 $S_1$ 不为空，将 $S_1$ 栈顶元素弹出至输出序列
操作 $c$：如果输入序列不为空，将第一个元素压入栈 $S_2$
操作 $d$：如果栈 $S_2$ 不为空，将 $S_2$ 栈顶元素弹出至输出序列

判断是否能使得输出序列升序排序，
若不能，则输出 $0$；
若能，则输出字典序最小的操作序列。

解题思路：

首先思考如何判断是否能使得输出序列升序排序。

考虑三个原序列的下标 $i,j,k$，满足 $i<j<k$，
若 $val[k]<val[i]<val[j]$，则 $i,j$ 不能进入同一个栈中。

原因：

若 $i,j,k$ 进入同一个栈中，由于 $val[i]<val[j]$，$i$ 要比 $j$ 先出栈；
而由于 $val[k]<val[i]<val[j]$，所以 $k$ 要比 $i,j$ 先出栈，$k$ 若要出栈，首先要进栈 废话，$k$ 若要进栈，那么 $i,j$ 就要先进栈，就会使得 $j$ 比 $i$ 先出栈，就产生了矛盾。

为了判断这个矛盾是否会导致无法排序，我们选择使用二分图染色，
在有矛盾的 $i,j$ 之间连一条边（无向边），然后对这张图进行染色，若不是二分图，则无法排序，输出 0。

判断完了是否能正确排序后，我们就可以思考如何取字典序最小的操作序列了。

首先考虑怎么使操作是正确的，即操作后能产生升序序列。
大体思路就是将序列中的每个数依次压入它属于的栈中（属于哪个栈在二分图染色时就可以标记好），在将这个数压入栈前，我们要先判断压入之后栈是否仍然单调，若不单调，则一直弹出栈顶元素，直到单调为止。
注意：在弹出栈顶元素时，栈顶的元素可能不是当前应当弹出的数（因为我们要使得输出序列的元素是递增的），所以我们需要一个变量 $now$，表示当前应当弹出的数，若该栈顶的数不等于 $now$，就弹出另外一个栈顶的数。

在考虑以上条件之后，我们就可以输出正确的操作序列了，那要怎么才能输出字典序最小的呢？
同一个栈的压入和弹出的相对顺序似乎改变不了（好像是吧），那么我们就考虑两个栈的操作之间的顺序吧。
既然 $S_1$ 的操作的字典序更小，那么我们可以想一下什么时候能先进行 $S_1$ 的操作。由于压栈的顺序是一定的，那么我们就考虑弹出操作，在压入属于 $S_2$ 的数之前，我们可以先把 $S_1$ 中能弹出的数都弹出来，这样就可以使得字典序最小了。

说是这么说，但这道题我一点思路都没有，全都是看题解写出来的……

代码实现

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int N=1000+7;
int n,val[N],minx[N],col[N];
bool flag;
vector<int> p[N];
void init(){
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%d",&val[i]);
    minx[n+1]=n+1;
    for(int i=n;i>=1;i--)
        minx[i]=min(minx[i+1],val[i]);
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            if(val[i]<val[j]&&minx[j+1]<val[i]) p[i].push_back(j),p[j].push_back(i);
}
void run(){
    for(int i=1;i<=n;i++)
        if(!col[i]){
            queue<int> q;
            col[i]=1;
            q.push(i);
            while(!q.empty()){
                int u=q.front();
                q.pop();
                for(int j=0;j<p[u].size();j++){
                    int v=p[u][j];
                    if(col[v]){
                        if(col[v]==col[u]){
                            flag=1;
                            return;
                        }
                        continue;
                    }
                    col[v]=3-col[u];
                    q.push(v);
                }
            }
        }
}
struct stack{
    int a[N],p=0;
    int top(){ return a[p]; }
    bool empty(){ return p==0; }
    void pop(){ if(p) p--;}
    void push(int x){ a[++p]=x; }
}s[3];
int now;
bool judge(int id){
    if(s[id].empty()||s[id].top()!=now+1) return 0;
    return 1;
}
void Pop(int id){
    now++;
    s[id].pop();
    putchar(id==1 ?'b' :'d');
    putchar(' ');
}
void Push(int v,int id){
    if(id==2) while(judge(1)) Pop(1);
    while(!s[id].empty()&&s[id].top()<v){
        if(!judge(id)) Pop(3-id);
        else Pop(id);
    }
    if(id==2) while(judge(1)) Pop(1);
    s[id].push(v);
    putchar(id==1 ?'a' :'c');
    putchar(' ');
}
void print(){
    for(int i=1;i<=n;i++){
        Push(val[i],col[i]);
    }
    while(!s[1].empty()){
        if(!judge(1)) Pop(2);
        else Pop(1);
    }
    while(!s[2].empty()) Pop(2);
}
int main(){
    //freopen("1.txt","r",stdin);
    //freopen("2.txt","w",stdout);
    init();
    run();
    if(flag){
        printf("0");
        return 0;
    }
    print();
    return 0;
}
/*
4
1 3 2 4
*/