第 1 頁 *** 7 頁
全國信息學奧林匹克聯賽（NOIP2010）復賽
提高組（請選手務必仔細閱讀本頁內容）
壹．題目概況
中文題目名稱 機器翻譯 烏龜棋 關押罪犯 引水入城
英文題目與子目錄名 translate tortoise prison flow
可執行文件名 translate tortoise prison flow
輸入文件名 translate.in tortoise.in prison.in flow.in
輸出文件名 translate.out tortoise.out prison.out flow.out
每個測試點時限 1秒 1秒 1秒 1秒
測試點數目 10 10 10 10
每個測試點分值 10 10 10 10
附加樣例文件 有 有 有 有
結果比較方式 全文比較（過濾行末空格及文末回車）
題目類型 傳統 傳統 傳統 傳統
二．提交源程序文件名
對於pascal語言 translate.pas tortoise.pas prison.pas flow.pas
對於C語言 translate.c tortoise.c prison.c flow.c
對於C++語言 translate.cpp tortoise.cpp prison.cpp flow.cpp
三．編譯命令（不包含任何優化開關）
對於pascal語言 fpc translate.pasfpc tortoise.pasfpc prison.pas fpc flow.pas
對於C語言
gcc -o translate
translate.c -lm
gcc -o tortoise
tortoise.c -lm
gcc -o prison
prison.c -lm
gcc -o flow
flow.c -lm
對於C++語言 g++ -o translate
translate.cpp -lm
g++ -o tortoise
tortoise.cpp -lm
g++ -o prison
prison.cpp -lm
g++ -o flow
flow.cpp -lm
四．運行內存限制內存上限 128M 128M 128M 128M
註意事項：
1、文件名（程序名和輸入輸出文件名）必須使用英文小寫。
2、C/C++中函數main()的返回值類型必須是int，程序正常結束時的返回值必須是0。
3、全國統壹評測時采用的機器配置為：CPU P4 3.0GHz，內存1G，上述時限以此配置為準。
各省在自測時可根據具體配置調整時限。
換頁
全國信息學奧林匹克聯賽（NOIP2010）復賽 提高組
第 2 頁 *** 7 頁
1．機器翻譯
(translate.pas/c/cpp)
問題描述
小晨的電腦上安裝了壹個機器翻譯軟件，他經常用這個軟件來翻譯英語文章。
這個翻譯軟件的原理很簡單，它只是從頭到尾，依次將每個英文單詞用對應的中文含義
來替換。對於每個英文單詞，軟件會先在內存中查找這個單詞的中文含義，如果內存中有，
軟件就會用它進行翻譯；如果內存中沒有，軟件就會在外存中的詞典內查找，查出單詞的中
文含義然後翻譯，並將這個單詞和譯義放入內存，以備後續的查找和翻譯。
假設內存中有M個單元，每單元能存放壹個單詞和譯義。每當軟件將壹個新單詞存入
內存前，如果當前內存中已存入的單詞數不超過M?1，軟件會將新單詞存入壹個未使用的
內存單元；若內存中已存入M個單詞，軟件會清空最早進入內存的那個單詞，騰出單元來，
存放新單詞。
假設壹篇英語文章的長度為N個單詞。給定這篇待譯文章，翻譯軟件需要去外存查找多
少次詞典？假設在翻譯開始前，內存中沒有任何單詞。
輸入
輸入文件名為translate.in，輸入文件***2行。每行中兩個數之間用壹個空格隔開。
第壹行為兩個正整數M和N，代表內存容量和文章的長度。
第二行為N個非負整數，按照文章的順序，每個數（大小不超過1000）代表壹個英文
單詞。文章中兩個單詞是同壹個單詞，當且僅當它們對應的非負整數相同。
輸出輸出文件translate.out***1行，包含壹個整數，為軟件需要查詞典的次數。
輸入輸出樣例1
translate.in translate.out
3 7
1 2 1 5 4 4 1
5
輸入輸出樣例1說明
整個查字典過程如下：每行表示壹個單詞的翻譯，冒號前為本次翻譯後的內存狀況：
空：內存初始狀態為空。
1． 1：查找單詞1並調入內存。
2． 1 2：查找單詞2並調入內存。
3． 1 2：在內存中找到單詞1。
4． 1 2 5：查找單詞5並調入內存。
5． 2 5 4：查找單詞4並調入內存替代單詞1。
6． 2 5 4：在內存中找到單詞4。
7． 5 4 1：查找單詞1並調入內存替代單詞2。
***計查了5次詞典。
換頁
全國信息學奧林匹克聯賽（NOIP2010）復賽 提高組
第 3 頁 *** 7 頁
輸入輸出樣例2
translate.in translate.out
2 10
8 824 11 78 11 78 11 78 8 264
6
數據範圍
對於10%的數據有M=1，N≤5。
對於100%的數據有0≤100，0≤1000。
2．烏龜棋
(tortoise.pas/c/cpp)
問題描述
小明過生日的時候，爸爸送給他壹副烏龜棋當作禮物。
烏龜棋的棋盤是壹行N個格子，每個格子上壹個分數（非負整數）。棋盤第1格是唯壹
的起點，第N格是終點，遊戲要求玩家控制壹個烏龜棋子從起點出發走到終點。
……
1 2 3 4 5 ……N
烏龜棋中M張爬行卡片，分成4種不同的類型（M張卡片中不壹定包含所有4種類型
的卡片，見樣例），每種類型的卡片上分別標有1、2、3、4四個數字之壹，表示使用這種卡
片後，烏龜棋子將向前爬行相應的格子數。遊戲中，玩家每次需要從所有的爬行卡片中選擇
壹張之前沒有使用過的爬行卡片，控制烏龜棋子前進相應的格子數，每張卡片只能使用壹次。
遊戲中，烏龜棋子自動獲得起點格子的分數，並且在後續的爬行中每到達壹個格子，就得到
該格子相應的分數。玩家最終遊戲得分就是烏龜棋子從起點到終點過程中到過的所有格子的
分數總和。
很明顯，用不同的爬行卡片使用順序會使得最終遊戲的得分不同，小明想要找到壹種卡
片使用順序使得最終遊戲得分最多。
現在，告訴妳棋盤上每個格子的分數和所有的爬行卡片，妳能告訴小明，他最多能得到
多少分嗎？
輸入
輸入文件名tortoise.in。輸入文件的每行中兩個數之間用壹個空格隔開。
第1行2個正整數N和M，分別表示棋盤格子數和爬行卡片數。
第2行N個非負整數，a1a2
……aN
，其中ai表示棋盤第i個格子上的分數。第3行M個整數，b1b2
……bM
，表示M張爬行卡片上的數字。
輸入數據保證到達終點時剛好用光M張爬行卡片，即N?1=∑
M
ib
1
輸出
輸出文件名tortoise.out。
換頁
全國信息學奧林匹克聯賽（NOIP2010）復賽 提高組
第 4 頁 *** 7 頁
輸出只有1行，1個整數，表示小明最多能得到的分數。
輸入輸出樣例1
tortoise.in tortoise.out
9 5
6 10 14 2 8 8 18 5 17
1 3 1 2 1
73
輸入輸出樣例1說明
小明使用爬行卡片順序為1，1，3，1，2，得到的分數為6+10+14+8+18+17=73。註意，
由於起點是1，所以自動獲得第1格的分數6。
輸入輸出樣例2
tortoise.in tortoise.out
13 8
4 96 10 64 55 13 94 53 5 24 89 8 30
1 1 1 1 1 2 4 1
455
數據範圍
對於30%的數據有1
≤
N
≤
30，1
≤
M
≤
12。
對於50%的數據有1≤N≤120，1
≤
M
≤
50，且4種爬行卡片，每種卡片的張數不會超
過20。
對於100%的數據有1≤N≤350，1≤M≤120，且4種爬行卡片，每種卡片的張數不會
超過40；0≤ai≤100，1≤i≤N；1≤bi≤4，1≤i≤M。輸入數據保證N?1=
∑
M
ib
1
3．關押罪犯
(prison.pas/c/cpp)
問題描述
S城現有兩座監獄，壹***關押著N名罪犯，編號分別為1~N。他們之間的關系自然也極
不和諧。很多罪犯之間甚至積怨已久，如果客觀條件具備則隨時可能爆發沖突。我們用“怨
氣值”（壹個正整數值）來表示某兩名罪犯之間的仇恨程度，怨氣值越大，則這兩名罪犯之
間的積怨越多。如果兩名怨氣值為c的罪犯被關押在同壹監獄，他們倆之間會發生摩擦，並
造成影響力為c的沖突事件。
每年年末，警察局會將本年內監獄中的所有沖突事件按影響力從大到小排成壹個列表，
然後上報到S城Z市長那裏。公務繁忙的Z市長只會去看列表中的第壹個事件的影響力，
如果影響很壞，他就會考慮撤換警察局長。
在詳細考察了N名罪犯間的矛盾關系後，警察局長覺得壓力巨大。他準備將罪犯們在
兩座監獄內重新分配，以求產生的沖突事件影響力都較小，從而保住自己的烏紗帽。假設只
要處於同壹監獄內的某兩個罪犯間有仇恨，那麽他們壹定會在每年的某個時候發生摩擦。那
麽，應如何分配罪犯，才能使Z市長看到的那個沖突事件的影響力最小？這個最小值是多
換頁
全國信息學奧林匹克聯賽（NOIP2010）復賽 提高組
第 5 頁 *** 7 頁
少？
輸入
輸入文件名為prison.in。輸入文件的每行中兩個數之間用壹個空格隔開。
第壹行為兩個正整數N和M，分別表示罪犯的數目以及存在仇恨的罪犯對數。
接下來的M行每行為三個正整數aj，bj，cj，表示aj號和bj號罪犯之間存在仇恨，其怨
氣值為cj。數據保證Nba
jj
≤1，0000000001
0≤
jc
，且每對罪犯組合只出現壹
次。
輸出
輸出文件prison.out***1行，為Z市長看到的那個沖突事件的影響力。如果本年內監獄
中未發生任何沖突事件，請輸出0。
輸入輸出樣例
prison.in prison.out
4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884
3512
輸入輸出樣例說明
罪犯之間的怨氣值如下面左圖所示，右圖所示為罪犯的分配方法，市長看到的沖突事件
影響力是3512（由2號和3號罪犯引發）。其他任何分法都不會比這個分法更優。
數據範圍
對於30%的數據有N≤15。
對於70%的數據有N≤2000，M≤50000。
對於100%的數據有N≤20000，M≤100000。
2 1
3 4
1805 6618
2534 3512
12884
28351 2 1
3 4
2534 3512
換頁
全國信息學奧林匹克聯賽（NOIP2010）復賽 提高組
第 6 頁 *** 7 頁
4.引水入城
(flow.pas/c/cpp)
問題描述
湖泊
沙漠
在壹個遙遠的國度，壹側是風景秀美的湖泊，另壹側則是漫無邊際的沙漠。該國的行政
區劃十分特殊，剛好構成壹個N行M列的矩形，如上圖所示，其中每個格子都代表壹座城
市，每座城市都有壹個海拔高度。
為了使居民們都盡可能飲用到清澈的湖水，現在要在某些城市建造水利設施。水利設施
有兩種，分別為蓄水廠和輸水站。蓄水廠的功能是利用水泵將湖泊中的水抽取到所在城市的
蓄水池中。因此，只有與湖泊毗鄰的第1行的城市可以建造蓄水廠。而輸水站的功能則是通
過輸水管線利用高度落差，將湖水從高處向低處輸送。故壹座城市能建造輸水站的前提，是
存在比它海拔更高且擁有公***邊的相鄰城市，已經建有水利設施。
由於第N行的城市靠近沙漠，是該國的幹旱區，所以要求其中的每座城市都建有水利
設施。那麽，這個要求能否滿足呢？如果能，請計算最少建造幾個蓄水廠；如果不能，求幹
旱區中不可能建有水利設施的城市數目。
輸入
輸入文件名為flow.in。輸入文件的每行中兩個數之間用壹個空格隔開。
輸入的第壹行是兩個正整數N和M，表示矩形的規模。
接下來N行，每行M個正整數，依次代表每座城市的海拔高度。
輸出
輸出文件名為flow.out。
輸出有兩行。如果能滿足要求，輸出的第壹行是整數1，第二行是壹個整數，代表最少
建造幾個蓄水廠；如果不能滿足要求，輸出的第壹行是整數0，第二行是壹個整數，代表有
幾座幹旱區中的城市不可能建有水利設施。
輸入輸出樣例1
flow.in flow.out
2 5
9 1 5 4 3
8 7 6 1 2
11
換頁
全國信息學奧林匹克聯賽（NOIP2010）復賽 提高組
第 7 頁 *** 7 頁
樣例1說明
只需要在海拔為9的那座城市中建造蓄水廠，即可滿足要求。
輸入輸出樣例2
flow.in flow.out
3 6
8 4 5 6 4 4
7 3 4 3 3 3
3 2 2 1 1 2
13
樣例2說明
湖泊
8 4 5 6 4 4
7 3 4 3 3 3
3 2 2 1 1 2
沙漠
上圖中，在3個粗線框出的城市中建造蓄水廠，可以滿足要求。以這3個蓄水廠為源頭
在幹旱區中建造的輸水站分別用3種顏色標出。當然，建造方法可能不唯壹。
數據範圍
本題***有10個測試數據，每個數據的範圍如下表所示：
測試數據編號 能否滿足要求 N M
1 不能 ≤ 10 ≤ 10
2 不能 ≤ 100 ≤ 100
3 不能 ≤ 500 ≤ 500
4 能 = 1 ≤ 10
5 能 ≤ 10 ≤ 10
6 能 ≤ 100 ≤ 20
7 能 ≤ 100 ≤ 50
8 能 ≤ 100 ≤ 100
9 能 ≤ 200 ≤ 200
10 能 ≤ 500 ≤ 500
對於所有的10個數據，每座城市的海拔高度都不超過10
6
換頁