NOIP2015復(fù)賽普及組試題

1、CCF 全國信息學(xué)奧林匹克聯(lián)賽（NOIP2015）復(fù)賽 普及組 （請選手務(wù)必認真閱讀本頁內(nèi)容） 一題目概況 中文題目名稱 金幣 掃雷玩耍 求和 推銷員 英文題目與子名目名 coin mine sum salesman 可執(zhí)行文件名 coin mine sum salesman 輸入文件名 coin.in mine.in sum.in salesman.in 輸出文件名 coin.out mine.out sum.out salesman.out 每個測試點時限 1 秒 1 秒 1 秒 1 秒 測試點數(shù)目 10 10 10 10 每個測試點分值 10 10 10 10 附加樣例文件 有 有 有

2、有 結(jié)果比較方式 全文比較（過濾行末空格及文末回車） 題目類型 傳統(tǒng) 傳統(tǒng) 傳統(tǒng) 傳統(tǒng) 運行內(nèi)存上限 128M 128M 128M 128M 二提交源程序文件名 對于 C+語言 coin.cpp mine.cpp sum.cpp salesman.cpp 對于 C 語言 coin.c mine.c sum.c salesman.c 對于 pascal 語言 coin.pas mine.pas sum.pas salesman.pas 三編譯命令（不包含任何優(yōu)化開關(guān)） 對于 C+語言 g+ -o coin coin.cpp -lm g+ -o mine mine.cpp -lm g+ -o su

3、m sum.cpp -lm g+ -o salesman salesman.cpp -lm 對于 C 語言 gcc -o coin coin.c -lm gcc -o mine mine.c -lm gcc -o sum sum.c -lm gcc -o salesman salesman.c -lm 對于 pascal 語言 fpc coin.pas fpc mine.pas fpc sum.pas fpc salesman.pas 留意事項： 1、 文件名（程序名和輸入輸出文件名）必需使用英文小寫。 2、 C/C+中函數(shù) main()的返回值類型必需是 int，程序正常結(jié)束時的返回值必需是

4、 0。 3、 全國統(tǒng)一評測時接受的機器配置為：CPU AMD Athlon(tm) II x2 240 processor，2.8GHz，內(nèi)存 4G，上述時限以此配置為準。 4、 只供應(yīng) Linux 格式附加樣例文件。 5、 特殊提示：評測在當前最新公布的 NOI Linux 下進行，各語言的編譯器版本以其為準。 1. 金幣 (coin.cpp/c/pas) 國王將金幣作為工資，發(fā)放給忠誠的騎士。第一天，騎士收到一枚金幣；之后兩天（其次天和第三天），每天收到兩枚金幣；之后三天（第四、五、六天），每天收到三枚金幣；之后四天（第七、八、九、十天），每天收到四枚金幣；這種工資發(fā)放模式會始終這樣連續(xù)下

5、去：當連續(xù) N 天每天收到 N 枚金幣后，騎士會在之后的連續(xù) N+1 天里，每天收到 N+1 枚金幣。 請計算在前 K 天里，騎士一共獲得了多少金幣。 【輸入格式】 輸入文件名為 coin.in。 輸入文件只有 1 行，包含一個正整數(shù) K，表示發(fā)放金幣的天數(shù)。 【輸出格式】 輸出文件名為 coin.out。 輸出文件只有 1 行，包含一個正整數(shù)，即騎士收到的金幣數(shù)。 【輸入輸出樣例 1】 coin.in coin.out 6 14 見選手名目下的 coin/coin1.in 和 coin/coin1.ans。 【輸入輸出樣例 1 說明】 騎士第一天收到一枚金幣；其次天和第三天，每天收到兩枚金幣

6、；第四、五、六天，每天收到三枚金幣。因此一共收到 1+2+2+3+3+3=14 枚金幣。 【輸入輸出樣例 2】 coin.in coin.out 1000 29820 見選手名目下的 coin/coin2.in 和 coin/coin2.ans。 【數(shù)據(jù)說明】 對于 100%的數(shù)據(jù)，1 K 10,000。 2. 掃雷玩耍 （mine.cpp/c/pas） 掃雷玩耍是一款格外經(jīng)典的單機小玩耍。在 n 行 m 列的雷區(qū)中有一些格子含有地雷（稱之為地雷格），其他格子不含地雷（稱之為非地雷格）。玩家翻開一個非地雷格時，該格將會消滅一個數(shù)字提示四周格子中有多少個是地雷格。玩耍的目標是在不翻出任何地雷格的

7、條件下，找出全部的非地雷格。 現(xiàn)在給出n行m列的雷區(qū)中的地雷分布，要求計算出每個非地雷格四周的地雷格數(shù)。 注：一個格子的四周格子包括其上、下、左、右、左上、右上、左下、右下八個方向上與之直接相鄰的格子。 【輸入格式】 輸入文件名為 mine.in。 輸入文件第一行是用一個空格隔開的兩個整數(shù)n和m，分別表示雷區(qū)的行數(shù)和列數(shù)。 接下來 n 行，每行 m 個字符，描述了雷區(qū)中的地雷分布狀況。字符*表示相應(yīng)格子是地雷格，字符?表示相應(yīng)格子是非地雷格。相鄰字符之間無分隔符。 【輸出格式】 輸出文件名為 mine.out。 輸出文件包含 n 行，每行 m 個字符，描述整個雷區(qū)。用*表示地雷格，用四周的地雷

8、個數(shù)表示非地雷格。相鄰字符之間無分隔符。 【輸入輸出樣例 1】 mine.in mine.out 3 3 *? ? ?*? *10 221 1*1 見選手名目下的 mine/mine1.in 和 mine/mine1.ans。 【輸入輸出樣例 2】 mine.in mine.out 2 3 ?*? *? 2*1 *21 見選手名目下的 mine/mine2.in 和 mine/mine2.ans。 【輸入輸出樣例 3】 見選手名目下的 mine/mine3.in 和 mine/mine3.ans。 【數(shù)據(jù)說明】 對于 100%的數(shù)據(jù)，1n100，1m100。 3. 求和 (sum.cpp/c/

9、pas) 一條狹長的紙帶被均勻劃分出了 n 個格子，格子編號從 1 到 n。每個格子上都染了一種顏色𝑐𝑜𝑙𝑜𝑟𝑖（用1，m當中的一個整數(shù)表示），并且寫了一個數(shù)字𝑛𝑢𝑚𝑏𝑒𝑟𝑖。 5 5 3 2 2 2 1 2 3 4 5 6 編號 定義一種特殊的三元組：(x, y, z)，其中 x，y，z 都代表紙帶上格子的編號，這里的三元組要求滿足以下兩個條件： 1. 𝑥, ү

10、10;, 𝑧都是整數(shù), 𝑥 < 𝑦 < 𝑧, 𝑦 𝑥 = 𝑧 𝑦 2. 𝑐𝑜𝑙𝑜𝑟𝑥 = 𝑐𝑜𝑙𝑜𝑟𝑧 滿足上述條件的三元組的分數(shù)規(guī)定為(x + z) (𝑛𝑢𝑚𝑏𝑒𝑟

11、19909; + 𝑛𝑢𝑚𝑏𝑒𝑟𝑧)。整個紙帶的分數(shù)規(guī)定為全部滿足條件的三元組的分數(shù)的和。這個分數(shù)可能會很大，你只要輸出整個紙帶的分數(shù)除以 10,007 所得的余數(shù)即可。 【輸入格式】 輸入文件名為 sum.in。 第一行是用一個空格隔開的兩個正整數(shù)𝑛和𝑚，𝑛代表紙帶上格子的個數(shù)，𝑚代表紙帶上顏色的種類數(shù)。 其次行有𝑛個用空格隔開的正整數(shù)，第𝑖個數(shù)字𝑛𝑢

12、19898;𝑏𝑒𝑟𝑖代表紙帶上編號為𝑖的格子上面寫的數(shù)字。 第三行有𝑛個用空格隔開的正整數(shù)，第𝑖個數(shù)字𝑐𝑜𝑙𝑜𝑟𝑖代表紙帶上編號為𝑖的格子染的顏色。 【輸出格式】 輸出文件名為 sum.out。 共一行，一個整數(shù)，表示所求的紙帶分數(shù)除以 10,007 所得的余數(shù)。 【輸入輸出樣例 1】 sum.in sum.out 6 2 5 5 3 2 2 2 2 2 1 1 2 1 8

13、2 見選手名目下的 sum/sum1.in 和 sum/sum1.ans。 【輸入輸出樣例 1 說明】 紙帶如題目描述中的圖所示。 全部滿足條件的三元組為：(1,3, 5), (4, 5, 6)。 所以紙帶的分數(shù)為(1 + 5) (5 + 2) + (4 + 6) (2 + 2) = 42 + 40 = 82。 歡迎下載【輸入輸出樣例 2】 sum.in sum.out 15 4 5 10 8 2 2 2 9 9 7 7 5 6 4 2 4 2 2 3 3 4 3 3 2 4 4 4 4 1 1 1 1388 見選手名目下的 sum/sum2.in 和 sum/sum2.ans。 【輸入輸出樣

14、例 3】見選手名目下的 sum/sum3.in 和 sum/sum3.ans。 【數(shù)據(jù)說明】對于第 1 組至第 2 組數(shù)據(jù)，1 𝑛 100, 1 𝑚 5； 對于第 3 組至第 4 組數(shù)據(jù)，1 𝑛 3000, 1 𝑚 100； 對于第 5 組至第 6 組數(shù)據(jù)，1 𝑛 100000, 1 𝑚 100000，且不存在消滅次數(shù)超過 20 的顏色； 對于全部 10 組數(shù)據(jù)， 1 𝑛 100000, 1 𝑚 100000, 1 𝑐𝑜𝑙

15、;𝑜𝑟𝑖 𝑚, 1 𝑛𝑢𝑚𝑏𝑒𝑟𝑖 100000。 4. 推銷員 (salesman.cpp/c/pas) 【問題描述】 阿明是一名推銷員，他奉命到螺絲街推銷他們公司的產(chǎn)品。螺絲街是一條死胡同，出口與入口是同一個，街道的一側(cè)是圍墻，另一側(cè)是住戶。螺絲街一共有 N 家住戶，第 i 家住戶到入口的距離為 Si 米。由于同一棟房子里可以有多家住戶，所以可能有多家住戶與入口的距離相等。阿明會從入口進入，依次向螺絲街的 X 家住戶

16、推銷產(chǎn)品，然后再原路走出去。 阿明每走 1 米就會積累 1 點疲憊值，向第 i 家住戶推銷產(chǎn)品會積累 Ai 點疲憊值。阿明是工作狂，他想知道，對于不同的 X，在不走多余的路的前提下，他最多可以積累多少點疲憊值。 【輸入格式】 輸入文件名為 salesman.in。 第一行有一個正整數(shù) N，表示螺絲街住戶的數(shù)量。 接下來的一行有 N 個正整數(shù)，其中第 i 個整數(shù) Si 表示第 i 家住戶到入口的距離。數(shù)據(jù)保證 S1S2Sn<108。 接下來的一行有 N 個正整數(shù)，其中第 i 個整數(shù) Ai 表示向第 i 戶住戶推銷產(chǎn)品會積累的疲憊值。數(shù)據(jù)保證 Ai<103。 【輸出格式】 輸出文件名為

17、 salesman.out。 輸出 N 行，每行一個正整數(shù)，第 i 行整數(shù)表示當 X=i 時，阿明最多積累的疲憊值。 【輸入輸出樣例 1】 salesman.in salesman.out 5 1 2 3 4 5 1 2 3 4 5 15 19 22 24 25 見選手名目下的 salesman/salesman1.in 和 salesman/salesman1.ans。 【輸入輸出樣例 1 說明】 X=1: 向住戶 5 推銷，來回走路的疲憊值為 5+5，推銷的疲憊值為 5，總疲憊值為15。 X=2: 向住戶 4、5 推銷，來回走路的疲憊值為 5+5，推銷的疲憊值為 4+5，總疲憊值為 5+5

18、+4+5=19。 X=3: 向住戶 3、4、5 推銷，來回走路的疲憊值為 5+5，推銷的疲憊值 3+4+5，總疲憊值為 5+5+3+4+5=22。 X=4: 向住戶 2、3、4、5 推銷，來回走路的疲憊值為 5+5，推銷的疲憊值 2+3+4+5，總疲憊值 5+5+2+3+4+5=24。 X=5: 向住戶 1、2、3、4、5 推銷，來回走路的疲憊值為 5+5，推銷的疲憊值 1+2+3+4+5，總疲憊值 5+5+1+2+3+4+5=25。 【輸入輸出樣例 2】 salesman.in salesman.out 5 1 2 2 4 5 5 4 3 4 1 12 17 21 24 27 見選手名目下的 salesman/salesman2.in 和 salesman/salesman2.ans。 【輸入輸出樣例 2 說明】 X=1：向住戶 4 推銷，來回走路的疲憊值為 4+4，推銷的疲憊值為 4，總疲憊值 4+4+4=12。 X=2：向住戶 1、4 推銷，來回走路的疲憊值為 4+4，推銷的疲憊值為 5+4，總疲憊值4+4+5+4=17。 X=3：向住戶 1、2、4 推銷，來回走路的疲憊值為 4+4，推銷的疲憊值為 5+4+4，總疲憊值 4+4+5+4+4=21。 X=4：向住戶 1、2、3、4 推銷，來回走路的疲憊值為 4+4，推銷的疲憊值為 5+4+3+4，總疲憊值 4+4+5+4+3