noip2008 双栈排序 求解 pascal
http://zhidao.baidu.com/question/126153043.html?fr=qrl&cid=866&index=1
不是早就有人问过了吗
单栈排序
Tom最近在研究一个有趣的排序问题:有一个1~n的输入序列和1个栈S，Tom希望借助以下2种操作实现将输入序列升序排序。
操作a：如果输入序列不为空，将第一个元素压入栈S1
操作b：如果栈S1不为空，将S1栈顶元素弹出至输出序列
如果一个1-n的排列P可以通过一系列操作使得输出序列为1，2，…，(n-1)，n，Tom就称P是一个“可单栈排序排列”。
【输入】第一行是一个整数n。第二行有n个用空格隔开的正整数，构成一个1~n的排列。
【输出】输出文件共一行，如果输入的排列不是“可单栈排序排列”，输出数字0；否则输出字典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。
------------------------------
定理：考虑对于任意两个数q[i]和q[j],它们不能压入同一个栈中的充要条件: 存在一个k,使得i<j<k且q[k]<q[i]<q[j]。
充分性证明：即如果满足上述条件,那么q[i]和q[j]一定不能压入同一个栈：
反证法:假设这两个数压入了同一个栈,那么在压入q[k]的时候栈内情况如下:
+----+
|q[j] |
+----+
|... |
+----+
|q[i] |
+----+
因为q[k]比q[i]和q[j]都小,所以很显然,当q[k]没有被弹出的时候,另两个数也都不能被弹出(否则输出序列的数字顺序就不是1,2,3,…,n了)。而之后,无论其它的数字在什么时候被弹出,q[j]总是会在q[i]之前弹出，而q[j]>q[i],这显然是不正确的.
必要性证明：如果两个数不可以压入同一个栈,那么它们一定满足上述条件。
证明逆否命题：也就是"如果不满足上述条件,那么这两个数一定可以压入同一个栈." 不满足上述条件有两种情况:
情况1：对于任意iq[i];
情况2：对于任意iq[j].
第一种情况：在q[k]被压入栈的时候,q[i]已经被弹出栈。那么,q[k]不会对q[j]产生任何影响(这里可能有点乱,因为看起来,q[j]<q[k]的时候是会有影响的,但实际上,这还需要另一个数r,满足j<k<r且 q[r]<q[j]<q[k],也就是证明充分性的时候所说的情况…而事实上我们现在并不考虑这个r,所以说q[k]对q[j]没有影响)。 第二种情况：可以发现这其实就是一个降序序列,所以所有数字都可以压入同一个栈. 这样,原命题的逆否命题得证,所以原命题得证。
由此得出有解的判断方法：对所有的数对(i,j)满足1≤i<j≤n,检查是否存在i<j<k满足q[k]<q[i]。
var
n,top,i,j,k:longint;{序列长度为n，栈指针为top}
ans:string;{操作序列}
st:array [1..1000000] of longint;{栈}
begin
read(n);{读序列长度}
top:=0;j:=1;ans:='';{栈和输出序列空，从1开始输出}
for i:=1 to n do{依次处理每个数字}
begin
read(k);ans:=ans+'a ';inc(top);st[top]:=k;{读当前数字，进行a操作，该数字入栈}
while st[top]=j do {若栈顶满足递增要求，则出栈（进行b操作），下一个输出数字应+1，这一过程反复进行，直至不满足条件为止}
begin dec(top);inc(j);ans:=ans+'b 'end end;
if j<=n {若未输出1¨n，则失败退出；否则输出操作序列}
then writeln(0)
else writeln(copy(ans,1,length(ans)-1))
end.
================================================================
双栈排序
【问题描述】Tom最近在研究一个有趣的排序问题。如图所示，通过2个栈S1和S2，Tom希望借助以下4种操作实现将输入序列升序排序。
操作a：如果输入序列不为空，将第一个元素压入栈S1
操作b：如果栈S1不为空，将S1栈顶元素弹出至输出序列
操作c：如果输入序列不为空，将第一个元素压入栈S2
操作d：如果栈S2不为空，将S2栈顶元素弹出至输出序列
+--------------------
s1 |
+--------------------
+--------------------
s2 |
+--------------------
如果一个1~n的排列P可以通过一系列操作使得输出序列为1，2，…，(n-1)，n，Tom就称P是一个“可双栈排序排列”。
例如(1,3,2,4)就是一个“可双栈排序序列”，而(2,3,4,1)不是。下图描述了一个将(1,3,2,4)排序的操作序列：
(这个图网上有，你自己找找吧）
当然，这样的操作序列有可能有几个，对于上例(1,3,2,4)，是另外一个可行的操作序列。Tom希望知道其中字典序最小的操作序列是什么。
【输入】输入文件twostack.in的第一行是一个整数n。第二行有n个用空格隔开的正整数，构成一个1~n的排列。
【输出】输出文件twostack.out共一行，如果输入的排列不是“可双栈排序排列”，输出数字0；否则输出字典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。
========================================
简述题意
有两个队列和两个栈,分别命名为队列1(q1),队列2(q2),栈1(s1)和栈2(s2)。最初的时候,q2,s1和s2都为空,而q1中有n个数(n≤1000),为1~n的某个排列. 现在支持如下四种操作: a操作,将 q1的首元素提取出并加入s1的栈顶； b操作,将s1的栈顶元素弹出并加入q2的队列尾；
c操作,将 q1的首元素提取出并加入s2的栈顶； d操作,将s2的栈顶元素弹出并加入q2的队列尾； 请判断,是否可以经过一系列操作之后,使得q2中依次存储着1,2,3,…,n.如果可以,求出字典序最小的一个操作序列.
1、判断是否有解和任意两个数能否压入同一个栈
⑴、对任意两个数q[i]和q[j],若存在一个k,使得i<j<k且q[k]<q[i]<q[j]，则这两个数分别入s1栈和s2栈
⑵、将s1栈和s2栈中的数字组合成两个顶点子集，同一顶点子集内不会出现任何连边,即不能压入同一个栈的所有数字被分到了两个栈中。任两个不在同一栈的数字间连边。此时我们只考虑检查是否有解,所以只要化O(n)时间检查这个图是不是二分图,就可以得知是否有解了。
======================================================
二分图及二分图的匹配
二分图是一种特殊类型的图：图中的顶点集被划分成X与Y两个子集,图中每条边的两个端点一定是一个属于X而另一个属于Y。二分图的匹配是求边的一个子集，该子集中的任意两条边都没有公共的端点。
======================================================
找字典序最小的解
1、确定每个数字入哪个栈，即构造二分图
把二分图染成1和2两种颜色,染色为1的结点被压入s1栈, 染色为2结点被压入s2栈。为了字典序尽量小,我们希望让编号小的结点优先压入s1栈。 由于二分图的不同连通分量之间的染色是互不影响的,所以可以每次选取一个未染色的编号最小的结点,将它染色为1，并从它开始DFS染色,直到所有结点都被染色为止。这样,我们就得到了每个结点应该压入哪个栈中。
2、从数字1开始，按照目标序列的递增顺序构造操作序列
先处理入栈：按照搜索递增顺序每个顶点：若顶点i的颜色为1，则进行a操作，q1[i]入s1栈；若顶点i的颜色为2，则进行c操作，q1[i]入s2栈。
后处理出栈：若s1栈的栈顶元素为目标序列的当前数字k，则进行b操作，数字k出s1栈；若s2栈的栈顶元素为目标序列的当前数字k，则进行d操作，数字k出s2栈。
然后k+1,继续模拟，直至k为n为止。
==========================================================
数据结构
var
a,b,head,next,point,color:array[0..2001]of longint;{初始序列为a（对应q1），后缀的最小值序列为b，其中b[i]=min{a[k]}(i<=k<=n)；邻接表的表首顶点为head，后继指针为next，顶点序列为point，顶点的涂色序列为color}
s:array[1..2,0..1000]of longint;{s[1]栈，栈首指针为s[1,0];s[2]栈, 栈首指针为s[2,0]}
n,p,i,j,last:longint;{序列长度为n，当前应取数字为last}
procedure badend;{输出失败信息}
begin
writeln(0);close(output);halt;
end;
procedure addedge(a,b:longint);{（a,b）进入邻接表}
var t:longint;
begin
inc(p);point[p]:=b;{增加顶点b}
if head[a]=0 {（a,b）进入邻接表}
then head[a]:=p
else begin
t:=head[a];
while next[t]0 do t:=next[t];
next[t]:=p;
end;
end;
procedure dfs(now:longint);
var t:longint;
begin
t:=head[now];{搜索与顶点now相邻的所有顶点}
while t0 do
begin
if color[point[t]]=0{若顶点now相邻的顶点point[t]未涂色，则该顶点涂互补色，沿该顶点递归下去}
then begin
color[point[t]]:=3-color[now];dfs(point[t]);
end;
if color[point[t]]=color[now] then badend;{若顶点now与相邻顶点point[t]涂相同色，则失败退出}
t:=next[t];{访问与顶点now相邻的下一个顶点}
end;
end;
begin
assign(input,'twostack.in');reset(input);{输入文件读准备}
assign(output,'twostack.out');rewrite(output);{输出文件写准备}
fillchar(s,sizeof(s),0);fillchar(a,sizeof(a),0);{两栈空}
readln(n);{读入排列}
for i:=1 to n do read(a[i]);
b[n+1]:=maxlongint;p:=0;
for i:=n downto 1 do{计算b[i]= }
begin
b[i]:=b[i+1];
if a[i]<b[i] then b[i]:=a[i];
end;
for i:=1 to n do
for j:=i+1 to n do
if (b[j+1]<a[i])and(a[i]<a[j]) {若a[i]和a[j]不能不能压入同一个栈，则(i,j)和(j,i)进入邻接表}
then begin addedge(i,j);addedge(j,i);end;
for i:=1 to n do{所有未涂色的顶点涂颜色1，递归}
if color[i]=0 then begin color[i]:=1;dfs(i);end;
last:=1;{目标序列初始化}
for i:=1 to n do{模拟输出序列}
begin
if color[i]=1 {a[i]入s[1]或s[2]栈}
then write('a ')
else write('c ');
inc(s[color[i],0]);s[color[i],s[color[i],0]]:=a[i];
while (s[1,s[1,0]]=last)or(s[2,s[2,0]]=last) do
begin{将s[1]或s[2]栈顶的数字last取出}
if s[1,s[1,0]]=last then begin write('b ');dec(s[1,0]);end;{将s[1]栈顶的last取出}
if s[2,s[2,0]]=last then begin write('d ');dec(s[2,0]);end;{将s[2]栈顶的last取出}
inc(last);{按递增要求取下一个数字}
end;
end;
close(input);close(output);{关闭输入输出文件}
end.
考虑对于任意两个数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)检查出这个图是不是二分图,就可以得知是否有解.
然后处理最小字典序问题。实际上对二分图染色后对应的操作显然编号小的优先使用a操作，可以使得字典序尽量小。
这里要提二分图的一个性质：二分图中不同的连通分量染色是互不影响的。所以为了满足最小字典序的问题，可以选取编号最小的未染色结点染成1并对它所在连通分量染色。染完之后，模拟输出序列就可以了。
(以下代码部分仅供学习之用)
var
n,i,j,st1,st2,next_num,min,t:longint;
a,color,s1,s2:array[0..1500] of longint;
map:array[1..1500,1..1500] of boolean;
vis:array[1..1500] of boolean;
ans:array[1..3000] of char;
procedure print;
begin
writeln(0);
halt;
end;
procedure dfs(x,nowcolor:longint);
var
i:longint;
begin
vis[x]:=true;
color[x]:=nowcolor;
for i:=1 to n do
if map[x,i] then
begin
if not vis[i] then
dfs(i,3-nowcolor)
else
if color[i]<>3-nowcolor then print;
end;
end;
begin
readln(n);
for i:=1 to n do
read(a[i]);
readln;
min:=maxlongint;
for i:=n downto 1 do
begin
for j:=1 to i-1 do
if (a[j]<a[i]) and (min<a[j]) then
begin
map[a[i],a[j]]:=true;
map[a[j],a[i]]:=true;
end;
if a[i]<min then min:=a[i];
end;
fillchar(vis,sizeof(vis),0);
for i:=1 to n do
if not vis[a[i]] then dfs(a[i],1);
i:=1;
next_num:=1;
t:=a[i];
st1:=0;
st2:=0;
j:=0;
while (i<=n) or (next_num<=n) do
begin
if (i<=n) and (color[t]=1) and ((st1=0) or (t<s1[st1])) then
begin
inc(j);
ans[j]:='a';
inc(st1);
s1[st1]:=t;
inc(i);
if i<=n then t:=a[i] else t:=0;
continue;
end;
if (st1>0) and (s1[st1]=next_num) then
begin
inc(j);
ans[j]:='b';
dec(st1);
inc(next_num);
continue;
end;
if (i<=n) and (color[t]=2) and ((st2=0) or (t<s2[st2])) then
begin
inc(j);
ans[j]:='c';
inc(st2);
s2[st2]:=t;
inc(i);
if i<=n then t:=a[i] else t:=0;
continue;
end;
if (st2>0) and (s2[st2]=next_num) then
begin
inc(j);
ans[j]:='d';
dec(st2);
inc(next_num);
continue;
end;
end;
for i:=1 to j-1 do
write(ans[i],' ');
writeln(ans[j]);
end.
这道题大概可以归结为如下题意:
有两个队列和两个栈,分别命名为队列1(q1),队列2(q2),栈1(s1)和栈2(s2).最初的时候,q2,s1和s2都为空,而q1中有n个数(n<=1000),为1~n的某个排列.
现在支持如下四种操作:
a操作,将 q1的首元素提取出并加入s1的栈顶.
b操作,将s1的栈顶元素弹出并加入q1的队列尾.
c操作,将 q1的首元素提取出并加入s2的栈顶.
d操作,将s2的栈顶元素弹出并加入q1的队列尾.
请判断,是否可以经过一系列操作之后,使得q2中依次存储着1,2,3,…,n.如果可以,求出字典序最小的一个操作序列.
这道题的错误做法很多,错误做法却能得满分的也很多,这里就不多说了.直接切入正题,就是即将介绍的这个基于二分图的算法.
注意到并没有说基于二分图匹配,因为这个算法和二分图匹配无关.这个算法只是用到了给一个图着色成二分图.
第一步需要解决的问题是,判断是否有解.
考虑对于任意两个数q1[i]和q1[j]来说,它们不能压入同一个栈中的充要条件是什么(注意没有必要使它们同时存在于同一个栈中,只是压入了同一个栈).实际上,这个条件p是:存在一个k,使得i接下来证明必要性.也就是,如果两个数不可以压入同一个栈,那么它们一定满足条件p.这里我们来证明它的逆否命题,也就是"如果不满足条件p,那么这两个数一定可以压入同一个栈."
不满足条件p有两种情况:一种是对于任意i第一种情况下,很显然,在q1[k]被压入栈的时候,q1[i]已经被弹出栈.那么,q1[k]不会对q1[j]产生任何影响(这里可能有点乱,因为看起来,当q1[j]第二种情况下,我们可以发现这其实就是一个降序序列,所以所有数字都可以压入同一个栈.
这样,原命题的逆否命题得证,所以原命题得证.
此时,条件p为q1[i]和q1[j]不能压入同一个栈的充要条件也得证.
这样,我们对所有的数对(i,j)满足1<=i二分图的两部分看作两个栈,因为二分图的同一部分内不会出现任何连边,也就相当于不能压入同一个栈的所有结点都分到了两个栈中.
此时我们只考虑检查是否有解,所以只要O(n)检查出这个图是不是二分图,就可以得知是否有解.
此时,检查有解的问题已经解决.接下来的问题是,如何找到字典序最小的解.
实际上,可以发现,如果把二分图染成1和2两种颜色,那么结点染色为1对应当前结点被压入s1,为2对应被压入s2.为了字典序尽量小,我们希望让编号小的结点优先压入s1.
又发现二分图的不同连通分量之间的染色是互不影响的,所以可以每次选取一个未染色的编号最小的结点,将它染色为1并从它开始DFS染色,直到所有结点都被染色为止.这样,我们就得到了每个结点应该压入哪个栈中.接下来要做的,只不过是模拟之后输出序列啦~
还有一点小问题,就是如果对于数对(i,j),都去枚举检查是否存在k使得p1[k]附代码(除去注释不到100行),带注释.代码中的a数组对应文中的队列p1.
已经过掉所有标准数据,以及5 7 2 4 1 6 3这组让很多贪心程序挂掉的数据~
薄斧抒彤： car牛是这么讲的: 考虑对于任意两个数q1[i]和q1[j]来说,它们不能压入同一个栈中的充要条件是什么(注意没有必要使它们同时存在于同一个栈中,只是压入了同一个栈).实际上,这个条件p是:存在一个k,使得i<j<k且q1[k]<q1[i]<q1[j]....
元谋县17339136334： 急求NOIP2008(提高组)复赛测试数据 ？
薄斧抒彤： 全国信息学奥林匹克联赛(NOIP2008)复赛 提高组 一、题目概览 中文题目名称 笨小猴 火柴棒等式 传纸条 双栈排序 英文题目名称 word matches message twostack 可执...
元谋县17339136334： 求这道题的C++解法？
薄斧抒彤： #include<iostream> #include<math.h> using namespace std; int su(int x) { int i; if(x<2) return 0; for(i=2;i<=sqrt(x);i++) if(x%i==0) return 0; return 1; } int main() { FILE *fp; char s[100]={0}; int maxn,minn,sub; int i,c[26]={0};fp=fopen(＂WORD.IN＂,＂r＂...
元谋县17339136334： 求noip2010第三题关押罪犯 并差集解法 - ？
薄斧抒彤： 首先,将怨恨值由大到小排序,对于每个犯人建立为一个独立的集合,对立集合设为空集.由大到小依次按如下方法合并怨恨值所表示的两点:如果属于同一集合则输出这个值,否则依次与另一个点的对立集合合并,注意空集情况! 复杂度O(m*log(m)) 根本不用二分答案!!!但是你如果就是喜欢二分答案我建议你二分答案+BFS二分图判定.复杂度O(m*log(10^9))
元谋县17339136334： 笨小猴 - NOIp2008 提高组 - ？
薄斧抒彤： program word; var a,b,c,d,i,j,x,y,m:integer; st,s:string; F:boolean; begin readln(st); s:=st; c:=length(st); a:=0; b:=c; d:=c; for i:=1 to c do begin y:=0; if s[i]<>' ' then for j:=1 to c do if st[i]=s[j] then begin y:=y+1; s[j]:=' '; end; if y>a then a:=y; if (y0) then b:=y; ...
元谋县17339136334： noip2008 问题求解第二题 “21本书……”？
薄斧抒彤： 用插空法做简单. 21本书里选择4本书,然后做上记号,比如涂成红的. 它等价于这样的动作.有17本不红的书和4本已经涂成红色的书,把4本红的放在上面选择的位置,其余17本放在剩下的位置. 这样一种选择法对应一种排列法,选择就转换成了排列. 于是题目变成这样:17本白书,4本红书,排成一行.要求红书互不相邻,共有多少种排法.所以答案就是C(18,4)=3060种
元谋县17339136334： 排座位C++程序 Noip 2008 - ？
薄斧抒彤： #include using namespace std;ifstream fin(＂seat.in＂);ofstream fout(＂seat.out＂);int main(int argc, char *argv[]){int y[1010] , x[1010] , w[1010];int m , n , k , l , d;int x1 , y1 , x2 , y2;int i , j;fin >> m >> n >> k >> l >> d;for (i = 1; i y[i]=0;for ...
元谋县17339136334： 2008年noip普及组复赛题解 - ？
薄斧抒彤： 第一题:很水的送分题,可能对于刚刚接触OI的选手来说,处理字符串是一个难点,不妨用整体读入,用st-'0'[fly]的方法即可求出该位数字(C++写法,PASCAL有些忘记见谅,希望有人能够补充上).最后注意'X'即可获得满分 第二题:贪心....
元谋县17339136334： 求2008年NOIP初赛答案？
薄斧抒彤： 参考答案 一 1.C 2.A 3.B 4.C 5.B 6.D 7.D 8.E 9.C 10.C 二 11.ABD 12.AC 13.BC 14.BD? 15.ABC 16.ABD 17.BCD 18.ABC 19.ACD 20.ABC 三 1.7 2.3060 四 1. 23 2. 1,3,2 3. 132/213/231/312/321/ 4. defghijxyzabc/hfizxjaybcccc 五 (Pascal) 1. ...
元谋县17339136334： 求NOIP 2008 程序第二题procedure foo(a,b,c:integer);每个步骤详解,弄不懂递归 - ？
薄斧抒彤： foo(3,1,2)--->>> 3>1 ---->>foo(2,3,1)2>3 ----->> writeln(2,3,1); 这里用到的递归是很基础的,这个一定要掌握!!!不会的话像老师请教一下 补充一下,递归就是程序调用自身,举个例子:(求阶乘,如5的阶乘=5*4*3*2*1,n的阶乘=n*(n-1)的阶乘) function jiecheng(a:longint):longint; begin if a=1 then jiecheng:=1 else jiecheng:=a*jiecheng(a-1); end; 这就是一个经典的递归
