NOIP2008第四題雙棧排序twostack題解

1、NOIP 2008第四題雙棧排序(twostack)題解這道題大概可以歸結(jié)為如下題意：有兩個(gè)隊(duì)列和兩個(gè)棧，分別命名為隊(duì)列1(q1),隊(duì)列2(q2),棧1(s1)和棧2(s2). 最初的時(shí)候,q2,s1和s2都為空，而q1中有n個(gè)數(shù)(n<=1000),為1時(shí)勺某個(gè)排列. 現(xiàn)在支持如下四種操作：a操作，將q1的首元素提取出并加入s1的棧頂.b操作，將s1的棧頂元素彈出并加入q1q2的隊(duì)列尾.c操作，將q1的首元素提取出并加入s2的棧頂.d操作，將s2的棧頂元素彈出并加入q1q2的隊(duì)列尾.請判斷,是否可以經(jīng)過一系列操作之后，使得q2中依次存儲(chǔ)著1,2,3,n.如果 可以,求出字典序最小的一個(gè)操

2、作序列.這道題的錯(cuò)誤做法很多，錯(cuò)誤做法卻能得滿分的也很多，這里就不多說了 .直接切 入正題,就是即將介紹的這個(gè)基丁二分圖的算法.注意到并沒有說基丁二分圖匹配，因?yàn)檫@個(gè)算法和二分圖匹配無關(guān).這個(gè)算法只 是用到了給一個(gè)圖著色成二分圖.第一步需要解決的問題是，判斷是否有解.考慮對丁任意兩個(gè)數(shù)q1i和q1j來說，它們不能壓入同一個(gè)棧中的充要條件 是什么(注意沒有必要使它們同時(shí)存在丁同一個(gè)棧中，只是壓入了同一個(gè)棧).實(shí) 際上，這個(gè)條件p是:存在一個(gè)k,使得i<j<k且q1k<q1i<q1j.首先證明充分性，即如果滿足條件p,那么這兩個(gè)數(shù)一定不能壓入同一個(gè)棧.這個(gè) 結(jié)論很顯然，使用

3、反證法可證.假設(shè)這兩個(gè)數(shù)壓入了同一個(gè)棧，那么在壓入q1k的時(shí)候棧內(nèi)情況如下: q1i q1j 因?yàn)閝1k比q1i和q1j都小，所以很顯然,當(dāng)q1k沒有被彈出的時(shí)候,另外 兩個(gè)數(shù)也都不能被彈出(否則q2中的數(shù)字順序就不是1,2,3,n 了).而之后，無論其它的數(shù)字在什么時(shí)候被彈出，q1j總是會(huì)在q1i之前彈出.而 q1j>q1i,這顯然是不正確的.接下來證明必要性.也就是,如果兩個(gè)數(shù)不可以壓入同一個(gè)棧，那么它們一定滿足 條件p.這里我們來證明它的逆否命題,也就是”如果不滿足條件p,那么這兩個(gè)數(shù) 一定可以壓入同一個(gè)棧."不滿足條件p有兩種情況：一種是對丁任意i<j<k且

4、q1i<q1j,q1k>q1i;另一種是對丁任意i<j,q1i>q1j.第一種情況下,很顯然，在q1k被壓入棧的時(shí)候,q1i已經(jīng)被彈出棧.那么,q1k不會(huì)對q1j產(chǎn)生任何影響(這里可能有點(diǎn)亂，因?yàn)榭雌饋?，?dāng) q1j<q1k的時(shí)候，是會(huì)有影響的，但實(shí)際上，這還需要另一個(gè)數(shù)r,滿足j<k<r 且q1r<q1j<q1k,也就是證明充分性的時(shí)候所說的情況而事實(shí)上我們現(xiàn)在并不考慮這個(gè)r,所以說q1k對q1j沒有影響).第二種情況下,我們可以發(fā)現(xiàn)這其實(shí)就是一個(gè)降序序列,所以所有數(shù)字都可以壓入同一個(gè)棧.這樣，原命題的逆否命題得證，所以原命題得證.此時(shí)，條

5、件p為q1i和q1j不能壓入同一個(gè)棧的充要條件也得證.這樣，我們對所有的數(shù)對（i,j）滿足1<=i<j<=n,檢查是否存在i<j<k滿足 p1k<p1i<p1j.如果存在，那么在點(diǎn)i和點(diǎn)j之間連一條無向邊，表示p1i和p1j不能壓入同一個(gè)棧.此時(shí)想到了什么？那就是二分圖二分圖的兩部分看作兩個(gè)棧，因?yàn)槎謭D的同一部分內(nèi)不會(huì)出現(xiàn)任何連邊，也就 相當(dāng)于不能壓入同一個(gè)棧的所有結(jié)點(diǎn)都分到了兩個(gè)棧中.此時(shí)我們只考慮檢查是否有解，所以只要O（n）檢查出這個(gè)圖是不是二分圖，就可 以得知是否有解.此時(shí)，檢查有解的問題已經(jīng)解決.接下來的問題是，如何找到字典序最小的解.實(shí)際

6、上，可以發(fā)現(xiàn)，如果把二分圖染成1和2兩種顏色，那么結(jié)點(diǎn)染色為1對應(yīng)當(dāng) 前結(jié)點(diǎn)被壓入s1,為2對應(yīng)被壓入s2.為了字典序盡量小，我們希望讓編號(hào)小的結(jié) 點(diǎn)優(yōu)先壓入s1.乂發(fā)現(xiàn)二分圖的不同連通分量之間的染色是互不影響的，所以可以每次選取一個(gè)未染色的編號(hào)最小的結(jié)點(diǎn)，將它染色為1并從它開始DF躲色，直到所有結(jié)點(diǎn)都被 染色為止.這樣，我們就得到了每個(gè)結(jié)點(diǎn)應(yīng)該壓入哪個(gè)棧中.接下來要做的，只不 過是模擬之后輸出序列啦還有一點(diǎn)小問題，就是如果對于數(shù)對（i，j），都去枚舉檢查是否存在k使得p1k<p1i<p1j的話，那么復(fù)雜度就升到了 O"3）.解決方法就是，首先預(yù)處理出數(shù)組b，bi表示從p

7、1i到p1n中的最小值.接下來，只需要枚舉所有數(shù)對 （i，j）， 檢查bj+1是否小于p1i且p1i是否小于p1j就可以了.附代碼（除去注釋不到100行），帶注釋.代碼中的a數(shù)組對應(yīng)文中的隊(duì)列p1. 已經(jīng)過掉所有標(biāo)準(zhǔn)數(shù)據(jù)，以及57 2 4 1 63這組讓很多貪心程序掛掉的數(shù)據(jù)1 #include <iostream>23 using namespace std;410000000005 const int nn = 1002，mm = nn * 2, inf6 int n, tot, now;7 int a nn , b nn , head nn , color nn;8 int

8、adj mnj , next mm ;9 int stack 3 nn;10 bool result;111213void addEdge (int x,int y ) / 加邊14 (15 + tot;1718192021222324252627282930313233343536373839404142434445464748495051525354555657585916adjtot = y;next tot = head x;head x = tot;bool dfs (int i ) /DFS染色，檢查圖是否是二分圖的經(jīng)典算法int temp = head i ;while (tem

9、p ) /鄰接表，檢查每一條邊if ( ! color adj temp )/如果與當(dāng)前結(jié)點(diǎn)的結(jié)點(diǎn)還未染色color adj temp = 3 - color i ; / 進(jìn)行染色dfs ( adj temp ) ; /DFS if (color adj temp = color i ) return false ;/如果兩個(gè)相鄰結(jié)點(diǎn)染色相同，說明此圖不是二分圖，返回?zé)o 解temp = next temp ;return true ;int main () freopen ("twostack.in",freopen ("twostack.out",&q

10、uot;r""w", stdin ) ;, stdout ) ;/輸入scanf ("%d" , &n);for (int i = 1; i <= n;+i ) scanf ("%d" , &a i );/預(yù)處理b數(shù)組b n + 1 = inf;for (int i = n; i >= 1;-i)b i = min ( bi + 1 , ai )/"min" in STL/枚舉數(shù)對(i,j) 并加邊tot = 0;for (int i = 1; i <= n; + i )

11、for (int j = i + 1; j <= n; + j )if (bj + 1 < a i && ai < a j ) addEdge(i, j);addEdge(j, i);/DFS染色memset (color, 0, sizeof (color );result = true ;for (int i = 1; i <= n; + i ) /每次找當(dāng)前未染色的編號(hào)最小的結(jié)點(diǎn)，并染顏色1if ( ! color i ) /當(dāng)前位置尚未被染色color i = 1;if ( ! dfs (i ) /染色時(shí)出現(xiàn)矛盾，此時(shí)圖不是一個(gè)二分圖 即無法分配

12、到兩個(gè)棧中result= false ; / 記錄無解break ;if (! result ) / 無解printf ("0");else /有解/模擬求解now = 1;60616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103for (int i = 1; i <= n; + i )104105106107/將當(dāng)前數(shù)字壓入對應(yīng)的棧if (colorprintfi = 1) ("a ");elsestackstackprintf ("c ");color i 0 +;color i stack color i 0= a i ;/this will work even if stack10 = 0/循環(huán)檢查，如果可以的話就從棧頂彈出元素whil