This post is written in Chinese. Please consider using Google Translate

这道题的错误做法很多,但是实际在考场上，大多数人拿到了30分。错误做法却能得满分的也很多,正确的算法是基于二分图的算法。注意，不是二分图匹配！

分析条件，我们把问题抽象为数学模型。设输入序列为S，考虑S[i],S[j]两个元素不能进入同一个栈的条件.注意,这里所说的"S[i],S[j]两个元素不能进入同一个栈",不是说仅仅不能同时在一个栈中,而是自始至终不能进入一个栈,即如果有解,那么S[i],S[j]一定进入过的栈不同.

结论P: S[i],S[j]两个元素不能进入同一个栈 <=> 存在k,满足i<j<k,使得S[k]<S[i]<S[j]. 证明略过,请参考sqybi.尝试后可以发现结论P是正确的.

把每个元素按照输入序列中的顺序编号,看作一个图中的每个顶点.这时,我们对所有的(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).

参考资料:sqybi的题解

/* 
 * Problem: NOIP2008 twostack
 * Author: Guo Jiabao
 * Time: 2008.12.9 21:22:52
 * State: Solved 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;

const int MAXN=1002;
const int INF=0x7FFFFFFF;

class tStack
{
    private:
        int top;
        int S[MAXN];
    public:
        tStack() : top(0) {}
        void ins(int k)
        {
            S[++top]=k;
        }
        int tp()
        {
            return S[top];
        }
        void pop()
        {
            top--;
        }
};

int S[MAXN],F[MAXN],bel[MAXN];
bool adjm[MAXN][MAXN];
int N,top1,top2;
tStack T[3];

void init()
{
    int i;
    freopen("twostack.in","r",stdin);
    freopen("twostack.out","w",stdout);
    scanf("%d",&N);
    for (i=1;i<=N;i++)
    {
        scanf("%d",&S[i]);
    }
}

void noanswer()
{
    printf("0");
    exit(0);
}

void color(int i,int c)
{
    bel[i]=c;
    int j;
    for (j=1;j<=N;j++)
    {
        if (adjm[i][j])
        {
            if (bel[j]==c) //conflict : not a bipartite graph
            {
                noanswer();
            }
            if (!bel[j])
            {
                color(j,3-c); // color the opposite color 1<->2
            }
        }
    }
}

void dye()
{
    int i,j;
    F[N+1]=INF;
    for (i=N;i>=1;i--)
    {
        F[i]=S[i];
        if (F[i+1]<F[i])
            F[i]=F[i+1];
    }
    for (i=1;i<=N-1;i++)
    {
        for (j=i+1;j<=N;j++)
        {
            if (S[i]<S[j] && F[j+1]<S[i])
            {
                adjm[i][j]=adjm[j][i]=true;
            }
        }
    }
    for (i=1;i<=N;i++)
    {
        if (!bel[i])
        {
            color(i,1);
        }
    }
}

void solve()
{
    int i,should=1,s;
    for (i=1;i<=N;i++)
    {
        s=bel[i];
        if (s==1)
        {
            T[1].ins(S[i]);
            printf("a ");
        }
        else
        {
            T[2].ins(S[i]);
            printf("c ");
        }
        while (T[1].tp()==should || T[2].tp()==should)
        {
            if (T[1].tp()==should)
            {
                T[1].pop();
                printf("b");
                if (should!=N)
                    printf(" ");
                should++;
            }
            else
            {
                T[2].pop();
                printf("d");
                if (should!=N)
                    printf(" ");
                should++;
            }
        }
    }
}

int main()
{
    init();
    dye();
    solve();
    return 0;
}