noip2008 双栈排序

题目描述 Description

$Tom$最近在研究一个有趣的排序问题。如图所示，通过$2$个栈$S_1$和$S_2$，$Tom$希望借助以下$4$种操作实现将输入序列升序排序。

操作$a$

如果输入序列不为空，将第一个元素压入栈$S_1$

操作$b$

如果栈$S_1$不为空，将$S_1$栈顶元素弹出至输出序列

操作$c$

如果输入序列不为空，将第一个元素压入栈$S_2$

操作$d$

如果栈$S_2$不为空，将$S_2$栈顶元素弹出至输出序列

如果一个$1$到$n$的排列$P$可以通过一系列操作使得输出序列为$1，2，…，(n-1)，n$，$Tom$就称$P$是一个“可双栈排序排列”。例如$(1,3,2,4)$就是一个“可双栈排序序列”，而$(2,3,4,1)$不是。下图描述了一个将$(1,3,2,4)$排序的操作序列：$a,c,c,b,a,d,d,b$

输入描述 Input Description

输入的第一行是一个整数n。

第二行有$n$个用空格隔开的正整数，构成一个$1$到$n$的排列。

输出描述 Output Description

输出共一行，如果输入的排列不是“可双栈排序排列”，输出数字$0$；否则输出字典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。

当然，这样的操作序列有可能有几个，对于上例$(1,3,2,4)$，$a,c,c,b,a,d,d,b$是另外一个可行的操作序列。$Tom$希望知道其中字典序最小的操作序列是什么。

　　把以前不会写的$noip$题目补一下~其实现在我也还是不会。

　　感觉这道题思路非常神……首先，贪心的选显然是错误的，因为不能保证可以构造出一组可行解。然后……这道题到底该怎么做啊啊啊！

　　于是到最后我还是去看题解了……

　　这道题首先要证明一个结论：对于任意两个数$a_i$和$a_j$来说,它们不能压入同一个栈(不仅仅指同时在栈中，而是压入了同一个栈)中的充要条件是：存在一个$k$，使得$i<j<k$且$a_k<a_i<a_j$ 。

　　首先证明充分性。由于$a_k<a_i$，那么当$a_k$入栈时，$a_i$还没有被弹出，那么如果$a_i$和$a_j$被压入同一个栈$a_j$就会比$a_i$先出栈，无解。

　　然后证明必要性。这个东西比较难证，于是我们可以转而证明它的逆否命题：若对于任意的$i<j<k$,不满足$a_k<a_i<a_j$_，那么他们可以压入一个栈。

　　对于不满足$a_k<a_i<a_j$有两种情况：一是$a_k>a_i$，二是$a_i>a_j$。

　　对于第一种情况，由于$a_k>a_i$，所以在$a_k$入栈之前$a_i$已经可以弹出，于是可以压入同一个栈。

　　对于第二种情况，显然不论$a_k$大小如何，都可以先把$a_i$和$a_j$压入同一个栈，$a_j$会先于$a_i$弹出。

　　于是该命题的逆否命题得证，所以原命题得证。

　　于是，这个问题就变成了二分图的问题了。把不可以压入同一个栈的点连边，然后判断一个图不是二分图就无解，否则有解。

　　然后就是字典序最小的问题了。由于字典序最小需要靠前的数尽量往第一个栈里丢，所以可以从前到后判断一下，在二分图中$dfs$一遍。

　　于是这道题就这么愉快的解决辣！话说考场上碰到这种题我真的写得出来吗？

　　小结一下：1.碰到一类毫无思路的问题时，要推一推题目中有没有什么奇妙的性质；

　　　　　　 2.发现自己的复杂度远过低时，一定要多检查几遍；

　　　　　　 3.一定要先写暴力，可以用来验证自己猜的结论。

　　下面贴代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)

#define N 1010

using namespace std;

typedef long long llg;

int n,a[N<<1],wa[N],co[N],b[N],lb;

int head[N],next[N*N],to[N*N],tt;

int s1[N],t1,s2[N],t2,now=1;

bool vis[N];

int getint(){

    int w=0;bool q=0;

    char c=getchar();

    while((c>'9'||c<'0')&&c!='-') c=getchar();

    if(c=='-') c=getchar(),q=1;

    while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar();

    return q?-w:w;

}

void link(int x,int y){

    to[++tt]=y;next[tt]=head[x];head[x]=tt;

    to[++tt]=x;next[tt]=head[y];head[y]=tt;

}

bool ran(int u){

    bool ww=0;

    for(int i=head[u],v;v=to[i],i;i=next[i])

        if(co[v]==co[u]) return 0;

        else if(!co[v]) co[v]=3-co[u],ww|=!ran(v);

    return !ww;

}

void dfs(int u,bool w){

    if(w) co[u]=3-co[u]; vis[u]=1;

    for(int i=head[u],v;v=to[i],i;i=next[i])

        if(!vis[v]) dfs(v,w);

}

int main(){

    File("a");

    n=getint(); wa[n+1]=2147483647;

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

    for(int i=n;i>=1;i--) wa[i]=min(wa[i+1],a[i]);

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

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

            if(a[i]<a[j] && a[i]>wa[j+1]) link(i,j);

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

        if(!co[i]){

            co[i]=1;

            if(!ran(i)){

                printf("0");

                return 0;

            }

        }

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

        if(!vis[i]) dfs(i,co[i]!=1);

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

        if(co[i]==1) s1[++t1]=a[i],b[++lb]=1;

        if(co[i]==2) s2[++t2]=a[i],b[++lb]=3;

        while(s1[t1]==now || s2[t2]==now){

            if(s1[t1]==now) t1--,b[++lb]=2;

            if(s2[t2]==now) t2--,b[++lb]=4;

            now++;

        }

    }

    for(int i=1;i<=lb;i++) printf("%c ",'a'+b[i]-1);

}

　　UPD：最近发现被hack了……于是就重写了一份，代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)

#define N 1010

using namespace std;

typedef long long llg;

int n,a[N<<1],wa[N],co[N],b[N],lb;

int hd[N],nt[N*N],to[N*N],tt;

int s1[N],t1,s2[N],t2,now=1;

bool vis[N];

int getint(){

	int w=0;bool q=0;

	char c=getchar();

	while((c>'9'||c<'0')&&c!='-') c=getchar();

	if(c=='-') c=getchar(),q=1;

	while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar();

	return q?-w:w;

}

void link(int x,int y){

	to[++tt]=y;nt[tt]=hd[x];hd[x]=tt;

	to[++tt]=x;nt[tt]=hd[y];hd[y]=tt;

}

void ran(int u){

	for(int i=hd[u],v;v=to[i],i;i=nt[i])

		if(co[v]==co[u]){printf("0");exit(0);}

		else if(!co[v]) co[v]=3-co[u],ran(v);

}

int main(){

	File("a");

	n=getint(); wa[n+1]=2147483647;

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

	for(int i=n;i>=1;i--) wa[i]=min(wa[i+1],a[i]);

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

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

			if(a[i]<a[j] && a[i]>wa[j+1]) link(i,j);

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

		if(!co[i]) co[i]=1,ran(i);

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

		if(co[i]==1){

			if(t1 && a[i]>s1[t1])

				while(s1[t1]==now || s2[t2]==now){

					if(s1[t1]==now) t1--,b[++lb]=2;

					if(s2[t2]==now) t2--,b[++lb]=4;

					now++;

				}

			s1[++t1]=a[i],b[++lb]=1;

		}

		if(co[i]==2){

			if(t2 && b[i]>s2[t2])

				while(s1[t1]==now || s2[t2]==now){

					if(s1[t1]==now) t1--,b[++lb]=2;

					if(s2[t2]==now) t2--,b[++lb]=4;

					now++;

				}

			s2[++t2]=a[i]; b[++lb]=3;

		}

		while(s1[t1]==now) t1--,b[++lb]=2,now++;

	}

	while(s1[t1]==now || s2[t2]==now){

		if(s1[t1]==now) t1--,b[++lb]=2;

		if(s2[t2]==now) t2--,b[++lb]=4;

		now++;

	}

	for(int i=1;i<=lb;i++) printf("%c ",'a'+b[i]-1);

}

巴特西

noip2008 双栈排序

题目描述 Description

输入描述 Input Description

输出描述 Output Description

最新文章

热门文章