信息學(xué)-noip2008提高組第四題twostack

第四題以下saybi的題 s2都為空,q1n個(gè)數(shù)(n<=1000),1~n的某個(gè)排列.a操作,q1s1的棧頂b操作,s1q1q2的隊(duì)列尾c操作,q1s2的棧頂d操作,s2q1q2的隊(duì)列尾請(qǐng)判斷,是否可以經(jīng)過一系列操作之后,使得q2中依次著1,2,3,…,n.如果可以,求出字典序這道題的錯(cuò)誤做法很多,錯(cuò)誤做法卻能得滿分的也很多,這里就不多說了.直接切入正題,就是.個(gè)圖成二分圖.q1[i]q1[j]來說,它們不能壓入同一個(gè)棧中的充要條件是什么(注意沒有必要使它們同時(shí)存在于同一個(gè)棧中,只是壓入了同一個(gè)棧).實(shí)際上,p是:存在一個(gè)k,i<j<kq1[k]<q1[i]<q1[j].首先證明充分性,即如果滿足條件p,那么這兩個(gè)數(shù)一定不能壓入同一個(gè)棧.這個(gè)結(jié)論很顯然因?yàn)閝1[k]比q1[i]和q1[j]都小,所以很顯然,當(dāng)q1[k]沒有被彈出的時(shí)候,另外兩個(gè)數(shù)也都不能被彈出(q21,2,3,…,n了).而之后,無論其它的數(shù)字在什么時(shí)候被彈出,q1[j]總是會(huì)在q1[i]之前彈出.而q1[j]>q1[i],這顯接下來證明必要性.也就是,如果兩個(gè)數(shù)不可以壓入同一個(gè)棧,那么它們一定滿足條件p.這里來證明它的逆否命題,也就是"p,那么這兩個(gè)數(shù)一定可以壓入同一個(gè)棧."不滿足條件p有兩種情況:一種是對(duì)于任意i<j<k且q1[i]<q1[j],q1[k]>q1[i];另一種是對(duì)于任意第一種情況下,很顯然,q1[k]被壓入棧的時(shí)候,q1[i]已經(jīng)被彈出棧.那么,q1[k]q1[j]產(chǎn)生任何影響(這里可能有點(diǎn)亂,因?yàn)榭雌饋?當(dāng)q1[j]第二種情況下,可以發(fā)現(xiàn)這其實(shí)就是此時(shí)只考慮檢查是否有解,所以只要O(n)檢查出這個(gè)圖是不是二分圖,就可以得知是否有號(hào)最小的結(jié)點(diǎn),將它染色為1并從它開始DFS染色,直到所有結(jié)點(diǎn)都被染色為止.這樣,就還有一點(diǎn)小問題,就是如果對(duì)于數(shù)對(duì)(i,j),kp1[k]MRain:程序是寫的(懶得按照格式輸出了),已經(jīng)過了所有標(biāo)準(zhǔn)數(shù)據(jù).vara,b,head,next,point,color:array[0..2001]oflongint;s:array[1..2,0..1000]oflongint;procedurebadend;procedureaddedge(a,b:longint);vart:longint;ifhead[a]=0thenwhilenext[t]<>0doproceduredfs(now:longint);vart:longint;whilet<>0doifcolor[point[t]]=0then

ifcolor[point[t]]=color[now]thenbadend;fori:=1tonfori:=ndownto1doifa[i]<b[i]thenfori:=1tonforj:=i+1tonif(b[j+1]<a[i])and(a[i]<a[j])thenfori:=1tonifcolor[i]=0thenfori:=1tondoifcolor[i]=1thenwrite('a')write('cwhile(s[1,s[1,0]]=last)or(s[2,s[2,0]]=la