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

基本程序題集

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

　　題集目錄

　　一、貪心算法

　　Problem1刪數(shù)問題

　　Problem2旅行家的預(yù)算

　　Problem3線段覆蓋

　　Problem4背包問題

　　Problem5任務(wù)調(diào)度

　　Problem6果子合并

　　Problem7射擊競賽

　　Problem8任務(wù)安排

　　Problem9最小差距

　　二、 分治算法

　　Problem1一元三次方程的解

　　Problem2查找第k大元素

　　Problem3麥森數(shù)

　　Problem4逆序?qū)�個數(shù)

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

　　Problem6剔除多余括號

　　Problem7賽程安排

　　三、 搜索算法

　　Problem1皇后問題

　　Problem2八數(shù)碼問題

　　Problem3拼圖

　　Problem4質(zhì)數(shù)方陣

　　Problem5埃及分?jǐn)?shù)

　　Problem6字符串變換

　　Problem7聰明的打字員

　　Problem8 01序列

　　Problem9生日蛋糕

　　四、 圖論算法

　　Problem1一筆畫問題

　　Problem2 Car的旅行路線

　　Problem3求割點(diǎn)與橋

　　Problem4十字繡

　　Problem5舞會

　　Problem6休息中的小呆

　　Problem7最優(yōu)布線問題

　　Problem8磁盤碎片整理

　　Problem9說謊島

　　Problem10 01串問題

　　Problem11海島地圖

　　五、 數(shù)學(xué)問題

　　Problem1數(shù)的劃分

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

　　Problem3出棧序列統(tǒng)計(jì)

　　Problem4百事世界杯之旅

　　Problem5電子鎖

　　Problem6堆塔問題

　　Problem7取數(shù)游戲

　　Problem8球迷購票

　　Problem9 Fibonacci公約數(shù)

　　Problem10傳球問題

　　Problem11約瑟夫問題

　　Problem12青蛙過河

　　Problem13棋盤游戲

　　六、 數(shù)據(jù)結(jié)構(gòu)

　　Problem1火車棧

　　Problem2括號表達(dá)式

　　Problem3銀河英雄傳說

　　Problem4矩形覆蓋

　　Problem5最短路徑問題

　　Problem6果子合并

　　七、 字符串處理

　　Problem1相對分子質(zhì)量

　　Problem2表達(dá)式求值

　　Problem3偵探推理

　　Problem4最長公共子串

　　Problem5一元一次方程的解

　　Problem6多項(xiàng)式乘法

　　一、 貪心算法

　　Problem1刪數(shù)問題

　　題目描述：

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

　　輸入

　　輸入有兩行，第一行為整數(shù)n，第二行即為s

　　輸出

　　輸出一行，即最小的那個數(shù)

　　Problem2旅行家的預(yù)算

　　題目描述

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

　　輸入

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

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

　　輸出

　　輸出僅一行，即最少花費(fèi)

　　Problem3線段覆蓋

　　題目描述

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

　　輸入

　　輸入第一行為整數(shù)N，接下來有N行，分別描述每條線段

　　輸出

　　輸出第一行為最少刪除的線段數(shù)s

　　后面s行描述一個可行的刪除方案，即刪除那些線段

　　Problem4背包問題

　　題目描述

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

　　輸入

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

　　輸出

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

　　Problem5任務(wù)調(diào)度

　　題目描述

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

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

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

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

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

　　輸入

　　輸入第一行為N(N<=1000)，后面N行每行兩個數(shù)，即為對應(yīng)的di與wi

　　輸出

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

　　Problem6果子合并

　　題目描述

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

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

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

　　例如有3種果子，數(shù)目依次為1，2，9。可以先將1、2堆合并，新堆數(shù)目為3，耗費(fèi)體力為3。接著，將新堆與原先的第三堆合并，又得到新的堆，數(shù)目為12，耗費(fèi)體力為12。所以多多總共耗費(fèi)體力=3+12=15。可以證明15為最小的體力耗費(fèi)值。