noip2017提高組試題day1day2 Word版

1、CCF 全國信息學奧林匹克聯(lián)賽（NOIP2017）復賽提高組 day1（請選手務必仔細閱讀本頁內(nèi)容）一題目概況中文題目名稱小凱的疑惑時間復雜度逛公園英文題目與子目錄名mathcomplexitypark可執(zhí)行文件名mathcomplexitypark輸入文件名math.incomplexity.inpark.in輸出文件名math.outcomplexity.outpark.out每個測試點時限1 秒1 秒3 秒測試點數(shù)目201010每個測試點分值51010附加樣例文件有有有結(jié)果比較方式全文比較（過濾行末空格及文末回車）題目類型傳統(tǒng)傳統(tǒng)傳統(tǒng)運行內(nèi)存上限256M256M512M二提交源程序文件名

2、對于 C+語言math.cppcomplexity.cpppark.cpp對于 C 語言math.ccomplexity.cpark.c對于 pascal 語言math.pascomplexity.paspark.pas三編譯命令（不包含任何優(yōu)化開關(guān)）對于 C+語言g+ -o mathmath.cpp -lmg+ -o complexitycomplexity.cpp -lmg+ -o parkpark.cpp -lm對于 C 語言gcc -o math math.c-lmgcc -o complexitycomplexity.c -lmgcc -o park park.c-lm對于 pasc

3、al 語言fpc math.pasfpc complexity.pasfpc park.pas注意事項：1、文件名（程序名和輸入輸出文件名）必須使用英文小寫。2、C/C+中函數(shù) main()的返回值類型必須是 int，程序正常結(jié)束時的返回值必須是 0。3、全國統(tǒng)一評測時采用的機器配置為：CPU AMD Athlon(tm) II x2 240 processor，2.8GHz， 內(nèi)存 4G，上述時限以此配置為準。4、只提供 Linux 格式附加樣例文件。5、提交的程序代碼文件的放置位置請參照各省的具體要求。6、特別提醒：評測在當前最新公布的 NOI Linux 下進行，各語言的編譯器版本以其為

4、準?！締栴}描述】1小凱的疑惑(math.cpp/c/pas)小凱手中有兩種面值的金幣，兩種面值均為正整數(shù)且彼此互素。每種金幣小凱都有無數(shù)個。在不找零的情況下，僅憑這兩種金幣，有些物品他是無法準確支付的?，F(xiàn)在小凱想知道在無法準確支付的物品中，最貴的價值是多少金幣？注意：輸入數(shù)據(jù)保證存在小凱無法準確支付的商品?！据斎敫袷健枯斎胛募麨?math.in。輸入數(shù)據(jù)僅一行，包含兩個正整數(shù) a 和 b，它們之間用一個空格隔開，表示小凱手中金幣的面值?！据敵龈袷健枯敵鑫募麨?math.out。輸出文件僅一行，一個正整數(shù) N，表示不找零的情況下，小凱用手中的金幣不能準確支付的最貴的物品的價值?！据斎胼敵鰳永?/p>

5、 1】math.inmath.out3 711見選手目錄下的 math/math1.in 和 math/math1.ans?！据斎胼敵鰳永?1 說明】小凱手中有面值為3 和7 的金幣無數(shù)個，在不找零的前提下無法準確支付價值為1、2、4、5、8、11 的物品，其中最貴的物品價值為 11，比 11 貴的物品都能買到，比如：12 = 3 * 4 + 7 * 013 = 3 * 2 + 7 * 114 = 3 * 0 + 7 * 215 = 3 * 5 + 7 * 0【輸入輸出樣例 2】見選手目錄下的 math/math2.in 和 math/math2.ans。【數(shù)據(jù)規(guī)模與約定】對于 30%的數(shù)據(jù)：

6、 1 a，b 50。對于 60%的數(shù)據(jù)： 1 a，b 10,000。對于 100%的數(shù)據(jù)：1 a，b 1,000,000,000?！締栴}描述】2時間復雜度(complexity.cpp/c/pas)小明正在學習一種新的編程語言 A+，剛學會循環(huán)語句的他激動地寫了好多程序并給出了他自己算出的時間復雜度，可他的編程老師實在不想一個一個檢查小明的程序， 于是你的機會來啦！下面請你編寫程序來判斷小明對他的每個程序給出的時間復雜度是否正確。A+語言的循環(huán)結(jié)構(gòu)如下：F i x y循環(huán)體E其中“F i x y”表示新建變量 （i 變量 i 不可與未被銷毀的變量重名）并初始化為 x，然后判斷 i 和 y 的大

7、小關(guān)系，若 i 小于等于 y 則進入循環(huán)，否則不進入。每次循環(huán)結(jié)束后 i 都會被修改成 i +1，一旦 i 大于 y 終止循環(huán)。x 和 y 可以是正整數(shù)（x 和 y 的大小關(guān)系不定）或變量 n。n 是一個表示數(shù)據(jù)規(guī)模的變量，在時間復雜度計算中需保留該變量而不能將其視為常數(shù)，該數(shù)遠大于 100。“E”表示循環(huán)體結(jié)束。循環(huán)體結(jié)束時，這個循環(huán)體新建的變量也被銷毀。注：本題中為了書寫方便，在描述復雜度時，使用大寫英文字母“O”表示通常意義下“”的概念?！据斎敫袷健枯斎胛募麨?complexity.in。輸入文件第一行一個正整數(shù) t，表示有 t（t 10）個程序需要計算時間復雜度。每個程序我們只需抽取

8、其中 “F i x y”和“E”即可計算時間復雜度。注意：循環(huán)結(jié)構(gòu)允許嵌套。接下來每個程序的第一行包含一個正整數(shù) L 和一個字符串，L 代表程序行數(shù)，字符串表示這個程序的復雜度，“O(1)”表示常數(shù)復雜度，“O(nw)”表示復雜度為𝑛𝑤，其中w 是一個小于100 的正整數(shù)（輸入中不包含引號），輸入保證復雜度只有O(1)和O(nw) 兩種類型。接下來 L 行代表程序中循環(huán)結(jié)構(gòu)中的“F i x y”或者 “E”。程序行若以“F”開頭，表示進入一個循環(huán)，之后有空格分離的三個字符（串）i x y， 其中 i 是一個小寫字母（保證不為“n”），表示新建的變量名，x 和 y

9、 可能是正整數(shù)或 n ，已知若為正整數(shù)則一定小于 100。程序行若以“E”開頭，則表示循環(huán)體結(jié)束。【輸出格式】輸出文件名為 complexity.out。輸出文件共 t 行，對應輸入的 t 個程序，每行輸出“Yes”或“No”或者“ERR”（輸出中不包含引號），若程序?qū)嶋H復雜度與輸入給出的復雜度一致則輸出“Yes”，不一致則輸出“No”，若程序有語法錯誤（其中語法錯誤只有: F 和 E 不匹配 新建的變量與已經(jīng)存在但未被銷毀的變量重復兩種情況），則輸出“ERR”。注意：即使在程序不會執(zhí)行的循環(huán)體中出現(xiàn)了語法錯誤也會編譯錯誤， 要輸出“ERR”?！据斎胼敵鰳永?1】complexity.inco

10、mplexity.out82 O(1)F i 1 1 E2 O(n1)F x 1 n E1 O(1)F x 1 n 4 O(n2)F x 5 n F y 10 n EE4 O(n2)F x 9 n EF y 2 n E4 O(n1)F x 9 n F y n 4 EE4 O(1)F y n 4 F x 9 n EE4 O(n2)F x 1 n F x 1 10 EEYes Yes ERRYes No Yes Yes ERR見選手目錄下的complexity/complexity1.in 和 complexity/complexity1.ans?！据斎胼敵鰳永?1 說明】第一個程序 i 從 1

11、到 1 是常數(shù)復雜度。第二個程序 x 從 1 到 n 是 n 的一次方的復雜度。第三個程序有一個 F 開啟循環(huán)卻沒有 E 結(jié)束，語法錯誤。第四個程序二重循環(huán)，n 的平方的復雜度。第五個程序兩個一重循環(huán)，n 的一次方的復雜度。第六個程序第一重循環(huán)正常，但第二重循環(huán)開始即終止（因為n 遠大于100，100 大于4）。第七個程序第一重循環(huán)無法進入，故為常數(shù)復雜度。第八個程序第二重循環(huán)中的變量 x 與第一重循環(huán)中的變量重復，出現(xiàn)語法錯誤，輸出ERR?！据斎胼敵鰳永?2】見選手目錄下的complexity/complexity2.in 和 complexity/complexity2.ans?！緮?shù)據(jù)規(guī)模

12、與約定】對于 30%的數(shù)據(jù)：不存在語法錯誤，數(shù)據(jù)保證小明給出的每個程序的前 L/2 行一定為以 F 開頭的語句，第 L/2+1 行至第 L 行一定為以 E 開頭的語句，L<=10，若 x、y 均為整數(shù)，x 一定小于 y，且只有 y 有可能為 n。對于 50%的數(shù)據(jù)：不存在語法錯誤，L<=100，且若 x、y 均為整數(shù)，x 一定小于 y， 且只有 y 有可能為 n。對于 70%的數(shù)據(jù)：不存在語法錯誤，L<=100。對于 100%的數(shù)據(jù)：L<=100。【問題描述】3. 逛公園(park.cpp/c/pas)策策同學特別喜歡逛公園。公園可以看成一張𝑁個點

13、19872;條邊構(gòu)成的有向圖，且沒有自環(huán)和重邊。其中1號點是公園的入口，𝑁號點是公園的出口，每條邊有一個非負權(quán)值， 代表策策經(jīng)過這條邊所要花的時間。策策每天都會去逛公園，他總是從1號點進去，從𝑁號點出來。策策喜歡新鮮的事物，他不希望有兩天逛公園的路線完全一樣，同時策策還是一個特別熱愛學習的好孩子，他不希望每天在逛公園這件事上花費太多的時間。如果1號點到𝑁號點的最短路長為𝑑，那么策策只會喜歡長度不超過𝑑 + 𝐾的路線。策策同學想知道總共有多少條滿足條件的路線，你能幫幫他嗎？ 為避免輸出過大，答案對&#

14、119875;取模。如果有無窮多條合法的路線，請輸出1?！据斎敫袷健枯斎胛募麨?park.in。第一行包含一個整數(shù) 𝑇, 代表數(shù)據(jù)組數(shù)。接下來𝑇組數(shù)據(jù)，對于每組數(shù)據(jù)：第一行包含四個整數(shù) 𝑁, 𝑀, 𝐾, 𝑃，每兩個整數(shù)之間用一個空格隔開。接下來𝑀行，每行三個整數(shù)𝑎𝑖, 𝑏𝑖, 𝑐𝑖 ，代表編號為𝑎𝑖, 𝑏𝑖的點之間有一條權(quán)值

15、為 𝑐𝑖的有向邊，每兩個整數(shù)之間用一個空格隔開。【輸出格式】輸出文件名為 park.out。輸出文件包含 𝑇行，每行一個整數(shù)代表答案?！据斎胼敵鰳永?1】park.inpark.out25 7 2 101 2 12 4 04 5 22 3 23 4 13 5 21 5 32 2 0 101 2 02 1 03-1見選手目錄下的 park/park1.in 和 park/park1.ans。對于第一組數(shù)據(jù)，最短路為 3。1 5, 1 2 4 5, 1 2 3 5 為 3 條合法路徑。【輸入輸出樣例 2】見選手目錄下的 park/park2.in 和

16、 park/park2.ans。【數(shù)據(jù)規(guī)模與約定】對于不同的測試點，我們約定各種參數(shù)的規(guī)模不會超過如下 測試點編號 𝑇 𝑁 𝑀 𝐾 是否有 0 邊 1 5 5 10 0 否 2 5 1000 2000 0 否 3 5 1000 2000 50 否 4 5 1000 2000 50 否 5 5 1000 2000 50 否 6 5 1000 2000 50 是 7 5 100000 200000 0 否 8 3 100000 200000 50 否 9 3 100000 200000 50 是 10 3 100000 200000

17、50 是 對于 100%的數(shù)據(jù), 1 𝑃 109,1 𝑎𝑖, 𝑏𝑖 𝑁 , 0 𝑐𝑖 1000。數(shù)據(jù)保證：至少存在一條合法的路線。 CCF 全國信息學奧林匹克聯(lián)賽（NOIP2017）復賽提高組 day2（請選手務必仔細閱讀本頁內(nèi)容）一題目概況中文題目名稱奶酪寶藏列隊英文題目與子目錄名cheesetreasurephalanx可執(zhí)行文件名cheesetreasurephalanx輸入文件名reasure.inphalanx.in輸出文件名cheese

18、.outtreasure.outphalanx.out每個測試點時限1 秒1 秒2 秒測試點數(shù)目102020每個測試點分值1055附加樣例文件有有有結(jié)果比較方式全文比較（過濾行末空格及文末回車）題目類型傳統(tǒng)傳統(tǒng)傳統(tǒng)運行內(nèi)存上限256M256M512M二提交源程序文件名對于 C+語言cheese.cpptreasure.cppphalanx.cpp對于 C 語言cheese.ctreasure.cphalanx.c對于 pascal 語言cheese.pastreasure.pasphalanx.pas三編譯命令（不包含任何優(yōu)化開關(guān)）對于 C+語言g+ -o cheesecheese.cpp -

19、lmg+ -o treasuretreasure.cpp -lmg+ -o phalanxphalanx.cpp -lm對于 C 語言gcc -o cheesecheese.c -lmgcc -o treasuretreasure.c -lmgcc -o phalanxphalanx.c -lm對于 pascal 語言fpc cheese.pasfpc treasure.pasfpc phalanx.pas注意事項：1、文件名（程序名和輸入輸出文件名）必須使用英文小寫。2、C/C+中函數(shù) main()的返回值類型必須是 int，程序正常結(jié)束時的返回值必須是 0。3、全國統(tǒng)一評測時采用的機器配置

20、為：CPU AMD Athlon(tm) II x2 240 processor，2.8GHz， 內(nèi)存 4G，上述時限以此配置為準。4、只提供 Linux 格式附加樣例文件。5、提交的程序代碼文件的放置位置請參照各省的具體要求。6、特別提醒：評測在當前最新公布的 NOI Linux 下進行，各語言的編譯器版本以其為準?！締栴}描述】1奶酪(cheese.cpp/c/pas)現(xiàn)有一塊大奶酪，它的高度為 h，它的長度和寬度我們可以認為是無限大的，奶酪中間有許多半徑相同的球形空洞。我們可以在這塊奶酪中建立空間坐標系，在坐標系中， 奶酪的下表面為z = 0，奶酪的上表面為z = h?，F(xiàn)在，奶酪的下表面有

21、一只小老鼠 Jerry，它知道奶酪中所有空洞的球心所在的坐標。如果兩個空洞相切或是相交，則 Jerry 可以從其中一個空洞跑到另一個空洞，特別地，如果一個空洞與下表面相切或是相交，Jerry 則可以從奶酪下表面跑進空洞；如果一個空洞與上表面相切或是相交，Jerry 則可以從空洞跑到奶酪上表面。位于奶酪下表面的 Jerry 想知道，在不破壞奶酪的情況下，能否利用已有的空洞跑到奶酪的上表面去?空間內(nèi)兩點𝑃1(𝑥1, 𝑦1, 𝑧1)、𝑃2(𝑥2, 𝑦2, 𝑧2)的距離公式如

22、下：dist(𝑃1, 𝑃2) = (𝑥1 𝑥2)2 + (𝑦1 𝑦2)2 + (𝑧1 𝑧2)2【輸入格式】輸入文件名為 cheese.in。每個輸入文件包含多組數(shù)據(jù)。輸入文件的第一行，包含一個正整數(shù) T，代表該輸入文件中所含的數(shù)據(jù)組數(shù)。接下來是 T 組數(shù)據(jù)，每組數(shù)據(jù)的格式如下：第一行包含三個正整數(shù) n，h 和 r，兩個數(shù)之間以一個空格分開，分別代表奶酪中空洞的數(shù)量，奶酪的高度和空洞的半徑。接下來的 n 行，每行包含三個整數(shù) x、y、z，兩個數(shù)之間以一個空格分開，表示空

23、洞球心坐標為(𝑥, 𝑦, 𝑧)。【輸出格式】輸出文件名為 cheese.out。輸出文件包含 T 行，分別對應 T 組數(shù)據(jù)的答案，如果在第 i 組數(shù)據(jù)中，Jerry 能從下表面跑到上表面，則輸出“Yes”，如果不能，則輸出“No”（均不包含引號）?！据斎胼敵鰳永?1】cheese.incheese.out3Yes241No001Yes003251001004252002204見選手目錄下的 cheese/cheese1.in 和 cheese/cheese1.ans?！据斎胼敵鰳永?1 說明】第一組數(shù)據(jù)，由奶酪的剖面圖可見： 第一個空洞在（0，0

24、，0）與下表面相切第二個空洞在（0，0，4）與上表面相切兩個空洞在（0，0，2）相切輸出 Yes第二組數(shù)據(jù)，由奶酪的剖面圖可見： 兩個空洞既不相交也不相切輸出 No第三組數(shù)據(jù)，由奶酪的剖面圖可見： 兩個空洞相交且與上下表面相切或相交輸出 Yes【輸入輸出樣例 2】見選手目錄下的 cheese/cheese2.in 和 cheese/cheese2.ans?！緮?shù)據(jù)規(guī)模與約定】對于 20%的數(shù)據(jù)，n = 1，1 h , r 10,000，坐標的絕對值不超過 10,000。對于 40%的數(shù)據(jù)，1 n 8， 1 h , r 10,000，坐標的絕對值不超過 10,000。對于 80%的數(shù)據(jù)，1 n 1

25、,000，1 h , r 10,000，坐標的絕對值不超過 10,000。對于 100%的數(shù)據(jù)，1 n 1,000，1 h , r 1,000,000,000，T 20，坐標的絕對值不超過 1,000,000,000?！締栴}描述】2. 寶藏（treasure.cpp/c/pas)參與考古挖掘的小明得到了一份藏寶圖，藏寶圖上標出了 n 個深埋在地下的寶藏屋， 也給出了這 n 個寶藏屋之間可供開發(fā)的 m 條道路和它們的長度。小明決心親自前往挖掘所有寶藏屋中的寶藏。但是，每個寶藏屋距離地面都很遠， 也就是說，從地面打通一條到某個寶藏屋的道路是很困難的，而開發(fā)寶藏屋之間的道路則相對容易很多。小明的決心

26、感動了考古挖掘的贊助商，贊助商決定免費贊助他打通一條從地面到某個寶藏屋的通道，通往哪個寶藏屋則由小明來決定。在此基礎(chǔ)上，小明還需要考慮如何開鑿寶藏屋之間的道路。已經(jīng)開鑿出的道路可以任意通行不消耗代價。每開鑿出一條新道路，小明就會與考古隊一起挖掘出由該條道路所能到達的寶藏屋的寶藏。另外，小明不想開發(fā)無用道路，即兩個已經(jīng)被挖掘過的寶藏屋之間的道路無需再開發(fā)。新開發(fā)一條道路的代價是：這條道路的長度 × 從贊助商幫你打通的寶藏屋到這條道路起點的寶藏屋所經(jīng)過的寶藏屋的數(shù)量（包括贊助商幫你打通的寶藏屋和這條道路起點的寶藏屋）。請你編寫程序為小明選定由贊助商打通的寶藏屋和之后開鑿的道路，使得工程總

27、代價最小，并輸出這個最小值?！据斎敫袷健枯斎胛募麨?treasure.in。第一行兩個用空格分離的正整數(shù) n 和 m，代表寶藏屋的個數(shù)和道路數(shù)。接下來 m 行，每行三個用空格分離的正整數(shù)，分別是由一條道路連接的兩個寶藏屋的編號（編號為 1n），和這條道路的長度 v?！据敵龈袷健枯敵鑫募麨?treasure.out。輸出共一行，一個正整數(shù)，表示最小的總代價。【輸入輸出樣例 1】reasure.out454121133141234341見選手目錄下的 treasure/treasure1.in 與 treasure/treasure1.ans【輸入輸出樣例 1 說明】小

28、明選定讓贊助商打通了 1 號寶藏屋。小明開發(fā)了道路 1à2，挖掘了 2 號寶藏。開發(fā)了道路 1à4，挖掘了 4 號寶藏。還開發(fā)了道路 4à3，挖掘了 3 號寶藏。工程總代價為：1×1 + 1×1 + 1×2 = 4(1à2)(1à4)(4à3)【樣例輸入輸出 2】reasure.out455121133141234342見選手目錄下的 treasure/treasure2.in 與 treasure/treasure2.ans?！据斎胼敵鰳永?2 說明】小明選定讓贊助商打通了 1

29、號寶藏屋。小明開發(fā)了道路 1à2，挖掘了 2 號寶藏。開發(fā)了道路 1à3，挖掘了 3 號寶藏。還開發(fā)了道路 1à4，挖掘了 4 號寶藏。工程總代價為：1×1 + 3×1 + 1×1 = 5(1à2)(1à3)(1à4)【輸入輸出樣例 3】見選手目錄下的 treasure/treasure3.in 和 treasure/treasure3.out?！緮?shù)據(jù)規(guī)模與約定】對于 20%的數(shù)據(jù)：保證輸入是一棵樹，1n8，v5000 且所有的 v 都相等。對于 40%的數(shù)據(jù)：1n8，0m1000，v5000 且所有的

30、v 都相等。對于 70%的數(shù)據(jù)：1n8，0m1000，v 5000對 于 100% 的 數(shù) 據(jù) ： 1n12，0m1000，v 500000【問題描述】3列隊(phalanx.cpp/c/pas)Sylvia 是一個熱愛學習的女孩子。前段時間，Sylvia 參加了學校的軍訓。眾所周知，軍訓的時候需要站方陣。Sylvia所在的方陣中有n × m名學生，方陣的行數(shù)為 n，列數(shù)為 m。為了便于管理，教官在訓練開始時，按照從前到后，從左到右的順序給方陣中的學生從 1 到 n × m 編上了號碼（參見后面的樣例）。即：初始時，第 i 行第 j 列的學生的編號是(i 1) × m + j。然而在練習方陣的時候，經(jīng)常會有學生因為各種各樣的事情需要離隊。在一天中，一共發(fā)生了 q 件這樣的離隊事件。每一