NOIP2008(twostack)題解這道題大概可以歸結為如下題意:1(q1),2(q2)1(s1)2(s2).最初的時候,q2,s1s2q1n(n<=1000)1~naq1s1bs1q1q2cq1s2d操作,將s2的棧頂元素彈出并加入q1q2的隊列尾.q21,2,3,…,n.可以,求出字典序最小的一個操作序列.這道題的錯誤做法很多,錯誤做法卻能得滿分的也很多,這里就不多說了.直接切入正題,就是即將介紹的這個基于二分圖的算法.注意到并沒有說基于二分圖匹配,因為這個算法和二分圖匹配無關.這個算法只是用到了給一個圖著色成二分圖.第一步需要解決的問題是,判斷是否有解.q1[i]q1[j]pk,i<j<kq1[k]<q1[i]<q1[j].p,結論很顯然,使用反證法可證.假設這兩個數壓入了同一個棧,那么在壓入q1[k]的時候棧內情況如下:…q1[i]…q1[j]…q1[k]q1[i]q1[j]q1[kq21,2,3,…,n而之后,無論其它的數字在什么時候被彈出,q1[jq1[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[kr,j<k<rq1[r]<q1[j]<q1[k]r,q1[k]q1[j]沒有影響).第二種情況下,我們可以發現這其實就是一個降序序列,所以所有數字都可以壓入同一個棧.這樣,原命題的逆否命題得證,所以原命題得證.pq1[i]q1[j]不能壓入同一個棧的充要條件也得證.這樣,我們對所有的數對(i,j)1<=i<j<=n,i<j<kijp1[j]不能壓入同一個棧.此時想到了什么?那就是二分圖~二分圖的兩部分看作兩個棧,因為二分圖的同一部分內不會出現任何連邊,也就相當于不能壓入同一個棧的所有結點都分到了兩個棧中.O(n)以得知是否有解.此時,檢查有解的問題已經解決.接下來的問題是,如何找到字典序最小的解.121s1,為2s2.s1.又發現二分圖的不同連通分量之間的染色是互不影響的,所以可以每次選取一個未染色的編號最小的結點,將它染色為1DFS染色為止.這樣,我們就得到了每個結點應該壓入哪個棧中.接下來要做的,只不過是模擬之后輸出序列啦~還有一點小問題,就是如果對于數對(i,j),kO(n^3).解決方法就是,首先預處理出數組b,b[i]表示從p1[i]到p1[n](i,j)b[j+1p1[i]p1[i]p1[j]就可以了.附代碼(除去注釋不到100行),帶注釋.代碼中的a數組對應文中的隊列p1.已經過掉所有標準數據,以及5724163這組讓很多貪心程序掛掉的數據~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染色,檢查圖是否是二分圖的經典算法23{24 inttemp=head[i];2526 while(temp//鄰接表,檢查每一條邊27 {282930色

if(!color[adj[temp]])//如果與當前結點的結點還未染31 {3233

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

//如果兩個相鄰結點染色相同,說明此圖不是二分圖,返回無next[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數組57 n+]=58 for(inti=n;i>=1;--i)b[i]=min(b[i+1],a[i]);59//"min"inSTL6061//枚舉數對(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//每次找當前未染色的編號最, , 798081 if(color[i])//當前位置尚未被染色82 {83 ]=1;84if(dfs(i//染色時出現矛盾,此時圖不是一個二分圖,即無法分配到兩個棧中87 {888990break;91}92}938990break;91}92}9394if(!result//無解printf("0");9798 else//有解99 {100101102103

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

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