【正文】 ，互相以一個(gè)空格分隔。.第i個(gè)整數(shù)表示他進(jìn)入第i號(hào)山的洞穴后能夠到達(dá)的不同的山的個(gè)數(shù). Sample Input Sample Output5 0 1 2 3 41 2 3 4 5題36。光榮的夢(mèng)想Problem 依次給出n個(gè)整數(shù)序列，每次只能交換相鄰兩個(gè)數(shù)，問最少需要交換幾次才能使整個(gè)序列有序。Input第一行為數(shù)列中數(shù)的個(gè)數(shù)n= 10000,第二行為n個(gè)數(shù)。表示當(dāng)前數(shù)列的狀態(tài)。Output輸出一個(gè)整數(shù)，表示最少需要交換幾次能達(dá)到升序狀態(tài)。Sample Input Sample Output4 22 1 4 3題37。 【題目描述】光光回到家，完成了雙休日的作業(yè)，就開始看書，光光對(duì)歷史非常感興趣，于是光光就開始看一本古印度的書。書上面印了很多的象形文字，為了敘述簡(jiǎn)便，我們把每一種形狀的象形文字抽象成為一個(gè)1到70的數(shù)字，比如有這么一串文字：1 27 50 27 29,光光好像看出了什么,覺得如果添加上若干個(gè)文字之后，就能夠成為一個(gè)回文的一句話。比如上面一句話最少需要添加兩個(gè)字才能變?yōu)榛匚牡囊痪湓?。添加方法分別為：（1）方法1：1 29 27 50 27 29 1,或 （2）方法2：29 1 27 50 27 1 29 我們可以知道，給定一句話，通過添加若干個(gè)字符是可以成為一個(gè)回文句子的。因此，光光需要知道，他最少需要添加多少個(gè)文字，才能使這句話變成回文的?【輸入格式】：第一行:一個(gè)數(shù)字n，代表原句有n個(gè)字符。第二行:n個(gè)數(shù)字，代表這句話的內(nèi)容?！据敵龈袷健?，代表了最少添加文字的個(gè)數(shù)?！緲永斎搿? 【樣例輸出】5 21 27 50 27 29【數(shù)據(jù)規(guī)模】 30%的數(shù)據(jù)中，n=200。 100%的數(shù)據(jù)中，n=5000。題42。[Sense of Beauty] 【問題描述】有兩堆卡片，每堆卡片有n（4≤n≤1000）張，所有卡片中有n張是紅色的，n張是藍(lán)色的?，F(xiàn)在要將卡片逐張取下，紅的放在一起，藍(lán)的放在一起，每堆卡片中只能取最上面的那張，且要求任意時(shí)刻，已取得的紅色卡片數(shù)和藍(lán)色卡片數(shù)相差不超過1張，問如何取，才能完成任務(wù)？【輸入】第一行一個(gè)整數(shù)n，表示每堆卡片的張數(shù)。第二行有n個(gè)字符，表示第一堆的卡片顏色，第三行有n個(gè)字符，表示第二堆的卡片顏色。其中0代表紅色，1代表藍(lán)色，每行的第1個(gè)字符代表最上面的卡片顏色，第n個(gè)字符代表最下面的卡片顏色。【輸出】一行共2n個(gè)字符，表示一種取卡片的方案，如果有多種可行方案，只要輸出任意一種即可。其中字符1代表取自第一堆，字符2代表取自第二堆。如果不存在可行方案，則輸出一行“Impossible”?！緲永斎?】400110110【樣例輸出1】22121112【樣例輸入2】411001100【樣例輸出2】Impossible題43。[Fiscal operations] 【問題描述】有三個(gè)整數(shù)A、B、C，1≤A≤101000，1≤B≤101000，1≤C≤101000），如何改變A、B、C的某些位，使得A+B=C？改變一個(gè)數(shù)的某位的代價(jià)，為該位改變前后數(shù)字的差的絕對(duì)值。最終的代價(jià)為所有位的代價(jià)之和。你不能使三個(gè)數(shù)中的任一個(gè)減少位數(shù)（使最高位變0），也不能增加位數(shù)（在最高位前增加若干位）。【輸入】第一行一個(gè)整數(shù)A（1≤A≤101000），第二行一個(gè)整數(shù)B（1≤B≤101000），第三行一個(gè)整數(shù)C（1≤C≤101000）。【輸出】一個(gè)整數(shù)，表示最小代價(jià)。如果無論怎樣改變，A+B都不能等于C，則輸出“1”?！緲永斎搿?23554345【樣例輸出】8【樣例說明】可以將A變?yōu)?21，代價(jià)2，將B變?yōu)?24，代價(jià)5，將C變?yōu)?45，代價(jià)1，總代價(jià)為8。題44。[Kinversions] 【問題描述】給出一個(gè)排列a1,a2,…,an（所有的ai均為1至n之間的互不相同的整數(shù)）。如果1≤i1i2…ik且ai1ai2…aik，則將ai1,ai2,…,aik稱為長(zhǎng)度為k的遞減子序列。求排列a1,a2,…,an中長(zhǎng)度為k的遞減子序列數(shù)?！据斎搿康谝恍卸€(gè)正整數(shù)n和k，互相間以一個(gè)空格分隔。1≤n≤2000（原題中為20000）， 2≤k≤10。第二行有n個(gè)整數(shù)，表示給出的一個(gè)排列。【輸出】一個(gè)整數(shù)，表示長(zhǎng)度為K的遞減子序列數(shù)除以109后的余數(shù)?！緲永斎?】3 23 1 2【樣例輸出1】2【樣例輸入2】5 35 4 3 2 1【樣例輸出2】10題45。[Ents] 【問題描述】艾爾夫教會(huì)一只螞蟻兩個(gè)單詞。以后，螞蟻按照以下方法學(xué)習(xí)單詞：1)艾爾夫已經(jīng)教過的螞蟻會(huì)選沒有掌握任何單詞的一只老螞蟻和一只年輕螞蟻，讓他們學(xué)會(huì)自己掌握的所有單詞。2)上一步學(xué)習(xí)過的螞蟻中，艾爾夫教會(huì)老螞蟻一個(gè)新單詞，教會(huì)年輕螞蟻的單詞數(shù)等于它已經(jīng)掌握的單詞數(shù)。3)艾爾夫教過的螞蟻，不能再進(jìn)一步學(xué)習(xí)新的單詞。螞蟻的數(shù)量有足夠多，請(qǐng)問有多少只螞蟻掌握了K個(gè)單詞？【輸入】第一行二個(gè)正整數(shù)K和P，互相間以一個(gè)空格分隔。K≤107， P≤109?！据敵觥恳粋€(gè)整數(shù)，表示掌握K個(gè)單詞的螞蟻數(shù)量除以P的余數(shù)?！緲永斎搿? 10【樣例輸出】2題46。[Martian army] 【問題描述】有n個(gè)點(diǎn)，連成一棵樹，每個(gè)節(jié)點(diǎn)處有一個(gè)權(quán)值，樹根為1號(hào)點(diǎn)，權(quán)值為1，樹葉處權(quán)值為0，其余點(diǎn)處的權(quán)值為一些未知的實(shí)數(shù)。除了樹根外，所有點(diǎn)的父結(jié)點(diǎn)編號(hào)小于該點(diǎn)的編號(hào)。樹中每條邊有一個(gè)權(quán)值。比如，權(quán)值為Aij連接點(diǎn)I和點(diǎn)j，點(diǎn)I和點(diǎn)j處的權(quán)值分別為Bi和Bj，則在邊ij處能得到一個(gè)乘積|BiBj|*Aij（與邊相連的兩點(diǎn)處權(quán)值之差的絕對(duì)值，乘上邊上的權(quán)值），求如何安排各點(diǎn)處的值，使所有邊上乘積之和最小?！据斎搿康谝恍幸粋€(gè)整數(shù)n（2≤n≤100000）。第二行起至n行共n1行，每行有二個(gè)整數(shù)。第i行的二個(gè)整數(shù)Ki和Ci，表示第i點(diǎn)的父結(jié)點(diǎn)為Ki點(diǎn)，i與Ki間的邊上的權(quán)值為Ci。（1≤Kii≤n，0≤Ci≤1000）【輸出】一個(gè)整數(shù)，表示求得的最小值（保留兩位小數(shù)）?！緲永斎搿?1 102 52 33 13 23 3【樣例輸出】題47。[Email] 【問題描述】已知兩個(gè)由小寫英文構(gòu)成的字符串A和B，求長(zhǎng)度最小的字符串C，使得A和B均為C的子串。【輸入】二行，每行一個(gè)字符串，表示原串A和B。【輸出】一個(gè)整數(shù)，表示長(zhǎng)度最小的符合條件的字符串的個(gè)數(shù)，要求輸出所求得值除以109+7后的值?！緲永斎?】bab【樣例輸出1】1【樣例輸入2】abcabcba【樣例輸出2】4【提示】樣例2的情況時(shí)，所求的最小字符串長(zhǎng)度為4，共5個(gè)字符串，它們?yōu)閍bcaba或abcbab或 acbcab或 cabcab題48。[Eating High] 【問題描述】你和你的朋友共m個(gè)人去餐廳吃飯，餐廳中共有n種食品，每種食品能填飽不同數(shù)量的肚子，當(dāng)然每種食品的價(jià)格也是不同的。你想讓你們所有人都吃飽，又想花費(fèi)最少的錢。【輸入】第一行只有兩個(gè)整數(shù)N和M。N表示食品數(shù)，M表示就餐人數(shù)。(1 ≤ N ≤ 100。 1 ≤ M ≤ 20)以下N行描述N種食品。其中第k+1行有以兩個(gè)空格分隔的數(shù)據(jù)Sk Pk Nk，它們分別表示第k種食品：名稱為Sk（1至30個(gè)的小寫英文字母），價(jià)格為Pk（1至10000之間），每個(gè)能填飽Nk個(gè)人的肚子（，最多三位小數(shù)）?！据敵觥康谝恍幸粋€(gè)整數(shù)，表示最少的錢數(shù)。 第二行起的若干行表示最少錢數(shù)時(shí)的訂單，每行表示訂制的一種食品，包括食品名稱和食品份數(shù)，互相間以一個(gè)空格分隔。相同的食品不能放在不同行輸出，如果有多種方案，則輸出食品數(shù)最多的一種方案即可?！緲永斎搿? 6pizza 320 turkey 1050 lasagna 150 pasta 75 【樣例輸出】865pizza 2lasagna 1pasta 1題49。[三素?cái)?shù)數(shù)] 【問題描述】如果一個(gè)數(shù)的所有連續(xù)三位數(shù)字都是大于100的素?cái)?shù)，則該數(shù)稱為三素?cái)?shù)數(shù)。比如113797是一個(gè)6位的三素?cái)?shù)數(shù)?！据斎搿恳粋€(gè)整數(shù)n（3 ≤ n ≤ 10000），表示三素?cái)?shù)數(shù)的位數(shù)?！据敵觥恳粋€(gè)整數(shù)，表示n位三素?cái)?shù)的個(gè)數(shù)m，要求輸出m除以109 + 9的余數(shù)。題50。礦工配餐 IOI2007 Day2第1題 現(xiàn)有兩個(gè)煤礦，每個(gè)煤礦都雇用一組礦工。采煤工作很辛苦，所以礦工們需要良好飲食。每當(dāng)一輛食品車到達(dá)煤礦時(shí)，礦工們便會(huì)產(chǎn)出一定數(shù)量的煤。有三種類型的食品車：肉車，魚車和面包車。礦工們喜歡變化的食譜。如果提供的食品能夠不斷變化，他們的產(chǎn)煤量將會(huì)增加。每當(dāng)一個(gè)新的食品車到達(dá)煤礦時(shí)，礦工們就會(huì)比較這種新的食品和前兩次（或者少于兩次，如果前面運(yùn)送食品的次數(shù)不足兩次）的食品，并且：如果這幾次食品車都是同一類型的食品，則礦工們產(chǎn)出一個(gè)單位的煤。如果這幾次食品車中有兩種不同類型的食品，則礦工們產(chǎn)出兩個(gè)單位的煤。如果這幾次食品車中有三種不同類型的食品，則礦工們產(chǎn)出三個(gè)單位的煤。預(yù)先已知食品車的類型及其被配送的順序。通過確定哪車食品送到哪個(gè)煤礦可以影響產(chǎn)煤量。食品車不能被拆分，每個(gè)食品車必須被全部送到一個(gè)或另一個(gè)煤礦。兩個(gè)煤礦也并不要求接收相同數(shù)量的食品車（事實(shí)上，也允許將所有食品車都送到一個(gè)煤礦）。任務(wù)給出食品車的類型及其被配送的順序，要求你寫一個(gè)程序，確定哪個(gè)食品車應(yīng)被送到煤礦1，哪個(gè)食品車應(yīng)被送到煤礦2，以使得兩個(gè)煤礦的產(chǎn)煤量的總和最大。輸入輸入的第一行包含一個(gè)整數(shù)N (1 ≤ N ≤ 100000), 表示食品車的數(shù)目。第二行包含一個(gè)由N個(gè)字符組成的字符串，按照配送順序依次表示食品車配送的食品的類型。每個(gè)字符是以下三個(gè)大寫字母之一：39。M39。 (表示肉類), 39。F39。 (表示魚類) 或 39。B39。 (表示面包)。輸出輸出一個(gè)整數(shù)，表示最大的總產(chǎn)煤量。評(píng)分在45分的測(cè)試數(shù)據(jù)中，食品車的數(shù)目至多為20。提交時(shí)的反饋細(xì)節(jié)在競(jìng)賽中，對(duì)于這個(gè)題目，你可以選擇至多10次提交在部分正式測(cè)試數(shù)據(jù)上進(jìn)行測(cè)評(píng)。測(cè)評(píng)結(jié)束后，可以從競(jìng)賽系統(tǒng)中得到關(guān)于測(cè)試結(jié)果的總結(jié)。樣例Input6MBMFFBoutput12input16MMBMBBBBMMMMMBMBoutput29在左邊的例子中，可以按照如下的順序運(yùn)送食品車：煤礦 1, 煤礦 1, 煤礦 2, 煤礦 2, 煤礦 1, 煤礦 2, 依次產(chǎn)生的產(chǎn)煤量為1, 2, 1, 2, 3 和 3 個(gè)單位，一共是12 個(gè)單位。還有其它運(yùn)送方式也能產(chǎn)生上述最大總和的產(chǎn)煤量。（王宏譯，李文新校）