noip歷年試題及解題報(bào)告t2006年

1、NOIP2006 提高組解題作者:程軍康編輯日期:2009- 11- 6 12:03:00點(diǎn)擊數(shù):1198一道很經(jīng)典的 dp 題目，其實(shí)質(zhì)就是“石子合并問(wèn)題”的變形，有談不上什么變形，倒不如說(shuō)更好一點(diǎn)。的原因多為沒(méi)弄懂題目的意思就下手做了，把題目看簡(jiǎn)單了。說(shuō)：給你一項(xiàng)鏈，項(xiàng)鏈上有 n 顆珠子。相鄰的兩顆珠子可以合并(兩個(gè)合并成一個(gè))。合并的同時(shí)會(huì)放出一定的能量的能量是不同的。問(wèn)：按照怎樣的次序合并才能使的能量最多？p 表示第 i 顆珠子的頭標(biāo)記，用 wei 表示第 i 顆珠子的尾標(biāo)記，合并兩顆相鄰珠子所的能量是：*weii+1或 top*topi+1*weii+1;（一個(gè)樣的）定按順序的，本題

2、所提供的樣例也是導(dǎo)致出錯(cuò)的一大原因。行一次合并的后，就歸結(jié)到了 n-1 個(gè)珠子的合并題目，必然要滿足 dp 的兩大條件：、。所以想到了動(dòng)態(tài)規(guī)劃。結(jié)構(gòu)性質(zhì)；表示第 i 顆珠子到第 j 顆珠子合并所產(chǎn)生的能量。顯然 Q1,n表示的是合并產(chǎn)生的總的能量。給定一種標(biāo)號(hào)方法。設(shè)最后一次合并在 k 處進(jìn)行，則有 Q1,nQ1,kQk+1,ntop1*weik*wein。要 Q1,n最大，必然。設(shè) Q1,k不是最大，則必然存在一 Q1,kQ1,k。那么就有 Q1,nQ1,kQk+1,ntop1*weik*weinQ1,k。這與 Q1,n的最優(yōu)性構(gòu)性質(zhì)得證。無(wú)后效性；效性是顯然的，進(jìn)行某次合并，合并前與合并后

3、狀態(tài)是相對(duì)獨(dú)立，不相關(guān)聯(lián)，互不影響的。定了下來(lái)了，關(guān)鍵是怎么實(shí)現(xiàn)了。個(gè)環(huán)，而處理是對(duì)一個(gè)串進(jìn)行的。所以要把項(xiàng)鏈從某處割斷展開(kāi)，不同處也法。產(chǎn)生的 maxQ1,n也就不同的。所以要對(duì)這些 maxQ1,n進(jìn)行打擂，取其最大的一個(gè)，即為解了。移方程是：st=maxQ1,n1=i=n(i 表示從第 i 顆珠子處展開(kāi)，順次標(biāo)號(hào)）；i,j=maxQi,k+Qk+1,j+top*weik*weij1=i=kJ=N ;中 Qi,i=01=i=n;間復(fù)雜度為 O(n3)，n 種的展開(kāi)方法對(duì)應(yīng)需要 n 次的 dp，所以時(shí)間復(fù)雜度為 O(n4)?？臻g為 O(n2)。n4)過(guò)這個(gè)題目是有點(diǎn)欠缺的，對(duì)的大的數(shù)據(jù)貌似很容

4、易超時(shí)的。想想，還是做了很不重復(fù)的工作的，不同的展開(kāi)方式化的重復(fù)的工作，那么就合并起來(lái)吧?；氐狡瘘c(diǎn)，開(kāi)始的時(shí)候?yàn)槭裁匆獙?duì)項(xiàng)鏈做 n 次的展開(kāi)呢，基于在運(yùn)算子與第 n 顆珠子的相鄰性。為了一次 dp 就實(shí)現(xiàn)所以的的珠子的相鄰性，做如下處理：a2,a3.an,a1,a2.an-1（原來(lái)的）（延伸的）a2,a3.an,an+1,an+2.am-1;這一串珠子 dp 一次即解；dp 方程為：xQi,i+n-11=i=ni,j=maxQi,k+Qk+1,j+top*weik*weij1=i=kJ=MIN(I+N-1,M)i,i=01=im then break; for k:=i to j-1 doif

5、 fi,jFI,K+Fthenfi,jend;preger; best:long;t:=0;i:=1 to n do if bestwrin(best);案普及組試卷就會(huì)發(fā)現(xiàn)，對(duì)應(yīng)的第二個(gè)題目，也是一個(gè)樣的背景，提高組只是多了個(gè)“主件附件”的的關(guān)系，如果去也就成了經(jīng)典的背包問(wèn)題了。也就是多了這么一點(diǎn)，的時(shí)候就暈了。不知道怎么做了。后來(lái)才發(fā)現(xiàn)是個(gè)很簡(jiǎn)單做出來(lái)。題，可能會(huì)得到這樣的算法：dp，對(duì)每一個(gè)物品做兩種決策，取與不取。如果取，滿足兩個(gè)條件：1.要么它是主件包里了。2.放進(jìn)去后的重要度與價(jià)格的成績(jī)的總和要比沒(méi)放進(jìn)時(shí)的大。這兩個(gè)條件的。于是呼=fi-1,j;(i 為主件 ori 的附件在包中）

6、and (fi,jFI,J-V+V*W)then fi,j:=fi,j-v+v*w;析一下復(fù)雜度，空間：dp 的階段為 n2,對(duì)與每一個(gè)階段都要該狀態(tài)下在包中的物品有哪些（因?yàn)橐_定附件段的都要 O(n)的空間，所以總的就是 O(n3)。時(shí)間，一個(gè) dp，n2 的外層循環(huán)，用量加個(gè)主附件的就為 O(n2)的復(fù)雜度。出，時(shí)間的需求為 32000*60，不成問(wèn)題?？臻g 32000*60*60，大約要 7.5M 的空間，在 64M 的要求下是完全可以的個(gè)很隱秘的條件：“每件物品都是 10 元的整數(shù)倍”，就可以把速度在提高十倍。題目，還一個(gè)很重要的條件還沒(méi)用：“每個(gè)主件可以有個(gè)，個(gè)或個(gè)附件”。這貌似不

7、起眼的一句話，卻件。想，為什么題目要對(duì)附件的個(gè)數(shù)做限制呢，明顯是在降低難度。物品（包含主件，所以的附件），稱為一個(gè)屬類，對(duì)一個(gè)屬類的物品的方法，有以下種個(gè)都不買件件附件件附件件附件附件買方法也是唯一的五種方法，也就是說(shuō)對(duì)一屬類的物品，只有上述的種方法。很自然的就會(huì)想到把物品按物品的屬類捆在一起考慮。這樣把物品的屬類作為 dp 的狀態(tài)?？梢缘玫饺缦碌?dpxfi-1,j;fi-1,j-vi,0+vi,0*wi,0;fi-1,j-vi,0-vi,1+vi,0*wi,0+vi,1*wi,1;fi-1,j-vi,0-vi,2+vi,0*wi,0+vi,2*wi,2;fi-1,j-vi,0-vi,1-v

8、i,2+vi,0*wi,0+vi,1*wi,1+vi,2*wi,2;時(shí)間復(fù)雜度為 O(n2)，空間復(fù)雜度為 O(n2)，加上利用“每件物品都是 10 元的整數(shù)倍”除以 10 的優(yōu)化，本題就很完）；put,output);cordu:eger;v:array0.2 ofp:array0.2 of end;eger;eger;eger;1.60 of node;0.60,0.3200 of long;1.60 ofinit;eger;:eger;px,qx:array1.60 ofeger;dln(n,m); k:=0; i:=1 to m do beginreadln(vx,px,qx); if

9、 qx=0then begink:=k+1; g:=k; with wk do beginu:=0;v0:=vx;p0:=px;for j:=1 to 2 do begin vj:=0; pj:=0; end;end;end;end;i:=1 to m do if qx0then beginwith wgqx do beginu:=u+1;v:=vx; p:=px; end;end;doi:=1 to k with w do beginfor wriend;j:=0 to 2 don;write(,vj,pj,);t;:eger;lchar(f,sizeof(f),0); i:=1 to k

10、dowith w do beginfor j:=1 to n do beginfi,j:=fi-1,j;if(j=v0) and (fi,j=v0+v1) and (fi,j=v0+v2) and (fi,j=v0+v1+v2) and (fi,jFI-1,J-V0-V1-V2+V0*P0+V1*P1+V2*Pthen fi,j:=fi-1,j-v0-v1-v2+v0*p0+v1*p1+v2*p2;end;end;pr;評(píng)價(jià)：題目超長(zhǎng)，超簡(jiǎn)單，失分率最高。場(chǎng)上拿到這個(gè)題目的時(shí)候，的緊張的氣氛壓抑著讀了一遍，不知所up !回來(lái)，一看，這樣的題目竟然不會(huì)，一定是氣的死去活來(lái)，我就是這樣郁悶了整整的

11、一個(gè)月的。貪心算法。：有 n 個(gè)工件要在 m 個(gè)機(jī)器上加工，每個(gè)工件都有 m 到工序，每個(gè)工序?qū)?yīng)著相應(yīng)的加工機(jī)器。一個(gè)工件的工序必時(shí)只能加工一個(gè)工件。每個(gè)工件的每個(gè)工序需要一定的加工時(shí)間。問(wèn)：加工完所有的工件需要的最少時(shí)間是多少？目中連算法都給出了，的是對(duì)題意的理解和數(shù)據(jù)結(jié)構(gòu)，但本題的規(guī)模并沒(méi)有對(duì)數(shù)據(jù)結(jié)構(gòu)做過(guò)高的要求。應(yīng)該可題目了，但不是送分題，很多人和我一樣都望而止步了。按部就班就可以了。目中給的詳盡算法：操作到某臺(tái)機(jī)器的某個(gè)空檔時(shí)（機(jī)器上最后的尚未安排操作的部分也可以看作一個(gè)空檔），可以靠前，也使問(wèn)題簡(jiǎn)單一些，約定：在保證約束條件（1）（2）的條件下，盡量靠前。并且，還約定，如果有多約束

12、條件（1）（2）的條件下，到最前面的一個(gè)空檔。”在的時(shí)候使用數(shù)組，平時(shí)可以用指針寫一寫）；put,output);eger;1.400 ofeger;1.20,0.1000 ofrray1.20,1.20 of array1.20 of init;:eger;dln(m,n);i:=1 to n*m do read(a); dln;i:=1 to n do beginfor j:=1 to m do read(wui,j); readln;end;i:=1 to n do beginfor j:=1 to m do read(tii,j); readln;end;t;,k,xtime:eger

13、;lchar(f,sizeof(f),true); lchar(time,sizeof(time),0); lchar(g,sizeof(g),0);i:=1 to n*m dobegininc(ga); j:=timea+1; xtime:=0;while xtimebeginif fwua,ga,j then inc(xtime) else xtime:=0;j:=j+1;end; timea:=j-1;for k:=j-xtime to j-1end;dofwua,ga,k:=false;pr;,best:eger;t:=0;i:=1 to m dofor j:=1000 downto

14、0 if not fi,j thenbeginif best end;n(best);dobreak;為什么第 6 個(gè)數(shù)據(jù)是 112.而提供的);是 116.?迎牛人.呵呵.(說(shuō)中的數(shù)學(xué)題嗎?前曾沸沸揚(yáng)揚(yáng)的流傳過(guò)這么一段：“今年的題目出題加上今年的 maths 庫(kù)函數(shù)登上歷史舞臺(tái)。更讓人深信不移：今年要考數(shù)學(xué)題。信啊，冤死了多少牛們數(shù)學(xué)題，到不如說(shuō)是個(gè)找規(guī)律的題目。用標(biāo)準(zhǔn)的數(shù)學(xué)方法做一下好了。本題其實(shí)就是個(gè)很簡(jiǎn)單的組合數(shù)學(xué)問(wèn)題。沒(méi)上過(guò)高三做不出也就算了，上過(guò)高三的牛。以看出，w 的值限制著首位的取值。所以要對(duì)與特殊考慮。比如樣例中的 w=7，就限制了首位只能取和。了，w 決定了數(shù)的最大的位數(shù)，

15、最少的位數(shù)要求是位。k 決定了數(shù)的位權(quán)。說(shuō)了半天也不說(shuō)不清楚，舉個(gè)例子吧：就拿樣例說(shuō)，k=3。所以位權(quán)是 2k=8，w=7，決定了數(shù)的位數(shù)最大是w最最大只能是2(w+1) mod k-1)-1。所以分兩種做：1.位數(shù)是最多位，2.位數(shù)小于最多位。最多位（最多位為）；：后面的兩位只能在之間取兩個(gè)不同的數(shù)。顯然取法的種數(shù)為 c2,6。cn,m=m!/(n!*(m-n)!)，就是組里的最只能為，所以只一種情況。于最多位。兩位只能從之間取數(shù)，為 c2,7。有兩位的情況，所以只這一種情況。例子，可以看出一般的情況：k。位數(shù)：l=w div k+1;當(dāng) w mod k=0 時(shí)，最高為最大為，結(jié)合下大值：2

16、(w+1) mod k-1)-1。是要知道的幾個(gè)基本的元素統(tǒng)計(jì)滿足的數(shù)的個(gè)數(shù)：最多：為取值 x(2=x=mhigh);位 x 都有一些 L 位滿足條件的數(shù)，這些數(shù)的個(gè)數(shù)為 cl-1,n-x-1。最多：定的 w 位數(shù)都對(duì)應(yīng)著 cw,n-1個(gè)滿足條件的數(shù)。數(shù)全部加起來(lái)就可以了。，引進(jìn)一個(gè)組合公式：n-1,m-1+cn,m-1;其中 cn,m=m!/(n!*(m-n)!用高精度，64 可以過(guò)個(gè)點(diǎn)，高精度就可以全過(guò)了。put,output);,mhigh:eger;array1.200 ofeger;1.512,1.512,1.100 ofinit;eger;dln(k,w);ready;,l,jin,s:eger;i:=1 to 512 do c1,i,1:=i; i:=2 to 512 dobeginfor j:=2 to i do beginjin:=0;for l:=1 to 100 do begins:=cj-1,i-1,l+cj,i-1,l+jin; cj,i,l:=s mod 10;jin:=s div 10; end;end;end;plus(n,m:eger);in,s:eger;:=0;i:=1 to 100 do begins:=answer+cn,m,i+jin; jin:=s div 10;answer: