NOIP提高組 1999 & 2000 題解合集

【序言】話說我在學神奇算法的時候，基礎應該也要鞏固，于是打算提前把noip提高組的刷完。

具體的題目描述和送出我就在vijos上完成。

【1999.1】

給定一個信封，最多隻允許粘貼n張郵票，計算在給定m（n+m<=10）種郵票的情況下（假定所有的郵票數量都足夠）,如何設計郵票的面值，能得到最大max ，使得1～max之間的每一個郵資值都能得到。

例如，n=3，m＝2，如果面值分别為1分、4分，則在l分～6分之間的每一個郵資值都能得到（當然還有8分、9分和12分）：如果面值分别為1分、3分，則在1分～7分之間的每一個郵資值都能得到。可以驗證當n=3，m＝2時，7分就是可以得到連續的郵資最大值，是以max=7，面值分别為l分、3分。

樣例輸入：共一行，兩個整數，分表為n與m的值。

一行，分别為n,m。

兩行。

第一行為m種郵票的面值，按升序排列，各數之間用一個空格隔開。

第二行為最大值。

如果有多解，輸出字典序最大的一個。

各個測試點1s

noip1999

【分析】似乎很早很早以前做到過~那時候因為不太懂各種算法，就亂搞搞過去了。但是現在思維複雜起來了，時間效率考慮的太多，反而難以下手。開始想的是貪心，發現是有問題的。資料範圍n+m<=10，那麼我們果斷爆搜。在爆搜的途中如何随時更新值？隻能用背包了。1a。

【代碼】

【1999.2】

一個旅行家想駕駛汽車以最少的費用從一個城市到另一個城市(假設出發時油箱是空的)。給定兩個城市之間的距離d1、汽車油箱的容量c（以升為機關）、每升汽油能行駛的距離d2、出發點每升汽油價格p和沿途油站數n，油站i離出發點的距離d[i]、每升汽油價格p[i]。

計算結果四舍五入至小數點後兩位。

如果無法到達目的地，則輸出-1。

輸入共n+1行，第一行為d1,c,d2,p,n，以下n行，每行兩個資料，分别表示該油站距出發點的距離d[i]和該油站每升汽油的價格p[i]。兩個資料之間用一個空格隔開。

1 <= n <= 100

1s

0<=n<=100

【分析】開始還以為是dp，仔細一想是貪心。因為細節沒處理好，後來還下載下傳資料調試= =。

政策：主要是采用搜尋的架構（但是其實不是，每層隻有一個點在操作）設目前到達的點是k。

①對于k能到的點中，找到第一個油費比k小的點p。若能找到，跳到②；否則跳到⑤。

②加上剛好去p的油，累加答案，并來到p這個狀态。跳到①。

③說明在能到達的點中，k的油費最小。跳到④。

④判斷k能否直接到達終點，若能累加答案并退出，否則跳到⑤。

⑤找到k能到達的點中油費最小的點，同時加滿油駛向p。若已經沒有點了，輸出-1，否則跳到①。

但是很遺憾，還有一個小的問題：我們還要記錄一下目前所剩的油量q。以上過程都要涉及q。

1999的其它兩題就不必說了吧~~~

【2000.1】

jerryzhou同學經常改編習題給自己做。

這天，他又改編了一題。。。。。

設有n*n的方格圖，我們将其中的某些方格填入正整數，

而其他的方格中放入0。

某人從圖得左上角出發，可以向下走，也可以向右走，直到到達右下角。

在走過的路上，他取走了方格中的數。（取走後方格中數字變為0）

此人從左上角到右下角共走3次，試找出3條路徑，使得取得的數總和最大。

第一行:n (4<=n<=20)

接下來一個n*n的矩陣，矩陣中每個元素不超過80，不小于0

一行，表示最大的總和。

多程序dp

【分析】其實原題是二取方格數，不過這樣更加可以練練手。dp的方法應該很熟練了，我就寫了些網絡流。太高興了，建圖自己就yy出來了。設超級源點s，與左上角連一條費用為0，流量為3的邊；設超級彙點t，與右下角連一條同樣的邊。能到達的兩點連一條流量為inf，費用為0的邊。然後把每個點拆成兩個，連一條流量為inf，費用為0的邊和一條流量為1，費用為權值的邊。流量的意義是路徑，費用的意義是價值。然後跑一遍最大費用最大流。

【2000.2】

單詞接龍是一個與我們經常玩的成語接龍相類似的遊戲，現在我們已知一組單詞，且給定一個開頭的字母，要求出以這個字母開頭的最長的“龍”（每個單詞都最多在“龍”中出現兩次），在兩個單詞相連時，其重合部分合為一部分，例如 beast和astonish，如果接成一條龍則變為beastonish，另外相鄰的兩部分不能存在包含關系，例如at 和 atide 間不能相連。

輸入的第一行為一個單獨的整數n (n<=20)表示單詞數，以下n 行每行有一個單詞，輸入的最後一行為一個單個字元，表示“龍”開頭的字母。你可以假定以此字母開頭的“龍”一定存在.

隻需輸出以此字母開頭的最長的“龍”的長度

連成的“龍”為atoucheatactactouchoose

noip2000提高組第3題

【分析】開始還以為是dp，用f[i][j]表示連接配接了i個單詞，且最後一個是j的最大長度，後來發現無法獲知每個單詞是否用過（狀壓dp?）。想了一會了，n<=20,果斷搜尋。先預處理兩兩單詞的關系，然後爆搜~。1a。

【2000.3】

noip2000 提高組第一題

我們可以用這樣的方式來表示一個十進制數：将每個阿拉伯數字乘以一個以該數字所處位置的（值減1）為指數，以10為底數的幂之和的形式。例如，123可表示為1*10^2+2*10^1+3*10^0這樣的形式。

與之相似的，對二進制數來說，也可表示成每個二進制數位乘以一個以該數字所處位置的（值-1）為指數，以2為底數的幂之和的形式。一般說來，任何一個正整數r或一個負整數-r都可以被選來作為一個數制系統的基數。如果是以r或-r為基數，則需要用到的數位為0，1,....r-1。例如，當r=7時，所需用到的數位是0，1，2, 3，4，5和6，這與其是r或-r無關。如果作為基數的數絕對值超過10，則為了表示這些數位，通常使用英文字母來表示那些大于9的數位。例如對16進制數來說，用a表示10，用b表示11，用c表示12，用d表示13，用e表示14，用f表示15。在負進制數中是用-r作為基數，例如-15（＋進制）相當于110001（-2進制），

并且它可以被表示為2的幂級數的和數：

110001=1*(-2)^5+1*(-2)^4+0*(-2)^3+0*(-2)^2+0*(-2)^1+1*(-2)^0

問題求解:

設計一個程式，讀入一個十進制數的基數和一個負進制數的基數，并将此十進制數轉換為此負進制下的數：-r∈{-2，-3，-4,....-20}

輸入檔案有若幹行，每行有兩個輸入資料。

第一個是十進制數n（-32768<=n<=32767）; 第二個是負進制數的基數-r。

輸出此負進制數及其基數，若此基數超過10，則參照16進制的方式處理。【具體請參考樣例】

每個點1s。

每個測試資料不超過1000組。

from 瑪維-影之歌

noip2000原題

【分析】說來慚愧，開始想的太複雜了=_=。當進制是負數時該怎麼處理？開始想是枚舉答案的位數，然後一步步的逼近~~真是麻煩。後來一拍腦袋，不是可以直接除嗎？負數應該也滿足整數的性質，隻是除的時候要特判。1a。