NOIP 2008 第四題 雙棧排序(twostack) 題解

NOIP2008(twostack)題解這道題大概可以歸結(jié)為如下題意:1(q1),2(q2)1(s1)2(s2).最初的時(shí)候,q2,s1s2q1n(n<=1000)1~naq1s1bs1q1q2cq1s2d操作,將s2的棧頂元素彈出并加入q1q2的隊(duì)列尾.q21,2,3,…,n.可以,求出字典序最小的一個(gè)操作序列.這道題的錯(cuò)誤做法很多,錯(cuò)誤做法卻能得滿分的也很多,這里就不多說了.直接切入正題,就是即將介紹的這個(gè)基于二分圖的算法.注意到并沒有說基于二分圖匹配,因?yàn)檫@個(gè)算法和二分圖匹配無關(guān).這個(gè)算法只是用到了給一個(gè)圖著色成二分圖.第一步需要解決的問題是,判斷是否有解.q1[i]q1[j]pk,i<j<kq1[k]<q1[i]<q1[j].p,結(jié)論很顯然,使用反證法可證.假設(shè)這兩個(gè)數(shù)壓入了同一個(gè)棧,那么在壓入q1[k]的時(shí)候棧內(nèi)情況如下:…q1[i]…q1[j]…q1[k]q1[i]q1[j]q1[kq21,2,3,…,n而之后,無論其它的數(shù)字在什么時(shí)候被彈出,q1[jq1[i]q1[j]>q1[i],這顯然是不正確的.p.p,一定可以壓入同一個(gè)棧."不滿足條件p有兩種情況:一種是對于任意i<j<k且q1[i]<q1[j],q1[k]>q1[i];另一種是對于任意i<j,q1[i]>q1[j].q1[k]被壓入棧的時(shí)候,q1[i]么,q1[k]q1[j]產(chǎn)生任何影響(這里可能有點(diǎn)亂,因?yàn)榭雌饋?當(dāng)q1[j]<q1[kr,j<k<rq1[r]<q1[j]<q1[k]r,q1[k]q1[j]沒有影響).第二種情況下,我們可以發(fā)現(xiàn)這其實(shí)就是一個(gè)降序序列,所以所有數(shù)字都可以壓入同一個(gè)棧.這樣,原命題的逆否命題得證,所以原命題得證.pq1[i]q1[j]不能壓入同一個(gè)棧的充要條件也得證.這樣,我們對所有的數(shù)對(i,j)1<=i<j<=n,i<j<kijp1[j]不能壓入同一個(gè)棧.此時(shí)想到了什么?那就是二分圖~二分圖的兩部分看作兩個(gè)棧,因?yàn)槎謭D的同一部分內(nèi)不會(huì)出現(xiàn)任何連邊,也就相當(dāng)于不能壓入同一個(gè)棧的所有結(jié)點(diǎn)都分到了兩個(gè)棧中.O(n)以得知是否有解.此時(shí),檢查有解的問題已經(jīng)解決.接下來的問題是,如何找到字典序最小的解.121s1,為2s2.s1.又發(fā)現(xiàn)二分圖的不同連通分量之間的染色是互不影響的,所以可以每次選取一個(gè)未染色的編號(hào)最小的結(jié)點(diǎn),將它染色為1DFS染色為止.這樣,我們就得到了每個(gè)結(jié)點(diǎn)應(yīng)該壓入哪個(gè)棧中.接下來要做的,只不過是模擬之后輸出序列啦~還有一點(diǎn)小問題,就是如果對于數(shù)對(i,j),kO(n^3).解決方法就是,首先預(yù)處理出數(shù)組b,b[i]表示從p1[i]到p1[n](i,j)b[j+1p1[i]p1[i]p1[j]就可以了.附代碼(除去注釋不到100行),帶注釋.代碼中的a數(shù)組對應(yīng)文中的隊(duì)列p1.已經(jīng)過掉所有標(biāo)準(zhǔn)數(shù)據(jù),以及5724163這組讓很多貪心程序掛掉的數(shù)據(jù)~1#include<iostream>23usingnamespacestd;45constintnn=1002,mm=nn*2,inf=1000000000;intn,tot,now;inta[nn],b[nn],head[nn],color[nn];intadj[mm],next[mm];intstack[3][nn];boolresult;111213voidaddEdge(intxinty//加邊14{15 ++tot;[]==head[x];=tot;19}202122booldfs(inti//DFS染色,檢查圖是否是二分圖的經(jīng)典算法23{24 inttemp=head[i];2526 while(temp//鄰接表,檢查每一條邊27 {282930色

if(!color[adj[temp]])//如果與當(dāng)前結(jié)點(diǎn)的結(jié)點(diǎn)還未染31 {3233

[p3r進(jìn)行染色34 [p;35 }36 if(color[adj[temp]]==color[i])returnfalse;3738解

//如果兩個(gè)相鄰結(jié)點(diǎn)染色相同,說明此圖不是二分圖,返回?zé)onext[temp];41 }42 returntrue;43}4445intmain()46{freopen("twostack.in","r",stdin);freopen("twostack.out","w",stdout);495051 //輸入52 scanf("%d",&n);53 for(inti=1;i<=n;++i)scanf("%d",&a[i]);545556 //b數(shù)組57 n+]=58 for(inti=n;i>=1;--i)b[i]=min(b[i+1],a[i]);59//"min"inSTL6061//枚舉數(shù)對(i,j)并加邊tot=0;for(inti=1;i<=n;++i)for(intj=i+1;j<=n;++j)66 if(b[j+1]<a[i]&&a[i]<a[j])67 {j);i);70 }7172//DFS染色memset(color,0,sizeof(color));result=true;76for(inti1in//每次找當(dāng)前未染色的編號(hào)最, , 798081 if(color[i])//當(dāng)前位置尚未被染色82 {83 ]=1;84if(dfs(i//染色時(shí)出現(xiàn)矛盾,此時(shí)圖不是一個(gè)二分圖,即無法分配到兩個(gè)棧中87 {888990break;91}92}938990break;91}92}9394if(!result//無解printf("0");9798 else//有解99 {100101102103

//模擬求解now=1;for(inti=1;i<=n;++i)104105106107

{//將當(dāng)前數(shù)字壓入對應(yīng)的棧if(color[i]==1)printf("a");elseprintf("c");[i][ir]=];//thiswillworkevenifstack[1][0]=0//循環(huán)檢查,如果可以的話就從棧頂彈出元素while(stack[1][stack[1][0]]==now||stack