Luogu1155 NOIP2008双栈排序（并查集）

时间：2022-09-24 14:40:35

　　两个位置i和j上的元素不能被放进同一个栈的充要条件显然是存在k使i<j<k且ak<ai<aj。由此在保证合法的情况下贪心地放就是正确的了。

　　至于如何判断，可以记一下后缀最小值，每找到一对就利用补集并查集合并。放的时候要求与该栈所有元素不排斥且与另一个栈的元素不存在强制同栈的关系。

　　怎么感觉远古时代noip都这么困难啊。没救了。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 1010

int n,a[N],mn[N],fa[N<<],stk1[N],stk2[N],top1=,top2=,tot=,cur=;

char ans[N<<];

int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

void merge(int x,int y){fa[find(x+n)]=find(y),fa[find(y+n)]=find(x);}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("stack.in","r",stdin);

    freopen("stack.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read();

    for (int i=;i<=n;i++) a[i]=read();

    mn[n+]=n+;for (int i=n;i;i--) mn[i]=min(a[i],mn[i+]);

    for (int i=;i<=n+n;i++) fa[i]=i;

    for (int i=;i<=n;i++)

        for (int j=i+;j<=n;j++)

        if (a[i]<a[j]&&mn[j+]<a[i]) merge(i,j);

    for (int i=;i<=n;i++)

    {

        while (a[stk1[top1]]==cur+) cur++,ans[++tot]='b',top1--;

        bool flag=;

        for (int j=;j<=top1;j++) if (find(stk1[j]+n)==find(i)) {flag=;break;}

        for (int j=;j<=top2;j++) if (find(stk2[j])==find(i)) {flag=;break;}

        if (flag) stk1[++top1]=i,ans[++tot]='a';

        else

        {

            while (a[stk1[top1]]==cur+||a[stk2[top2]]==cur+)

            if (a[stk1[top1]]==cur+) cur++,ans[++tot]='b',top1--;

            else cur++,ans[++tot]='d',top2--;

            flag=;

            for (int j=;j<=top1;j++) if (find(stk1[j])==find(i)) {flag=;break;}

            for (int j=;j<=top2;j++) if (find(stk2[j]+n)==find(i)) {flag=;break;}

            if (flag) stk2[++top2]=i,ans[++tot]='c';

            else {cout<<;return ;}

        }

    }

    while (top1||top2)

    if (top1&&a[stk1[top1]]<a[stk2[top2]]||top2==) ans[++tot]='b',top1--;

    else ans[++tot]='d',top2--;

    for (int i=;i<=tot;i++) cout<<ans[i]<<' ';

    return ;

}

相关文章