信息學聯賽知識：基本程序題集

基本程序題集

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

　　題集目錄

　　一、貪心算法

　　Problem1刪數問題

　　Problem2旅行家的預算

　　Problem3線段覆蓋

　　Problem4背包問題

　　Problem5任務調度

　　Problem6果子合并

　　Problem7射擊競賽

　　Problem8任務安排

　　Problem9最小差距

　　二、 分治算法

　　Problem1一元三次方程的解

　　Problem2查找第k大元素

　　Problem3麥森數

　　Problem4逆序對個數

　　Problem5尋找最近點對

　　Problem6剔除多余括號

　　Problem7賽程安排

　　三、 搜索算法

　　Problem1皇后問題

　　Problem2八數碼問題

　　Problem3拼圖

　　Problem4質數方陣

　　Problem5埃及分數

　　Problem6字符串變換

　　Problem7聰明的打字員

　　Problem8 01序列

　　Problem9生日蛋糕

　　四、 圖論算法

　　Problem1一筆畫問題

　　Problem2 Car的旅行路線

　　Problem3求割點與橋

　　Problem4十字繡

　　Problem5舞會

　　Problem6休息中的小呆

　　Problem7最優布線問題

　　Problem8磁盤碎片整理

　　Problem9說謊島

　　Problem10 01串問題

　　Problem11海島地圖

　　五、 數學問題

　　Problem1數的劃分

　　Problem2最優分解方案

　　Problem3出棧序列統計

　　Problem4百事世界杯之旅

　　Problem5電子鎖

　　Problem6堆塔問題

　　Problem7取數游戲

　　Problem8球迷購票

　　Problem9 Fibonacci公約數

　　Problem10傳球問題

　　Problem11約瑟夫問題

　　Problem12青蛙過河

　　Problem13棋盤游戲

　　六、 數據結構

　　Problem1火車棧

　　Problem2括號表達式

　　Problem3銀河英雄傳說

　　Problem4矩形覆蓋

　　Problem5最短路徑問題

　　Problem6果子合并

　　七、 字符串處理

　　Problem1相對分子質量

　　Problem2表達式求值

　　Problem3偵探推理

　　Problem4最長公共子串

　　Problem5一元一次方程的解

　　Problem6多項式乘法

　　一、 貪心算法

　　Problem1刪數問題

　　題目描述：

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

　　輸入

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

　　輸出

　　輸出一行，即最小的那個數

　　Problem2旅行家的預算

　　題目描述

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

　　輸入

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

　　后面有N行，每行兩個實數，分別表示對應的加油站離出發點的距離，與每升汽油的價格

　　輸出

　　輸出僅一行，即最少花費

　　Problem3線段覆蓋

　　題目描述

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

　　輸入

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

　　輸出

　　輸出第一行為最少刪除的線段數s

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

　　Problem4背包問題

　　題目描述

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

　　輸入

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

　　輸出

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

　　Problem5任務調度

　　題目描述

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

　　1.包含n個單位時間任務的集合S={1,2,……,n};

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

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

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

　　輸入

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

　　輸出

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

　　Problem6果子合并

　　題目描述

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

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

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

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