VIJOS 1605 双栈排序
发布日期:2022-02-05 18:27:31 浏览次数:5 分类:技术文章

本文共 4548 字,大约阅读时间需要 15 分钟。

描述

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

操作a
如果输入序列不为空,将第一个元素压入栈S1
操作b
如果栈S1不为空,将S1栈顶元素弹出至输出序列
操作c
如果输入序列不为空,将第一个元素压入栈S2
操作d
如果栈S2不为空,将S2栈顶元素弹出至输出序列

如果一个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>

当然,这样的操作序列有可能有几个,对于上例(1,3,2,4),<a,c,c,b,a,d,d,b>是另外一个可行的操作序列。

Tom希望知道其中字典序最小的操作序列是什么。

格式

输入格式

第一行是一个整数n。

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

输出格式

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

样例

样例输入

41 3 2 4

样例输出

a b a a b b a b

限制

1s

提示

30%的数据满足: n<=10
50%的数据满足: n<=50
100%的数据满足: n<=1000

来源

NOIP2008 提高组第4题




一开始看到这个题真心不会 不过想到字典序最小 就想到了贪心

虽然感觉T4不可能是显而易见的贪心题目 但是无奈还是写了一个错误的贪心 可以得30

贪心的思路是这样的

首先第一个肯定放在栈1中 然后后面的尽可能放在1中 如果1中的栈顶小于要放的数 就放在栈2中 如果栈1 2 顶都小于要放的数 输出0

这个贪心一开始没发现什么问题 知道交上去WA30才明白

如果一组数据中 10  8  7  9

贪心的话是会出0的 因为1放10  2放8   1放7  后 9哪一个都放不下了

其实1放10   2放8   2放7    1放9  就可以排序了

所以贪心是错误的 



无奈只能去网上找题解了 没想到这居然是一个二分图验证的模型

尼玛!!!我这种蒟蒻怎么会看出来呢!!!!!!!


时间关系 我就直接抄过来了


======================================================================================================

这道题大概可以归结为如下题意:
有两个队列和两个栈,分别命名为队列1(q1),队列2(q2),栈1(s1)和栈2(s2).最初的时候,q2,s1和s2都为空,而q1中有n个数(n<=1000),为1~n的某个排列.
现在支持如下四种操作:
a操作,将 q1的首元素提取出并加入s1的栈顶.
b操作,将s1的栈顶元素弹出并加入q1q2的队列尾.
c操作,将 q1的首元素提取出并加入s2的栈顶.
d操作,将s2的栈顶元素弹出并加入q1q2的队列尾.
请判断,是否可以经过一系列操作之后,使得q2中依次存储着1,2,3,…,n.如果可以,求出字典序最小的一个操作序列.

这道题的错误做法很多,错误做法却能得满分的也很多,这里就不多说了.直接切入正题,就是即将介绍的这个基于二分图的算法.
注意到并没有说基于二分图匹配,因为这个算法和二分图匹配无关.这个算法只是用到了给一个图着色成二分图.

第一步需要解决的问题是,判断是否有解.

考虑对于任意两个数q1[i]和q1[j]来说,它们不能压入同一个栈中的充要条件是什么(注意没有必要使它们同时存在于同一个栈中,只是压入了同一个栈).实际上,这个条件p是:存在一个k,使得i<j<k且q1[k]<q1[i]<q1[j].

首先证明充分性,即如果满足条件p,那么这两个数一定不能压入同一个栈.这个结论很显然,使用反证法可证.
假设这两个数压入了同一个栈,那么在压入q1[k]的时候栈内情况如下:
…q1[i]…q1[j]…
因为q1[k]比q1[i]和q1[j]都小,所以很显然,当q1[k]没有被弹出的时候,另外两个数也都不能被弹出(否则q2中的数字顺序就不是1,2,3,…,n了).
而之后,无论其它的数字在什么时候被弹出,q1[j]总是会在q1[i]之前弹出.而q1[j]>q1[i],这显然是不正确的.

接下来证明必要性.也就是,如果两个数不可以压入同一个栈,那么它们一定满足条件p.这里我们来证明它的逆否命题,也就是"如果不满足条件p,那么这两个数一定可以压入同一个栈."
不满足条件p有两种情况:一种是对于任意i<j<k且q1[i]<q1[j],q1[k]>q1[i];另一种是对于任意i<j,q1[i]>q1[j].
第一种情况下,很显然,在q1[k]被压入栈的时候,q1[i]已经被弹出栈.那么,q1[k]不会对q1[j]产生任何影响(这里可能有点乱,因为看起来,当q1[j]<q1[k]的时候,是会有影响的,但实际上,这还需要另一个数r,满足j<k<r且q1[r]<q1[j]<q1[k],也就是证明充分性的时候所说的情况…而事实上我们现在并不考虑这个r,所以说q1[k]对q1[j]没有影响).
第二种情况下,我们可以发现这其实就是一个降序序列,所以所有数字都可以压入同一个栈.
这样,原命题的逆否命题得证,所以原命题得证.

此时,条件p为q1[i]和q1[j]不能压入同一个栈的充要条件也得证.

这样,我们对所有的数对(i,j)满足1<=i<j<=n,检查是否存在i<j<k满足p1[k]<p1[i]<p1[j].如果存在,那么在点i和点j之间连一条无向边,表示p1[i]和p1[j]不能压入同一个栈.此时想到了什么?那就是二分图~
二分图的两部分看作两个栈,因为二分图的同一部分内不会出现任何连边,也就相当于不能压入同一个栈的所有结点都分到了两个栈中.
此时我们只考虑检查是否有解,所以只要O(n)检查出这个图是不是二分图,就可以得知是否有解.

此时,检查有解的问题已经解决.接下来的问题是,如何找到字典序最小的解.
实际上,可以发现,如果把二分图染成1和2两种颜色,那么结点染色为1对应当前结点被压入s1,为2对应被压入s2.为了字典序尽量小,我们希望让编号小的结点优先压入s1.
又发现二分图的不同连通分量之间的染色是互不影响的,所以可以每次选取一个未染色的编号最小的结点,将它染色为1并从它开始DFS染色,直到所有结点都被染色为止.这样,我们就得到了每个结点应该压入哪个栈中.接下来要做的,只不过是模拟之后输出序列啦~

还有一点小问题,就是如果对于数对(i,j),都去枚举检查是否存在k使得p1[k]<p1[i]<p1[j]的话,那么复杂度就升到了O(n^3).解决方法就是,首先预处理出数组b,b[i]表示从p1[i]到p1[n]中的最小值.接下来,只需要枚举所有数对(i,j),检查b[j+1]是否小于p1[i]且p1[i]是否小于p1[j]就可以了.    From:

======================================================================================================


Orz

顺便说一组数据比较丧心病狂

7

5 7 2 4 1 6 3



下面贴本人的拙计代码。。。

顺便庆祝VIJOS AC 100  顺便求NOIP  RP++

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;int m,a,b,c,n;struct self{int x,y;}s[1011*1011*2];int first[1011*1011*2],nxt[1011*1011*2];int g[1011],f[1011][1011];int col[1011];stack
         
          s1,s2;int q[2011],top,now;void pop1(){
          
while(!s1.empty()&&now==s1.top())
{
s1.pop();
top++;
q[top]=2;
now++;
}}void pop2(){
while(!s2.empty()&&now==s2.top())
{
s2.pop();
top++;
q[top]=4;
now++;
}}bool print(){
int a,b;
now=1;
for(a=1;a<=m;a++)
{
if(col[a]==0)
{
pop1();
s1.push(g[a]);
top++;
q[top]=1;
pop1();
}
else
{
pop2();
s2.push(g[a]);
top++;
q[top]=3;
pop2();
}
}
while(top<2*m)
{
pop1();
pop2();
}
for(a=1;a <<(char)(q[a]-1+'a')<<" ";
cout<<(char)(q[top]-1+'a')<<'\n';}
bool dfs(int i,int c){
if(col[i]!=-1)
{
if(col[i]==c)return false;
return true;
}
col[i]=1-c;
for(int e=first[i];e!=-1;e=nxt[e])
if(!dfs(s[e].y,1-c))return false;
return true;}
void makeside(int x,int y){
n++;
s[n].x=x;
s[n].y=y;
nxt[n]=first[x];
first[x]=n;}int main(){
scanf("%d",&m);
memset(first,-1,sizeof(first));
memset(nxt,-1,sizeof(nxt));
memset(col,-1,sizeof(col));
for(a=1;a<=m;a++)scanf("%d",&g[a]);
for(a=1;a<=m;a++)
{
f[a][a]=g[a];
for(b=a+1;b<=m;b++)
f[a][b]=min(f[a][b-1],g[b]);
}
for(a=1;a<=m;a++)
for(b=a+1;b
if(g[b]>g[a]&&f[b+1][m]
{
makeside(a,b);
makeside(b,a);
}
for(a=1;a<=m;a++)
if(col[a]==-1)
if(!dfs(a,1))
{
cout<<0<
return 0;
}
print();
return 0;}


转载地址:https://blog.csdn.net/li412302070/article/details/14111971 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:VIJOS 1119 Car的旅行路线
下一篇:VIJOS 1754 最优贸易

发表评论

最新留言

很好
[***.191.171.16]2022年08月19日 12时41分02秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章