luogu P1155 双栈排序

骗分

首先看到这道题我最先想到的是模拟
但问题是其要求字典序最小，这就很麻烦了
假设这个条件没有（也就是假装数据很弱去骗分）
首先对于一个数，他只能加入空栈或栈顶的数比这个数大的栈
为了经可能有解，每次都加入栈顶数最小的栈
也就是说将空栈先加入一个极大值
然后模拟即可得到50分

#include <bits/stdc++.h>
using namespace std;
int read()
{
    long long tot=0,fs=1;
    char ch;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') ch=getchar(),fs=-1;
    while(ch>='0'&&ch<='9') tot=tot*10+ch-'0',ch=getchar();
    return tot*fs;
}
int now=1;
int sta1[1009],sta2[1009],top1,top2;
int n; 
char ans[100009];
int lenans;
int main() 
{
    n=read();
    sta1[0]=2000000000,sta2[0]=2000000000;
    for(int i=1,ls;i<=n;i++)
    {
        ls=read();
        if(ls==now) now++,ans[++lenans]='a',ans[++lenans]='b';
        else 
        {
            if(ls<sta1[top1]&&ls<sta2[top2])
            {
                if(sta1[top1]<=sta2[top2])
                {
                    sta1[++top1]=ls;
                    ans[++lenans]='a';
                }
                else
                {
                    sta2[++top2]=ls;
                    ans[++lenans]='c';
                }
            }
            else if(ls<sta1[top1])
            {
                sta1[++top1]=ls;
                ans[++lenans]='a';
            }
            else if(ls<sta2[top2])
            {
                sta2[++top2]=ls;
                ans[++lenans]='c';
            }
            else
            {
                cout<<0;
                return 0;    
            }
        }
        while(sta1[top1]==now||sta2[top2]==now)
        {
            if(sta1[top1]==now)
            {
                ans[++lenans]='b';
                top1--;
            }
            else 
            {
                ans[++lenans]='d';    
                top2--;
            }
            now++;
        }
    }
    for(int i=1;i<=lenans;i++)
    {
        printf("%c ",ans[i]);    
    }
}

实际上也可以加入随机化来加强骗分（在有两个选择的情况下，小概率无脑选1）

正解

如果a[i],a[j]两个数不在同一个栈中，则必定存在i<j<k且a[k]<a[i]<a[j]
暴力枚举为O(n^3)
考虑消去k这一纬
枚举k的意义就是找到在j后面且比j小的数
那么只要维护后缀最大值就行了
然后无解的情况就是 a不和b一起
但c不和b一起也不和a一起
就至少需要三个栈了（所以说这道题可以改编成问至少要有几个栈）
ok那我们就可进行染色看是否存在颜色冲突即可（优先染成一号栈的颜色）
然后既然颜色已知，按照骗分的方法模拟即可

#include <bits/stdc++.h>
using namespace std;
int read()
{
    long long tot=0,fs=1;
    char ch;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') ch=getchar(),fs=-1;
    while(ch>='0'&&ch<='9') tot=tot*10+ch-'0',ch=getchar();
    return tot*fs;
}
int n;
int a[1009];
int f[1009];
int sta1[10009],sta2[10009];
int top1,top2;
int head[1009],nt[200009],to[200009],bh;
int tot=1;
int color[1009];
int mark[1009];
void add(int u,int v)
{
    bh++;
    to[bh]=v;
    nt[bh]=head[u];
    head[u]=bh;
}
void bfs(int x)
{
    queue<int> q;
    q.push(x);
    color[x]=1;
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        for(int i=head[now];i;i=nt[i])
        {
            int nt=to[i];
            if(color[nt]==-1)
            {
                color[nt]=color[now]^1;
                q.push(nt);
            }
            else if(color[nt]!=(color[now]^1))
            {
                cout<<0;
                exit(0);    
            }
        }
    }
}
int main() 
{
    memset(color,-1,sizeof(color));
    n=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();    
    }
    f[n+1]=2000000000;
    for(int i=n;i;i--)
    {
        f[i]=min(f[i+1],a[i]);    
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(a[i]>f[j+1]&&a[i]<a[j])
            {
                add(i,j);
                add(j,i);
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(color[i]==-1) bfs(i);    
    }
    for(int i=1;i<=n;i++)
    {
        if(color[i])
        {
            sta1[++top1]=a[i];
            printf("a ");
        }
        else
        {
            sta2[++top2]=a[i];
            printf("c ");    
        }
        while(sta1[top1]==tot||sta2[top2]==tot)
        {
            if(sta1[top1]==tot)
            {
                printf("b ");
                top1--;    
            }
            else
            {
                printf("d ");
                top2--;
            }
            tot++;    
        }
    }
}