沖刺N(yùn)OIP2010模擬試題五.doc

NOIP2010模擬試題、（提高組 復(fù)賽）一、無窮的序列（seq）【問題描述】有一個(gè)無窮序列如下：110100100010000100000請(qǐng)你找出這個(gè)無窮序列中指定位置上的數(shù)字【輸入】第一行一個(gè)正整數(shù)N，表示詢問次數(shù)；接下來的N行每行一個(gè)正整數(shù)Ai，Ai表示在序列中的位置?！据敵觥縉行，每行為0或1，表示序列第Ai位上的數(shù)字?！据斎霕永?43 14 76【輸出樣例】 00 10【數(shù)據(jù)范圍】對(duì)于100%的數(shù)據(jù)有N1500000，Ai109二、湯姆斯的天堂夢(mèng)（par）【問題描述】湯姆斯生活在一個(gè)等級(jí)為0的星球上。那里的環(huán)境極其惡劣。每天12小時(shí)的工作和成堆的垃圾讓人忍無可忍。他向往著等級(jí)為N的星球上天堂般的生活。有一些航班將人從低等級(jí)的星球送上高一級(jí)的星球，有時(shí)需要向駕駛員支付一定金額的費(fèi)用，有時(shí)卻又可以得到一定的金錢。湯姆斯預(yù)先知道了從0等級(jí)星球去N等級(jí)星球的所有的航線和所需支付（或者可以得到）的金錢，他想找一條價(jià)格最低（甚至獲得金錢最多）的航線?！据斎搿康谝恍械谝粋€(gè)正整數(shù)N（N100），接下來的數(shù)據(jù)可分為N個(gè)段落。每段的第一行一個(gè)整數(shù)Ki（Ki100），表示等級(jí)為i的星球有Ki個(gè)。接下來的Ki中第Tij行依次表示與等級(jí)為i，編號(hào)為j的星球相連的等級(jí)為i-1的星球的編號(hào)和此航線需要的費(fèi)用（正數(shù)表示支出，負(fù)數(shù)表示收益，費(fèi)用的絕對(duì)值不超過1000）。每行以0結(jié)束，每行的航線數(shù)100?！据敵觥枯敵鏊瑁ɑ蛩茫┵M(fèi)用。正數(shù)表示支出，負(fù)數(shù)表示收益?！据斎霕永?32 1 15 0 1 5 0 31-52 10 0 1 3 0 2 40 0 21 12 5 3 -5 0 2-19 3-20 0【輸出樣例】-1【數(shù)據(jù)范圍】對(duì)于100%的數(shù)據(jù)N100 Ki100?！緲永忉尅咳鐖D3.13.22.11.10.11.22.32.25151040-20-5-551-19三、克魯斯的加減法（plus）【問題描述】奶?？唆斔拐J(rèn)為人類的加法算式太落后了。比如說有時(shí)候想要用加法計(jì)算+15*3.，只能寫成+15+15+15。真是浪費(fèi)精力啊！于是，克魯斯決定開發(fā)出一種新的加法算式。當(dāng)然新的算式也是建立在原本算式的基礎(chǔ)上的，不同就在于上式可以直接寫成+15，當(dāng)然對(duì)于15*3這樣的算式可以寫成15。一段時(shí)間后，克魯斯有被那無窮多個(gè)+號(hào) 到了，于是他又將這個(gè)算式改進(jìn)了一下。比如+15*3又可以寫成+(3)15，當(dāng)然，15*3等價(jià)于(3)15.但是從上面可以看出，對(duì)于乘數(shù)較小的情況，如+15這樣的表述還是很方便的，于是在新的算式中還是保留了這種丑陋的形式。對(duì)于算式還有做一點(diǎn)特殊的說明：+15*3轉(zhuǎn)換成魯克斯型算式時(shí)可以寫成+15或+(3)15，但是不可以寫成+(2)15這樣的形式。對(duì)于算式23+15*32可以表示為以下幾種形式：23+15223+(3)152+23+152+23+(3)152+(1)23+(3)15(1)2不會(huì)出現(xiàn)如下幾種形式：(1)23+152+23+(2)15(1)223+152+(0)10023(3)152【輸入】一行，一個(gè)克魯斯型算式。【輸出】一行，為運(yùn)算結(jié)果?！据斎霕永?(1)23+(3)15(1)2【輸出樣例】66【數(shù)據(jù)范圍】對(duì)于20%的數(shù)據(jù)，輸入長度不超過10；對(duì)于100%的數(shù)據(jù)，輸入長度不超過200。四、小明搬家（box）小明要搬家了，大家都來幫忙。小明現(xiàn)在住在第N樓，總共K個(gè)人要把X個(gè)大箱子搬上N樓。最開始X個(gè)箱子都在1樓，但是經(jīng)過一段混亂的搬運(yùn)已經(jīng)亂掉了。最后，大家發(fā)現(xiàn)這樣混亂的搬運(yùn)過程效率太低了，于是總結(jié)出了提高效率的方法。大家的速度都是每分鐘上或下層樓。多余向上走的人手中都拿一個(gè)箱子，所有向下走的人手中都不拿箱子。到達(dá)第N層立刻放下箱子向下走，到達(dá)第1層立刻拿起箱子向上走。當(dāng)一個(gè)人向上走，另一個(gè)人向下走而在樓道相遇時(shí)，向上走的人將手中的箱子交割另一個(gè)人，兩人同時(shí)反向。即原來拿箱子向上走的人不拿箱子往下走。原來不拿箱子向下走的人現(xiàn)在拿著箱子向上走。求將所有箱子搬完所需的最短時(shí)間?！据斎搿康谝恍蠳（N109），K（K500000），M（M109），分別比表示樓層數(shù)、人數(shù)、還放在一樓地上的箱子數(shù)。接下來K行，每行兩個(gè)數(shù)Ai，Bi。Ai表示第i人現(xiàn)所在的樓層數(shù)，Bi為0或1.，為0表示第i人正拿著箱子往上走，為1表示第i人不拿箱子向下走。輸入滿足沒有任意兩個(gè)人正在同一樓層，在第1層的人一定正拿著箱子向上走，在第N層的人一定正不拿著箱子向下走。【輸出】僅包含一個(gè)整數(shù)，為