提高組復(fù)賽命題與解題報(bào)告

1、NOIP2006 提高組復(fù)賽命題與解題1能量項(xiàng)鏈(energy.pas/p)【問(wèn)題描述】在 Mars 星球上，每個(gè) Mars 人都隨身佩帶著一串能量項(xiàng)鏈。在項(xiàng)鏈上有 N 顆能量珠。能量珠是一顆有頭標(biāo)記與尾標(biāo)記的珠子，這些標(biāo)記對(duì)應(yīng)著某個(gè)正整數(shù)。并且，對(duì)于相鄰的兩顆珠子，前一顆珠子的尾標(biāo)記一定等于后一顆珠子的頭標(biāo)記。因?yàn)?，通過(guò)吸盤(pán)（吸盤(pán)是 Mars 人吸收能量的一種）的作用，這兩顆珠子才能聚一顆珠子，同時(shí)出可以被吸盤(pán)吸收的能量。如果前一顆能量珠的頭標(biāo)記為 m，尾標(biāo)記為 r，后一顆能量珠的頭標(biāo)記為 r，尾標(biāo)記為 n，則聚合后的能量為在中，將求最小改為求最大，如果對(duì)所有可能結(jié)合的方式進(jìn)行全面搜索，可以

2、證明，對(duì)于 n 個(gè)矩陣連乘，不同的結(jié)合順序大約有 O(4n)種，當(dāng) n 較大時(shí)，顯然是行不通的。通常采用動(dòng)態(tài)規(guī)劃求解?？紤]連乘中的一段：ifstream myinf(energy.in,ios:nocreate);if(myinil()cerrn; for(i=0;ipi; for(i=n;i2*n;i+)pi=pi-n; myinf.close();file mynamen;void matrixch(p,n) /算法for(i,j;r=2;r=n;r+)for(i=1;i=n;i+)j=i+r-1; mij=0;for(k=i;kn)mk+1j=mk+1-nj-n;long t=mik+(

3、long)mk+1j+pi-1*pk*pj; if(tmij)mij=t;void out_neck(n) /輸出各階段最優(yōu)值i;ofstream myoutf1(energy.out); if(myoutf1.fail()cerrerror opening file mynamen; return;long t=0; for(i=1;it) t=mii+n-1;myoutf1 tendl; myoutf1.close();void main()init_neck(); matrixch(p,n); out_neck(n);2的方案(budget.pas/p)【問(wèn)題描述】今天很開(kāi)心，家里購(gòu)置的

4、新房就要領(lǐng)了，新房里有一間自己的很寬敞的房間。更讓他高興的是，昨天對(duì)他說(shuō)：“你的房間需要哪些物品，怎么布置，你說(shuō)了算，只要不超過(guò) N 元錢(qián)就行”。今天一早。就開(kāi)始做了，他把想買(mǎi)的物品分為兩類(lèi)：主件與附件，附件是從屬于某個(gè)主件的，下表就是一些主件與附件的例子：如果要買(mǎi)歸類(lèi)為附件的物品，必須先買(mǎi)該附件所屬的主件。每個(gè)主件可以有 0 個(gè)、1 個(gè)或 2個(gè)附件。附件不再有從屬于自己的附件。想買(mǎi)的東西很多，肯定會(huì)超過(guò)限定的 N 元。于是，他把每件物品規(guī)定了一個(gè)重要度，分為 5 等：用整數(shù) 15 表示，第 5 等最重要。他還從因特網(wǎng)上查到了每件物品的價(jià)格（都是 10 元的整數(shù)倍）。他希望在不超過(guò) N 元（可

5、以等于 N 元）的前提下，使每件物品的價(jià)格與重要度的乘積的總和最大。設(shè)第 j 件物品的價(jià)格為 vj，重要度為 wj，共選中了 k 件物品jk，則所求的總和為：vj1*wj1+vj2*wj2+ +vjk*wjk。（其中*為乘號(hào)）依次為 j1 ，j2，請(qǐng)你幫助【算法說(shuō)明】設(shè)計(jì)一個(gè)滿(mǎn)足要求的購(gòu)物單。此題是在 01 背包問(wèn)題的基礎(chǔ)上改編的，但比普及組類(lèi)似的一道題要難得多。一是數(shù)據(jù)量（物品個(gè)數(shù)）加大了，由 25 增到 60。二是設(shè)置了“附件”，使問(wèn)題難度加大，因此建議使用動(dòng)態(tài)規(guī)劃策略解題，而一般的遞歸回溯對(duì)較大的 m 會(huì)超時(shí)。（當(dāng)然還有其他一些可行的甚至更好的方法）。01 背包問(wèn)題的動(dòng)態(tài)規(guī)劃算法可在許多

6、書(shū)中找到。總錢(qián)數(shù)（32000）由于是 10 的整數(shù)倍，可以在0，3200中搜索，最后輸出時(shí)再乘以 10。由于附件的，每個(gè)物品的一種狀態(tài)可能變?yōu)?4 種狀態(tài)（只用主件，主件+附件 1，主件+主件附件電腦，掃描儀書(shū)柜書(shū)桌臺(tái)燈，文具工作椅無(wú)附件 2，主件+附件 1+附件 2）。這 4 種狀態(tài)是互相排斥的。因此在構(gòu)建動(dòng)態(tài)規(guī)劃的二維表時(shí)，相應(yīng)的行最多要處理 4 次（用循環(huán) for(j=1;j=4;j+)實(shí)現(xiàn)）。在 CPP 程序中，函數(shù)“void init_happy()”的功能是初始化處理：讀入已知數(shù)據(jù)，并計(jì)算數(shù)組 tmp, 存放每件物品對(duì)結(jié)果的貢獻(xiàn)值，這樣處理可減少許多重復(fù)的乘法。函數(shù)“ voidou

7、t_happy()”的功能是輸出結(jié)果。 函數(shù)“void oper1(k)”是遞歸回溯的部分。部分變量的含義如下：value：本次計(jì)算得到的目標(biāo)值， best 到目前為止，最好的目標(biāo)值。Allw：到目前為止已選定的物品的總價(jià)值。Nlimit：可用的錢(qián)數(shù)的最大值。主要變量說(shuō)明：vN3200=0;動(dòng)態(tài)規(guī)劃數(shù)組。最優(yōu)貢獻(xiàn)量（即價(jià)格與重要度的乘積）數(shù)組aN4=0;已知數(shù)據(jù)，0：，1：價(jià)格，2：重要度 3：主件bN5=0;經(jīng)處理后的數(shù)組，存放價(jià)格信息0：，1：?jiǎn)蝹€(gè)主件，2：主件加附件 1，3：主件加附件 2，4：主件加 2 個(gè)附件v2N5=0;經(jīng)處理后的數(shù)組，存放貢獻(xiàn)量信息nlimit：總錢(qián)數(shù)，nlimi

8、t2：總錢(qián)數(shù)/10，m:總物品數(shù)，m2:主件總數(shù)函數(shù)“void init_budg()“的功能包括：輸入已知數(shù)據(jù)，計(jì)算數(shù)組 bN5,v2N5及 nlimit2。函數(shù)“void out_budg() “的功能是輸出計(jì)算結(jié)果。函數(shù)“void oper1(分。k)”的作用是：前 k-1 件已處理完，現(xiàn)考慮處理前 k 件。是程序的部基本公式：設(shè)第 t 件物品的第j 種狀態(tài)的價(jià)格為 btj,貢獻(xiàn)量為 v2tj,則：對(duì)于 i=1,2,btj-1,vki=vk-1i （不使用第t 件物品）。對(duì)于 i=btj，,nlimit2,vki=max vk-1i（不使用第 t 件物品）， vk-1i-btj+v2tj

9、（使用第 t 件物品）。3作業(yè)調(diào)度方案(jsp.pas/p)【問(wèn)題描述】現(xiàn)在要利用 m 臺(tái)機(jī)器加工 n 個(gè)工件，每個(gè)工件都有 m 道工序，每道工序都在不同的指定的機(jī)器上完成。每個(gè)工件的每道工序都有指定的加工時(shí)間。每個(gè)工件的每個(gè)工序稱(chēng)為一個(gè)操作，用記號(hào) j-k 表示一個(gè)操作，其中 j 為 1 到 n 中的某個(gè)數(shù)字，為工件號(hào)；k 為 1 到 m 中的某個(gè)數(shù)字，為工序號(hào)，例如 2-4 表示第 2 個(gè)工件第 4 道工序的這個(gè)操作。在本題中，還給定對(duì)于各操作的一個(gè)安排順序。例如，當(dāng) n=3，m=2 時(shí)，“1-1，1-2，2-1，3-1，3-2，2-2”就是一個(gè)給定的安排順序，即先安排第 1 個(gè)工件的第

10、1 個(gè)工序，再安排第 1 個(gè)工件的第 2 個(gè)工序，然后再安排第 2 個(gè)工件的第 1 個(gè)工序，等等。一方面，每個(gè)操作的安排都要滿(mǎn)足以下的兩個(gè)約束條件。對(duì)同一個(gè)工件，每道工序必須在它前面的工序完成后才能開(kāi)始；同一時(shí)刻每一臺(tái)機(jī)器至多只能加工一個(gè)工件。另一方面，在安排后面的操作時(shí)，不能改動(dòng)前面已安排的操作的工作狀態(tài)。由于同一工件都是按工序的順序安排的，因此，只按原順序給出工件號(hào)，仍到同樣的安排順序，于是，在輸入數(shù)據(jù)中，這個(gè)安排順序簡(jiǎn)寫(xiě)為“1 1 2 3 3 2”。還要注意，“安排順序”只要求按照給定的順序安排每個(gè)操作。不一定是各機(jī)器上的實(shí)際操作順序。在具體實(shí)施時(shí)，有可能排在后面的某個(gè)操作比前面的某個(gè)操

11、作先完成。例如，取 n=3,m=2，已知數(shù)據(jù)如下：則對(duì)于安排順序“1 1 2 3 3 2”，下圖中的兩個(gè)實(shí)施方案都是正確的。但所需要的總時(shí)間分別是10 與 12。當(dāng)一個(gè)操作空檔），可以靠前到某臺(tái)機(jī)器的某個(gè)空檔時(shí)（機(jī)器上最后的尚未安排操作的部分也可以看作一個(gè)，也可以靠后或居中。為了使問(wèn)題簡(jiǎn)單一些，約定：在保證約束條件（1）（2）的條件下，盡量靠前。并且，還約定，如果有多個(gè)空檔可以，就在保證約束條件（1）（2）的條件下，到最前面的一個(gè)空檔。于是，在這些約定下，上例中的方案一是正確的，而方案二是不正確的。顯然，在這些約定下，對(duì)于給定的安排順序，符合該安排順序的實(shí)施方案是唯一的，請(qǐng)你計(jì)算出該方案完成全

12、部任務(wù)的總時(shí)間。【算法說(shuō)明】由于感到試卷在總體上偏難，本題在原基礎(chǔ)上做了較大的簡(jiǎn)化，取消了用遞歸回溯進(jìn)行搜索，對(duì)于已知的安排順序，只有一個(gè)實(shí)施方案。問(wèn)題的難點(diǎn)是涉及的量太多，要有好的數(shù)據(jù)結(jié)構(gòu)，還要十分細(xì)心。詳細(xì)處理可參看程序中的注釋。42k 進(jìn)制數(shù)（digital.pas/p）【問(wèn)題描述】設(shè) r 是個(gè) 2k 進(jìn)制數(shù)，并滿(mǎn)足以下條件：（1）r 至少是個(gè) 2 位的 2k 進(jìn)制數(shù)。作為 2k 進(jìn)制數(shù)，除最后一位外，r 的每一位嚴(yán)格小于它右邊相鄰的那一位。將 r 轉(zhuǎn)換為 2 進(jìn)制數(shù) q 后，則 q 的總位數(shù)不超過(guò) w。在這里，正整數(shù) k（1k9）和 w（kw30000）是事先給定的。問(wèn)：滿(mǎn)足上述條件的

13、不同的 r 共有多少個(gè)？工件號(hào)機(jī)器號(hào)/加工時(shí)間工序 1工序 211/32/221/22/532/21/4再?gòu)牧硪唤嵌茸餍┙忉專(zhuān)涸O(shè) S 是長(zhǎng)度為 w 的 01 字符串（即字符串 S 由 w 個(gè)“0”或“1”組成），S 對(duì)應(yīng)于上述條件（3）中的 q。將 S 從右起劃分為若干個(gè)長(zhǎng)度為 k 的段，每段對(duì)應(yīng)一位 2k 進(jìn)制的數(shù)，如果 S 至少可分成 2 段，則 S 所對(duì)應(yīng)的二進(jìn)制數(shù)又可以轉(zhuǎn)換為上述的 2k 進(jìn)制數(shù) r。例：設(shè) k=3，w=7。則 r 是個(gè)八進(jìn)制數(shù)（23=8）。由于 w=7，長(zhǎng)度為 7 的 01 字符串按 3 位一段分，可分為 3 段（即 1，3，3，左邊第一段只有一個(gè)二進(jìn)制位），則滿(mǎn)足條件的八進(jìn)制數(shù)有：2 位數(shù)：為 1：6 個(gè)（即 12，13，