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

基本程序題集

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

　　題集目錄

　　一、貪心算法

　　Problem1刪數(shù)問題

　　Problem2旅行家的預(yù)算

　　Problem3線段覆蓋

　　Problem4背包問題

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

　　Problem6果子合并

　　Problem7射擊競賽

　　Problem8任務(wù)安排

　　Problem9最小差距

　　二、 分治算法

　　Problem1一元三次方程的解

　　Problem2查找第k大元素

　　Problem3麥森數(shù)

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

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

　　Problem6剔除多余括號(hào)

　　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舞會(huì)

　　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括號(hào)表達(dá)式

　　Problem3銀河英雄傳說

　　Problem4矩形覆蓋

　　Problem5最短路徑問題

　　Problem6果子合并

　　七、 字符串處理

　　Problem1相對分子質(zhì)量

　　Problem2表達(dá)式求值

　　Problem3偵探推理

　　Problem4最長公共子串

　　Problem5一元一次方程的解

　　Problem6多項(xiàng)式乘法

　　一、 貪心算法

　　Problem1刪數(shù)問題

　　題目描述：

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

　　輸入

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

　　輸出

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

　　Problem2旅行家的預(yù)算

　　題目描述

　　一個(gè)旅行家想駕駛汽車以最少的費(fèi)用從一個(gè)城市到另一個(gè)城市（假設(shè)出發(fā)時(shí)油箱是空的）。給定兩個(gè)城市之間的距離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個(gè)數(shù)：D1，c，D2，P，N(前四個(gè)為實(shí)數(shù)，N為整數(shù),N<=1000)

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

　　輸出

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

　　Problem3線段覆蓋

　　題目描述

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

　　輸入

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

　　輸出

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

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

　　Problem4背包問題

　　題目描述

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

　　輸入

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

　　輸出

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

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

　　題目描述

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

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

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

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

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

　　輸入

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

　　輸出

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

　　Problem6果子合并

　　題目描述

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

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

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