信息學(xué)聯(lián)賽知識：基本程序題集

基本程序題集

　　NOIP是一個(gè)比較基礎的比賽，大家都說(shuō)NOIP是考察基本算法的熟練掌握，所以個(gè)人認為無(wú)論是普及組還是提高組，都要從最最基本的題做起，要達到：只要是簡(jiǎn)單題，編完就對--不用編譯；一般的題，寫(xiě)出來(lái)的都是對的--運行后幾本上是正確的。為了提高，于是做了一個(gè)基本程序題集，以便查找自己的不足之處。

　　題集目錄

　　一、貪心算法

　　Problem1刪數問(wèn)題

　　Problem2旅行家的預算

　　Problem3線(xiàn)段覆蓋

　　Problem4背包問(wèn)題

　　Problem5任務(wù)調度

　　Problem6果子合并

　　Problem7射擊競賽

　　Problem8任務(wù)安排

　　Problem9最小差距

　　二、 分治算法

　　Problem1一元三次方程的解

　　Problem2查找第k大元素

　　Problem3麥森數

　　Problem4逆序對個(gè)數

　　Problem5尋找最近點(diǎn)對

　　Problem6剔除多余括號

　　Problem7賽程安排

　　三、 搜索算法

　　Problem1皇后問(wèn)題

　　Problem2八數碼問(wèn)題

　　Problem3拼圖

　　Problem4質(zhì)數方陣

　　Problem5埃及分數

　　Problem6字符串變換

　　Problem7聰明的打字員

　　Problem8 01序列

　　Problem9生日蛋糕

　　四、 圖論算法

　　Problem1一筆畫(huà)問(wèn)題

　　Problem2 Car的旅行路線(xiàn)

　　Problem3求割點(diǎn)與橋

　　Problem4十字繡

　　Problem5舞會(huì )

　　Problem6休息中的小呆

　　Problem7最優(yōu)布線(xiàn)問(wèn)題

　　Problem8磁盤(pán)碎片整理

　　Problem9說(shuō)謊島

　　Problem10 01串問(wèn)題

　　Problem11海島地圖

　　五、 數學(xué)問(wèn)題

　　Problem1數的劃分

　　Problem2最優(yōu)分解方案

　　Problem3出棧序列統計

　　Problem4百事世界杯之旅

　　Problem5電子鎖

　　Problem6堆塔問(wèn)題

　　Problem7取數游戲

　　Problem8球迷購票

　　Problem9 Fibonacci公約數

　　Problem10傳球問(wèn)題

　　Problem11約瑟夫問(wèn)題

　　Problem12青蛙過(guò)河

　　Problem13棋盤(pán)游戲

　　六、 數據結構

　　Problem1火車(chē)棧

　　Problem2括號表達式

　　Problem3銀河英雄傳說(shuō)

　　Problem4矩形覆蓋

　　Problem5最短路徑問(wèn)題

　　Problem6果子合并

　　七、 字符串處理

　　Problem1相對分子質(zhì)量

　　Problem2表達式求值

　　Problem3偵探推理

　　Problem4最長(cháng)公共子串

　　Problem5一元一次方程的解

　　Problem6多項式乘法

　　一、 貪心算法

　　Problem1刪數問(wèn)題

　　題目描述：

　　給定一正整數n(n的位數小于240)，現要刪除數n中的s個(gè)數碼，使其得到的新數最小，求這個(gè)最小數。

　　輸入

　　輸入有兩行，第一行為整數n，第二行即為s

　　輸出

　　輸出一行，即最小的那個(gè)數

　　Problem2旅行家的預算

　　題目描述

　　一個(gè)旅行家想駕駛汽車(chē)以最少的費用從一個(gè)城市到另一個(gè)城市（假設出發(fā)時(shí)油箱是空的）。給定兩個(gè)城市之間的距離D1、汽車(chē)油箱的量C（以升為單位）、每升汽油能行駛的距離D2、出發(fā)點(diǎn)每升汽油價(jià)格P和沿途油站數N（N可以為零），油站i離出發(fā)點(diǎn)的距離i、每升汽油價(jià)格Pi（i=1，2，……N）。計算結果四舍五入至小數點(diǎn)后兩位。如果無(wú)法到達目的地，則輸出"No Solution"。

　　輸入

　　輸入第一行有5個(gè)數：D1，c，D2，P，N(前四個(gè)為實(shí)數，N為整數,N<=1000)

　　后面有N行，每行兩個(gè)實(shí)數，分別表示對應的加油站離出發(fā)點(diǎn)的距離，與每升汽油的價(jià)格

　　輸出

　　輸出僅一行，即最少花費

　　Problem3線(xiàn)段覆蓋

　　題目描述

　　給定數軸上的n條線(xiàn)段(n<100)，每個(gè)線(xiàn)段有其端點(diǎn)ai、bi組成(-999<=ai<bi<=999)，由于有些線(xiàn)段會(huì )相互覆蓋，所以求出至少去掉多少條線(xiàn)段，才能使剩下的所有線(xiàn)段之間互相沒(méi)有內部公共點(diǎn)(若只是端點(diǎn)重合，則不是內部公共點(diǎn))。

　　輸入

　　輸入第一行為整數N，接下來(lái)有N行，分別描述每條線(xiàn)段

　　輸出

　　輸出第一行為最少刪除的線(xiàn)段數s

　　后面s行描述一個(gè)可行的刪除方案，即刪除那些線(xiàn)段

　　Problem4背包問(wèn)題

　　題目描述

　　有一個(gè)賊在偷竊一家商店時(shí)發(fā)現有N件物品:第i件物品值Vi元，重Wi磅，(1≤i≤n)，此處Vi和Wi都是整數。他希望帶走的東西越值錢(qián)越好，但他的背包中最多只能裝下W磅的東西(W為整數)，小偷可帶走某個(gè)物品的一部分(只帶走其中的幾磅)，小偷應該帶走哪幾件東西，每件東西的重量是多少？

　　輸入

　　輸入第一行為N(N<=10000)，后面N行描述每個(gè)物品，每行兩個(gè)數，即為Vi與Wi

　　輸出

　　輸出第一行為大的最大價(jià)值，后面依次描述物品i應偷多少(如果沒(méi)偷，則不輸出，輸出對應的i為升序)。

　　Problem5任務(wù)調度

　　題目描述

　　一個(gè)單位時(shí)間任務(wù)是個(gè)作業(yè),如要在計算機上運行一個(gè)程序,它恰覆蓋一個(gè)單位的運行時(shí)間。給定一個(gè)單位時(shí)間任務(wù)的集合S,對S的一個(gè)調度即S的一個(gè)排列,其中規定了這些任務(wù)的執行順序。該調度中的第一個(gè)任務(wù)開(kāi)始于時(shí)間0,結束于時(shí)1;第二個(gè)任務(wù)開(kāi)始于時(shí)間1, 結束于時(shí)間2;……。單處理器上具有期限和罰款的單位時(shí)間任務(wù)調度問(wèn)題的輸入如下:

　　1.包含n個(gè)單位時(shí)間任務(wù)的集合S={1,2,……,n};

　　2.n個(gè)取整的期限d1,……,dn,(1≤d,≤n),任務(wù)i要求在di前完成;

　　3.n個(gè)非負的權(或罰款)w1,……,wn。如果任務(wù)i沒(méi)在時(shí)間di之前結束,則導致罰款wi;

　　要求找出S的一個(gè)調度,使之最小化總的罰款。

　　輸入

　　輸入第一行為N(N<=1000)，后面N行每行兩個(gè)數，即為對應的di與wi

　　輸出

　　輸出最小總罰款Problem6果子合并

　　Problem6果子合并

　　題目描述

　　在一個(gè)果園里，多多已經(jīng)將所有的果子打了下來(lái)，而且按果子的不同種類(lèi)分成了不同的堆。多多決定把所有的果子合成一堆。

　　每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和�？梢钥闯�，所有的果子經(jīng)過(guò)n-1次合并之后，就只剩下一堆了。多多在合并果子時(shí)總共消耗的體力等于每次合并所耗體力之和。

　　因為還要花大力氣把這些果子搬回家，所以多多在合并果子時(shí)要盡可能地節省體力。假定每個(gè)果子重量都為1，并且已知果子的種類(lèi)數和每種果子的數目，你的任務(wù)是設計出合并的次序方案，使多多耗費的體力最少，并輸出這個(gè)最小的體力耗費值。

　　例如有3種果子，數目依次為1，2，9�？梢韵葘�1、2堆合并，新堆數目為3，耗費體力為3。接著(zhù)，將新堆與原先的第三堆合并，又得到新的堆，數目為12，耗費體力為12。所以多多總共耗費體力=3+12=15�？梢宰C明15為最小的體力耗費值。