【正文】 （王宏譯，李文新校）。樣例Input6MBMFFBoutput12input16MMBMBBBBMMMMMBMBoutput29在左邊的例子中，可以按照如下的順序運送食品車：煤礦 1, 煤礦 1, 煤礦 2, 煤礦 2, 煤礦 1, 煤礦 2, 依次產(chǎn)生的產(chǎn)煤量為1, 2, 1, 2, 3 和 3 個單位，一共是12 個單位。提交時的反饋細(xì)節(jié)在競賽中，對于這個題目，你可以選擇至多10次提交在部分正式測試數(shù)據(jù)上進(jìn)行測評。輸出輸出一個整數(shù)，表示最大的總產(chǎn)煤量。B39。F39。M39。第二行包含一個由N個字符組成的字符串，按照配送順序依次表示食品車配送的食品的類型。輸入輸入的第一行包含一個整數(shù)N (1 ≤ N ≤ 100兩個煤礦也并不要求接收相同數(shù)量的食品車（事實上，也允許將所有食品車都送到一個煤礦）。通過確定哪車食品送到哪個煤礦可以影響產(chǎn)煤量。如果這幾次食品車中有三種不同類型的食品，則礦工們產(chǎn)出三個單位的煤。每當(dāng)一個新的食品車到達(dá)煤礦時，礦工們就會比較這種新的食品和前兩次（或者少于兩次，如果前面運送食品的次數(shù)不足兩次）的食品，并且：如果這幾次食品車都是同一類型的食品，則礦工們產(chǎn)出一個單位的煤。礦工們喜歡變化的食譜。每當(dāng)一輛食品車到達(dá)煤礦時，礦工們便會產(chǎn)出一定數(shù)量的煤。礦工配餐 IOI2007 Day2第1題 現(xiàn)有兩個煤礦，每個煤礦都雇用一組礦工?！据敵觥恳粋€整數(shù)，表示n位三素數(shù)的個數(shù)m，要求輸出m除以109 + 9的余數(shù)。比如113797是一個6位的三素數(shù)數(shù)。【樣例輸入】4 6pizza 320 turkey 1050 lasagna 150 pasta 75 【樣例輸出】865pizza 2lasagna 1pasta 1題49。 第二行起的若干行表示最少錢數(shù)時的訂單，每行表示訂制的一種食品，包括食品名稱和食品份數(shù)，互相間以一個空格分隔。其中第k+1行有以兩個空格分隔的數(shù)據(jù)Sk Pk Nk，它們分別表示第k種食品：名稱為Sk（1至30個的小寫英文字母），價格為Pk（1至10000之間），每個能填飽Nk個人的肚子（，最多三位小數(shù)）。(1 ≤ N ≤ 100?！据斎搿康谝恍兄挥袃蓚€整數(shù)N和M。[Eating High] 【問題描述】你和你的朋友共m個人去餐廳吃飯，餐廳中共有n種食品，每種食品能填飽不同數(shù)量的肚子，當(dāng)然每種食品的價格也是不同的。7后的值。【輸出】一個整數(shù)，表示長度最小的符合條件的字符串的個數(shù)，要求輸出所求得值除以109[Email] 【問題描述】已知兩個由小寫英文構(gòu)成的字符串A和B，求長度最小的字符串C，使得A和B均為C的子串。（1≤Kii≤n，0≤Ci≤1000）【輸出】一個整數(shù)，表示求得的最小值（保留兩位小數(shù)）。第二行起至n行共n1行，每行有二個整數(shù)。比如，權(quán)值為Aij連接點I和點j，點I和點j處的權(quán)值分別為Bi和Bj，則在邊ij處能得到一個乘積|BiBj|*Aij（與邊相連的兩點處權(quán)值之差的絕對值，乘上邊上的權(quán)值），求如何安排各點處的值，使所有邊上乘積之和最小。除了樹根外，所有點的父結(jié)點編號小于該點的編號?！緲永斎搿? 10【樣例輸出】2題46。K≤107， P≤109。3)艾爾夫教過的螞蟻，不能再進(jìn)一步學(xué)習(xí)新的單詞。以后，螞蟻按照以下方法學(xué)習(xí)單詞：1)艾爾夫已經(jīng)教過的螞蟻會選沒有掌握任何單詞的一只老螞蟻和一只年輕螞蟻，讓他們學(xué)會自己掌握的所有單詞?！緲永斎?】3 23 1 2【樣例輸出1】2【樣例輸入2】5 35 4 3 2 1【樣例輸出2】10題45。第二行有n個整數(shù)，表示給出的一個排列?！据斎搿康谝恍卸€正整數(shù)n和k，互相間以一個空格分隔。如果1≤i1i2…ik且ai1ai2…aik，則將ai1,ai2,…,aik稱為長度為k的遞減子序列。題44。如果無論怎樣改變，A+B都不能等于C，則輸出“1”?！据斎搿康谝恍幸粋€整數(shù)A（1≤A≤101000），第二行一個整數(shù)B（1≤B≤101000），第三行一個整數(shù)C（1≤C≤101000）。最終的代價為所有位的代價之和?！緲永斎?】400110110【樣例輸出1】22121112【樣例輸入2】411001100【樣例輸出2】Impossible題43。其中字符1代表取自第一堆，字符2代表取自第二堆。其中0代表紅色，1代表藍(lán)色，每行的第1個字符代表最上面的卡片顏色，第n個字符代表最下面的卡片顏色?，F(xiàn)在要將卡片逐張取下，紅的放在一起，藍(lán)的放在一起，每堆卡片中只能取最上面的那張，且要求任意時刻，已取得的紅色卡片數(shù)和藍(lán)色卡片數(shù)相差不超過1張，問如何取，才能完成任務(wù)？【輸入】第一行一個整數(shù)n，表示每堆卡片的張數(shù)。題42?！緲永斎搿? 【樣例輸出】5 21 27 50 27 29【數(shù)據(jù)規(guī)?！? 30%的數(shù)據(jù)中，n=200。第二行:n個數(shù)字，代表這句話的內(nèi)容。添加方法分別為：（1）方法1：1 29 27 50 27 29 1,或 （2）方法2：29 1 27 50 27 1 29 我們可以知道，給定一句話，通過添加若干個字符是可以成為一個回文句子的。書上面印了很多的象形文字，為了敘述簡便，我們把每一種形狀的象形文字抽象成為一個1到70的數(shù)字，比如有這么一串文字：1 27 50 27 29,光光好像看出了什么,覺得如果添加上若干個文字之后，就能夠成為一個回文的一句話。Sample Input Sample Output4 22 1 4 3題37。表示當(dāng)前數(shù)列的狀態(tài)。光榮的夢想Problem 依次給出n個整數(shù)序列，每次只能交換相鄰兩個數(shù)，問最少需要交換幾次才能使整個序列有序。另外兩座山可以有相同的高度. (1=每座山的高度=maxlongint) Output共一行n個整數(shù)，互相以一個空格分隔。小卡卡很想知道進(jìn)入每座山的洞穴后,他所到達(dá)的不同的山會有多少種可能。Pascal山的山頂有一個神奇的洞穴,進(jìn)入這個洞穴后,你將會到達(dá)這座山前方的另一座山,更加神奇的是,你到達(dá)的山一定比他所在的山高度要小。Pascal山脈Problem 小卡卡順著老者所指的方向,來到了Pascal神峰的頂峰。注：數(shù)據(jù)中的每個數(shù)值不會超過100000. ，表示Tom可以得到的最大加工費。接下來的n行中，每行有3個整數(shù)，分別表示每個零件加工的時間要求?，F(xiàn)在請你幫Tom設(shè)計一個程序,合理選擇部分(或全部)零件進(jìn)行加工,使得得到最大的加工費?，F(xiàn)在他卻遇到了麻煩,多家汽車制造商需要他加工一些不同零件(由于廠家和零件不同,所以給的加工費也不同）,而且不同廠家對于不同零件的加工時間要求不同(有些加工時間要求甚至是沖突的,但開始和結(jié)束時間相同不算沖突）。Tom的煩惱Problem Tom是一個非常有創(chuàng)業(yè)精神的人,由于大學(xué)學(xué)的是汽車制造專業(yè),所以畢業(yè)后他用有限的資金開了一家汽車零件加工廠 專門為汽車制造商制造零件?！緮?shù)據(jù)限制】本題共有10組測試數(shù)據(jù)，每組10分，共100分。(單位：J，1J＝1W以上n+1行中，每行的兩個整數(shù)之間都有一個空格分隔。第1行是兩個數(shù)字n和c，分別表示路燈數(shù)和老張所處位置的路燈號；第2行至第n+1行，每行有兩個整數(shù)。【樣例輸出】270 {此時關(guān)燈順序為34215，不必輸出這個關(guān)燈順序}【樣例輸入】5 32 103 205 206 308 10【樣例說明】有5盞燈，老張從第3盞燈開始關(guān)燈，最小耗電量=1*30+4*20+5*10+11*10=270 請你為老張編一程序來安排關(guān)燈的順序，使從老張開始關(guān)燈時刻算起所有燈消耗電最少（燈關(guān)掉后便不再消耗電了）。而事實并非如此，因為在關(guān)的過程中適當(dāng)?shù)卣{(diào)頭有可能會更省一些。他每天都是在天亮?xí)r首先關(guān)掉自己所處位置的路燈，然后可以向左也可以向右去關(guān)燈。老張就住在這條路中間某一路燈旁，他有一項工作就是每天早上天亮?xí)r一盞一盞地關(guān)掉這些路燈。如果q=0，表示該物品為主件，如果q0，表示該物品為附件，q是所屬主件的編號） 【輸出文件】，為不超過總錢數(shù)的物品的價格與重要度乘積的總和的最大值（200000）?！据斎胛募?的第1行，為兩個正整數(shù)，用一個空格隔開：N m（其中N（32000）表示總錢數(shù)，m（60）為希望購買物品的個數(shù)。設(shè)第j件物品的價格為v[j]，重要度為w[j]，共選中了k件物品，編號依次為j1，j2，……，jk，則所求的總和為：v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。他還從因特網(wǎng)上查到了每件物品的價格（都是10元的整數(shù)倍）。金明想買的東西很多，肯定會超過媽媽限定的N元。每個主件可以有0個、1個或2個附件。更讓他高興的是，媽媽昨天對他說：你的房間需要購買哪些物品，怎么布置，你說了算，只要不超過N元錢就行。【輸入樣例】 【輸出樣例】4 7102 3 5 10打印機，掃描儀附件圖書臺燈，文具無電腦主件書柜書桌工作椅題40。至于珠子的順序，你可以這樣確定：將項鏈放到桌面上，不要出現(xiàn)交叉，隨意指定第一顆珠子，然后按順時針方向確定其他珠子的順序。第i個數(shù)為第i顆珠子的頭標(biāo)記（1≤i≤N），當(dāng)iN時,第i顆珠子的尾標(biāo)記應(yīng)該等于第i+1顆珠子的頭標(biāo)記?！据斎胛募浚?≤N≤100），表示項鏈上珠子的個數(shù)。則第1兩顆珠子聚合后釋放的能量為：(4⊕1)=10*2*3=60。例如：設(shè)N=4，4顆珠子的頭標(biāo)記與尾標(biāo)記依次為(2，3) (3，5) (5，10) (10，2)。 需要時,Mars人就用吸盤夾住相鄰的兩顆珠子,通過聚合得到能量,直到項鏈上只剩下一顆珠子為止。因為只有這樣，通過吸盤（吸盤是Mars人吸收能量的一種器官）的作用，這兩顆珠子才能聚合成一顆珠子，同時釋放出可以被吸盤吸收的能量。能量珠是一顆有頭標(biāo)記與尾標(biāo)記的珠子，這些標(biāo)記對應(yīng)著某個正整數(shù)。【問題描述】在Mars星球上，每個Mars人都隨身佩帶著一串能量項鏈。假設(shè)n個物品的參數(shù)分別為1到n。輸入：，該行只有兩個整數(shù)n和t (1≤n≤20，0≤t≤n*(n1)/2 )。Grant是這家公司的排序員，他想知道對于n個參數(shù)都不同的物品組成的序列集合中，逆序?qū)?shù)為t的物品序列有多少個，并試給出其中一個最小的物品序列。若ij且AiAj，則i,j就為一個“逆序?qū)Α薄＃?,表示得到的最大值樣例輸入5樣例輸出7題21。1的最優(yōu)操作序列(請考慮使用動態(tài)規(guī)劃和其它方法解決此題) 在黑板上寫了N（n≤10000）個1，進(jìn)行如下操作：每次擦去其中兩個數(shù)a、b，并寫上數(shù)a*b+1，如此下去直至最后一個數(shù)A。數(shù)據(jù)規(guī)模