noip2017提高組試題

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

2、th.cppcomplexity.cpppark.cpp對于C語言math.ccomplexity.cpark.c對于pascal語百math.pascomplexity.paspark.pas三.編譯命令（不包含任何優(yōu)化開關）對于C+語百g+-omathmath.cpp-lmg+-ocomplexitycomplexity.cpp-lmg+-oparkpark.cpp-lm對于C語言gcc-omathmath.c-lmgcc-ocomplexitycomplexity.c-lmgcc-oparkpark.c-lm對于pascal語百fpcmath.pasfpccomplexity.pasfp

3、cpark.pas注意事項：1、文件名（程序名和輸入輸出文件名）必須使用英文小寫。2、C/C+中函數(shù)main（）的返回值類型必須是int,程序正常結束時的返回值必須是0。3、全國統(tǒng)一評測時采用的機器配置為：CPUAMDAthlon（tm）IIx2240processor,2.8GHz,內存4G,上述時限以此配置為準。4、只提供Linux格式附加樣例文件。5、提交的程序代碼文件的放置位置請參照各省的具體要求。6、特別提醒：評測在當前最新公布的NOILinux下進行，各語言的編譯器版本以其為準。【問題描述】1.小凱的疑惑(math.cpp/c/pas)小凱手中有兩種面值的金幣，兩種面值均為正整數(shù)且

4、彼此互素。每種金幣小凱都有無數(shù)個。在不找零的情況下，僅憑這兩種金幣，有些物品他是無法準確支付的?，F(xiàn)在小凱想知道在無法準確支付的物品中，最貴的價值是多少金幣？注意：輸入數(shù)據(jù)保證存在小凱無法準確支付的商品。【輸入格式】輸入文件名為math.in。輸入數(shù)據(jù)僅一行，包含兩個正整數(shù)a和b,它們之間用一個空格隔開，表示小凱手中金幣的面值?！据敵龈袷健枯敵鑫募麨閙ath.out。輸出文件僅一行，一個正整數(shù)N,表示不找零的情況下，小凱用手中的金幣不能準確支付的最貴的物品的價值。【輸入輸出樣例1】math.inmath.out3711見選手目錄下的math/mathl.in和math/mathl.ans【輸入

5、輸出樣例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ù)：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/pa

6、s）小明正在學習一種新的編程語言A+,剛學會循環(huán)語句的他激動地寫了好多程序并給出了他自己算出的時間復雜度，可他的編程老師實在不想一個一個檢查小明的程序，于是你的機會來啦！下面請你編寫程序來判斷小明對他的每個程序給出的時間復雜度是否正確。A+語言的循環(huán)結構如下：Fixy循環(huán)體E其中“Fixy”表示新建變量i（變量i不可與未被銷毀的變量重名）并初始化為x,然后判斷i和y的大小關系，若i小于等于y則進入循環(huán)，否則不進入。每次循環(huán)結束后i都會被修改成i+1,一旦i大于y終止循環(huán)。x和y可以是正整數(shù)（x和y的大小關系不定）或變量n0n是一個表示數(shù)據(jù)規(guī)模的變量，在時間復雜度計算中需保留該變量而不能將其視為

7、常數(shù)，該數(shù)遠大于100?！癊”表示循環(huán)體結束。循環(huán)體結束時，這個循環(huán)體新建的變量也被銷毀。注：本題中為了書寫方便，在描述復雜度時，使用大寫英文字母“O”表示通常意義下“。”的概念。【輸入格式】輸入文件名為complexity.in。輸入文件第一行一個正整數(shù)t,表示有t（t<10）個程序需要計算時間復雜度。每個程序我們只需抽取其中“Fixy”和“E”即可計算時間復雜度。注意：循環(huán)結構允許嵌套。接下來每個程序的第一行包含一個正整數(shù)L和一個字符串，L代表程序行數(shù)，字符串表示這個程序的復雜度，0（1）”表示常數(shù)復雜度，'O（nAw）”表示復雜度為？?，其中w是一個小于100的正整數(shù)（輸入

8、中不包含引號），輸入保證復雜度只有O（1）和O（nAw）兩種類型。接下來L行代表程序中循環(huán)結構中的“Fixy”或者“E”。程序行若以“F”開頭，表示進入一個循環(huán)，之后有空格分離的三個字符（串）ixy,其中i是一個小寫字母（保證不為“n”），表示新建的變量名，x和y可能是正整數(shù)或n,已知若為正整數(shù)則一定小于100。程序行若以“E”開頭，則表示循環(huán)體結束。【輸出格式】輸出文件名為complexity.out。輸出文件共t行，對應輸入的t個程序，每行輸出“Yes”或“No”或者“ERR”（輸出中不包含引號），若程序實際復雜度與輸入給出的復雜度一致則輸出“Yes”，不一致則輸出“No”，若程序有語法錯

9、誤（其中語法錯誤只有：F和E不匹配新建的變量與已經存在但未被銷毀的變量重復兩種情況），則輸出“ERR”。要輸出注意：即使在程序不會執(zhí)行的循環(huán)體中出現(xiàn)了語法錯誤也會編譯錯誤,“ERR”?！据斎胼敵鰳永?】complexity.incomplexity.out8Yes20(1)YesFi11ERREYes20(nA1)NoFx1nYesEYes10(1)Fx1n40(nA2)Fx5nFy10nEE40(nA2)Fx9nEFy2nE40(nA1)Fx9nFyn4EE40(1)Fyn4Fx9nEE40(nA2)Fx1nFx110EEERR見選手目錄下的complexity/complexityl.in

10、和complexity/complexityl.ans【輸入輸出樣例1說明】第一個程序i從1到1是常數(shù)復雜度。第二個程序x從1到n是n的一次方的復雜度。第三個程序有一個F開啟循環(huán)卻沒有E結束，語法錯誤。第四個程序二重循環(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?！据斎胼敵鰳永?】見選手目錄下的complexity/complexity2.in和complexit

11、y/complexity2.ans。【數(shù)據(jù)規(guī)模與約定】對于30%的數(shù)據(jù)：不存在語法錯誤，數(shù)據(jù)保證小明給出的每個程序的前L/2行一定為以F開頭的語句，第L/2+1行至第L行一定為以E開頭的語句，L<=10，若x、y均為整數(shù)，x一定小于y,且只有y有可能為no對于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)策策同學特別喜歡逛公園。公園可以看成一張？?t點？?條邊構成的有向圖，且沒有自環(huán)和

12、重邊。其中1號點是公園的入口，？/點是公園的出口，每條邊有一個非負權值，代表策策經過這條邊所要花的時間。策策每天都會去逛公園，他總是從1號點進去，從？名點出來。策策喜歡新鮮的事物，他不希望有兩天逛公園的路線完全一樣，同時策策還是一個特別熱愛學習的好孩子，他不希望每天在逛公園這件事上花費太多的時間。如果1號點到?/點的最短路長為?那么策策只會喜歡長度不超過？?+?勺路線。策策同學想知道總共有多少條滿足條件的路線，你能幫幫他嗎？為避免輸出過大，答案對？取模。如果有無窮多條合法的路線，請輸出-1?！据斎敫袷健枯斎胛募麨閜ark.in。第一行包含一個整數(shù)?代表數(shù)據(jù)組數(shù)。接下來？組數(shù)據(jù)，對于每組數(shù)據(jù)：

13、第一行包含四個整數(shù)？?,？?每兩個整數(shù)之間用一個空格隔開。接下來？知，每行三個整數(shù)？?？代表編號為？?電之間有一條權值為？?勺有向邊，每兩個整數(shù)之間用一個空格隔開。【輸出格式】輸出文件名為park.out。輸出文件包含？行，每行一個整數(shù)代表答案【輸入輸出樣例1】park.inpark.out2357210-112124045223234135215322010120210見選手目錄下的park/park1.in和park/park1.ans對于第一組數(shù)據(jù)，最短路為3。1-5,12-4-5,1-2-3-5為3條合法路徑?！据斎胼敵鰳永?】見選手目錄下的park/park2.in和park/par

14、k2.ans。【數(shù)據(jù)規(guī)模與約定】對于不同的測試點，我們約定各種參數(shù)的規(guī)模不會超過如下測試點編號?是否有0邊155100否25100020000否351000200050否451000200050否551000200050否651000200050是751000002000000否8310000020000050否9310000020000050是10310000020000050是對于100%的數(shù)據(jù)，1<?實109,1<霜?寧？0<?1000。數(shù)據(jù)保證：至少存在一條合法的路線。CCF全國信息學奧林匹克聯(lián)賽（NOIP2017）復賽提高組day2（請選手務必仔細閱讀本頁內容）題目

15、概況中文題目名稱奶酪寶臧列隊英文題目與子目錄名cheesetreasurephalanx可執(zhí)行文件名cheesetreasurephalanx輸入文件名reasure.inphalanx.in輸出文件名cheese.outtreasure.outphalanx.out每個測試點時限11秒1秒2秒測試點數(shù)目102020每個測試點分值1055附加樣例文件有有有結果比較方式全文比較（過濾行末空格及文末回車）題目傳統(tǒng)傳統(tǒng)傳統(tǒng)運行內存上限256M256M512M.提交源程序文件名對于C+語百cheese.cpptreasure.cppphalanx.cpp對于C語言cheese.ct

16、reasure.cphalanx.c對于pascal語百cheese.pastreasure.pasphalanx.pas三.編譯命令（不包含任何優(yōu)化開關）對于C+語百g+-ocheesecheese.cpp-lmg+-otreasuretreasure.cpp-lmg+-ophalanxphalanx.cpp-lm對于C語言gcc-ocheesecheese.c-lmgcc-otreasuretreasure.c-lmgcc-ophalanxphalanx.c-lm對于pascal語百fpccheese.pasfpctreasure.pasfpcphalanx.pas注意事項：1、文件名（程

17、序名和輸入輸出文件名）必須使用英文小寫。2、C/C+中函數(shù)main（）的返回值類型必須是int,程序正常結束時的返回值必須是0。3、全國統(tǒng)一評測時采用的機器配置為：CPUAMDAthlon（tm）IIx2240processor,2.8GHz,內存4G,上述時限以此配置為準。4、只提供Linux格式附加樣例文件。5、提交的程序代碼文件的放置位置請參照各省的具體要求。6、特別提醒：評測在當前最新公布的NOILinux下進行，各語言的編譯器版本以其為準?！締栴}描述】(cheese.cpp/c/pas)現(xiàn)有一塊大奶酪，它的高度為h,它的長度和寬度我們可以認為是無限大的，奶酪中間有許多半徑相同的球形空

18、洞。我們可以在這塊奶酪中建立空間坐標系，在坐標系中，奶酪的下表面為z=0,奶酪的上表面為z=h?，F(xiàn)在，奶酪的下表面有一只小老鼠Jerry,它知道奶酪中所有空洞的球心所在的坐標。如果兩個空洞相切或是相交，則Jerry可以從其中一個空洞跑到另一個空洞，特別地，如果一個空洞與下表面相切或是相交，Jerry則可以從奶酪下表面跑進空洞；如果一個空洞與上表面相切或是相交，Jerry則可以從空洞跑到奶酪上表面。位于奶酪下表面的Jerry想知道，在不破壞奶酪的情況下，能否利用已有的空洞跑到奶酪的上表面去？空間內兩點？?(？?,?,?)、?(?,?,?)的距離公式如下：dist(?,?)=v(?-?)2+(?-

19、?)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、v、z,兩個數(shù)之間以一個空格分開，表示空洞球心坐標為(？??！据敵龈袷健枯敵鑫募麨閏heese.out°輸出文件包含T行，分別對應T組數(shù)據(jù)的答案，如果在第i組數(shù)據(jù)中，Jerry能從下表面跑到上表面，則輸出“Yes”，如果不能，則輸出“N?！?均不包含

20、引號)。【輸入輸出樣例1】cheese.incheese.out3Yes241No001Yes003251001004252002204見選手目錄下的cheese/cheesel.in【輸入輸出樣例1說明】第一組數(shù)據(jù)，由奶酪的剖面圖可見：第一個空洞在（0,0,0）與下表面相切第二個空洞在（0,0,4）與上表面相切兩個空洞在（0,0,2）相切輸出Yes第二組數(shù)據(jù)，由奶酪的剖面圖可見：兩個空洞既不相交也不相切輸出No第三組數(shù)據(jù)，由奶酪的剖面圖可見：兩個空洞相交且與上下表面相切或相交輸出Yes和 cheese/cheesel.ans【輸入輸出樣例2】見選手目錄下的cheese/cheese2.in和

21、cheese/cheese2.ans。【數(shù)據(jù)規(guī)模與約定】對于20%的數(shù)據(jù)，n=1,1&h,r&10,000,坐標的絕對值不超過10,000。對于40%的數(shù)據(jù)，1<n08,1<h,r<10,000,坐標的絕對值不超過10,000。對于80%的數(shù)據(jù)，1<n&1,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.cp

22、p/c/pas）參與考古挖掘的小明得到了一份藏寶圖，藏寶圖上標出了n個深埋在地下的寶藏屋,也給出了這n個寶藏屋之間可供開發(fā)的m條道路和它們的長度。小明決心親自前往挖掘所有寶藏屋中的寶藏。但是，每個寶藏屋距離地面都很遠，也就是說，從地面打通一條到某個寶藏屋的道路是很困難的，而開發(fā)寶藏屋之間的道路則相對容易很多。小明的決心感動了考古挖掘的贊助商，贊助商決定免費贊助他打通一條從地面到某個寶藏屋的通道，通往哪個寶藏屋則由小明來決定。在此基礎上，小明還需要考慮如何開鑿寶藏屋之間的道路。已經開鑿出的道路可以任意通行不消耗代價。每開鑿出一條新道路，小明就會與考古隊一起挖掘出由該條道路所能到達的寶藏屋的寶藏。

23、另外，小明不想開發(fā)無用道路，即兩個已經被挖掘過的寶藏屋之間的道路無需再開發(fā)。新開發(fā)一條道路的代價是：這條道路的長度x從贊助商幫你打通的寶藏屋到這條道路起點的寶藏屋所經過的寶藏屋的數(shù)量（包括贊助商幫你打通的寶藏屋和這條道路起點的寶藏屋）。請你編寫程序為小明選定由贊助商打通的寶藏屋和之后開鑿的道路，使得工程總代價最小，并輸出這個最小值。【輸入格式】輸入文件名為treasure.in。第一行兩個用空格分離的正整數(shù)n和m,代表寶藏屋的個數(shù)和道路數(shù)。接下來m行，每行三個用空格分離的正整數(shù)，分別是由一條道路連接的兩個寶藏屋的編號（編號為1n）,和這條道路的長度v?！据敵龈袷健枯敵鑫募麨閠reasure.

24、out。輸出共一行，一個正整數(shù)，表示最小的總代價【輸入輸出樣例1】reasure.out454121133141234341見選手目錄下的treasure/treasurel.in與treasure/treasurel.ans【輸入輸出樣例1說明】小明選定讓贊助商打通了1號寶藏屋。小明開發(fā)了道路12,挖掘了2號寶藏。開發(fā)了道路14,挖掘了4號寶藏。還開發(fā)了道路43,挖掘了3號寶藏。工程總代價為：1x1+1x1+1x2=4(12)(14)(43)【樣例輸入輸出2】reasure.out451211331412343425見選手目錄下的treasur

25、e/treasure2.in與treasure/treasure2.ans?！据斎胼敵鰳永?說明】小明選定讓贊助商打通了1號寶藏屋。小明開發(fā)了道路12,挖掘了2號寶藏。開發(fā)了道路13,挖掘了3號寶藏。還開發(fā)了道路14,挖掘了4號寶藏。工程總代價為：1X1+3X1+1X1=5(12)(13)(14)【輸入輸出樣例3】見選手目錄下的treasure/treasure3.in和treasure/treasure3.out【數(shù)據(jù)規(guī)模與約定】對于20%的數(shù)據(jù)：保證輸入是一棵樹，1&n&8,v<5000且所有的v都相等。對于40%的數(shù)據(jù)：1<n<8,0&m&

26、;1000,v&5000且所有的v都相等。對于70%的數(shù)據(jù)：1<n<8,0<m<1000,v<5000對于100%的數(shù)據(jù)：1&n&12,0&m&1000,v<5000003.列隊【問題描述】(phalanx.cpp/c/pas)Sylvia是一個熱愛學習的女孩子。前段時間，Sylvia參加了學校的軍訓。眾所周知，軍訓的時候需要站方陣。Sylvia所在的方陣中有nxmg學生，方B$的行數(shù)為n,列數(shù)為m。為了便于管理，教官在訓練開始時，按照從前到后，從左到右的順序給方陣中的學生從1至Inxm編上了號碼(參見后面的樣例)。即：初始時，第i行第j列的學生的編號是(i-1)xm+j0然而在練習方陣的時候，經常會有學生因為各種各樣的事情需要離隊。在一天中，一共發(fā)生了q件這樣的離隊事件。每一次離隊事件可以用數(shù)對(？(1<x<n,1<y<m®述，表示第x行第y列的學生離隊。在有學生離隊后，隊伍