p提高組試題+版

1、CCF全國(guó)信息學(xué)奧林匹克聯(lián)賽（NOIP2017）復(fù)賽提局組dayl（請(qǐng)選手務(wù)必仔細(xì)閱讀本貞內(nèi)容）.題目概況中文題目名稱小凱的疑惑時(shí)間復(fù)雜度逛公園央文題目與子目錄名一mathcomplexitypark可執(zhí)行文件名mathcomplexitypark輸入文件名輸出文件名每個(gè)測(cè)試點(diǎn)時(shí)限1秒1秒3秒測(cè)試點(diǎn)數(shù)目201010每個(gè)測(cè)試點(diǎn)分值51010附加樣例文件有有有結(jié)果比較方式全文比較（過(guò)濾行末空格及文末回車）題目類型傳統(tǒng)傳統(tǒng)傳統(tǒng)運(yùn)行內(nèi)存上限256M256M512M.提交源程序文件名對(duì)于C+語(yǔ)言對(duì)于C語(yǔ)言對(duì)于pascal語(yǔ)言三.編譯命令（不包含任何優(yōu)化開關(guān)）對(duì)于C+語(yǔ)言g+-omath-lmg+-oco

2、mplexity-lmg+-opark-lm對(duì)于C語(yǔ)言gcc-omath-lmgcc-ocomplexity-lmgcc-opark-lm對(duì)于pascal語(yǔ)言fpcfpcfpc注意事項(xiàng)：1、文件名（程序名和輸入輸出文件名）必須使用英文小寫。2、C/C+中函數(shù)main（）的返回值類型必須是int，程序正常結(jié)束時(shí)的返回值必須是0。3、全國(guó)統(tǒng)一評(píng)測(cè)時(shí)采用的機(jī)器配置為：CPUAMDAthlon（tm）IIx2240processor,內(nèi)存4G上述時(shí)限以此配置為準(zhǔn)。4、只提供Linux格式附加樣例文件。5、提交的程序代碼文件的放置位置請(qǐng)參照各省的具體要求。6、特別提醒：評(píng)測(cè)在當(dāng)前最新公布的NOILinu

3、x下進(jìn)行，各語(yǔ)言的編譯器版本以其為準(zhǔn)?！締?wèn)題描述】1.小凱的疑惑c/pas)小凱手中有兩種面值的金幣，兩種面值均為正整數(shù)且彼此互素。每種金幣小凱都有無(wú)數(shù)個(gè)。在不找零的情況下，僅憑這兩種金幣，有些物品他是無(wú)法準(zhǔn)確支付的。現(xiàn)在小凱想知道在無(wú)法準(zhǔn)確支付的物品中，最貴的價(jià)值是多少金幣？注意：輸入數(shù)據(jù)保證存在小凱無(wú)法準(zhǔn)確支付的商品?！据斎敫袷健枯斎胛募麨椤］斎霐?shù)據(jù)僅一行，包含兩個(gè)正整數(shù)a和b,它們之間用一個(gè)空格隔開，表示小凱手中金幣的面值。【輸出格式】輸出文件名為。輸出文件僅一行，一個(gè)正整數(shù)N,表示不找零的情況下，小凱用手中的金幣不能準(zhǔn)確支付的最貴的物品的價(jià)值。【輸入輸出樣例1】3711見(jiàn)選手目錄下的

4、math/和math/?！据斎胼敵鰳永?說(shuō)明】小凱手中有面值為3和7的金幣無(wú)數(shù)個(gè)，在不找零的前提下無(wú)法準(zhǔn)確支付價(jià)值為1、2、4、5、8、11的物品，其中最貴的物品價(jià)值為11,比11貴的物品都能買到,比如：12 =3*4+7*013 =3*2+7*114 =3*0+7*215 =3*5+7*0.【輸入輸出樣例2】見(jiàn)選手目錄下的math/和math/。【數(shù)據(jù)規(guī)模與約定】對(duì)丁30%的數(shù)據(jù)：1<a,b<50。對(duì)丁60%的數(shù)據(jù)：1<a,b<10,000。對(duì)丁100%的數(shù)據(jù)：1<a,b<1,000,000,000。【問(wèn)題描述】2.時(shí)間復(fù)雜度c/pas）小明正在學(xué)習(xí)一種新

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

6、0?！癊'表示循環(huán)體結(jié)束。循環(huán)體結(jié)束時(shí)，這個(gè)循環(huán)體新建的變量也被銷毀。注：本題中為了書寫方便，在描述復(fù)雜度時(shí)，使用大寫英文字母“O'表示通常意義下的概念?！据斎敫袷健枯斎胛募麨?。輸入文件第一行一個(gè)正整數(shù)t,表示有t（tV10）個(gè)程序需要計(jì)算時(shí)間復(fù)雜度。每個(gè)程序我們只需抽取其中“Fixy”和“E'即可計(jì)算時(shí)間復(fù)雜度。注意：循環(huán)結(jié)構(gòu)允許嵌套。接下來(lái)每個(gè)程序的第一行包含一個(gè)正整數(shù)L和一個(gè)字符申，L代表程序行數(shù)，字符申表示這個(gè)程序的復(fù)雜度，“0（1）”表示常數(shù)復(fù)雜度，O（nAw）”表示復(fù)雜度為?，其中w是一個(gè)小丁100的正整數(shù)（輸入中不包含引號(hào)），輸入保證復(fù)雜度只有0（1）和

7、O（nw）兩種類型。接下來(lái)L行代表程序中循環(huán)結(jié)構(gòu)中的“Fixy”或者"E'。程序行若以“F'開頭，表示進(jìn)入一個(gè)循環(huán)，之后有空格分離的三個(gè)字符（申）ixy,其中i是一個(gè)小寫字母（保證不為“n”），表示新建的變量名，x和y可能是正整數(shù)或n，已知若為正整數(shù)則一定小丁100。程序行若以“E'開頭，則表示循環(huán)體結(jié)束。【輸出格式】輸出文件名為。輸出文件共t行，對(duì)應(yīng)輸入的t個(gè)程序，每行輸出“Yes”或“N6'或者“ERR（輸出中不包含引號(hào)），若程序?qū)嶋H復(fù)雜度與輸入給出的復(fù)雜度一致則輸出“YeS,不一致則輸出“N6',若程序有語(yǔ)法錯(cuò)誤（其中語(yǔ)法錯(cuò)誤只有：F和E

8、不匹配新建的變量與已經(jīng)存在但未被銷毀的變量重復(fù)兩種情況），則輸出“ERR。注意：即使在程序不會(huì)執(zhí)行的循環(huán)體中出現(xiàn)了語(yǔ)法錯(cuò)誤也會(huì)編譯錯(cuò)誤，要輸出“ERR?！据斎胼敵鰳永?】820(1)Fi11E20(nA1)Fx1nE10(1)Fx1n40(nA2)Fx5nFy10nEE4O(nA2)Fx9nEFy2nE4O(nA1)Fx9nFyn4EE40(1)Fyn4Fx9nEE40(nA2)Fx1nFx110EEYesYesERRYesNoYesYesERR見(jiàn)選手目錄下的complexity/和complexity/?！据斎胼敵鰳永?說(shuō)明】第一個(gè)程序i從1到1是常數(shù)復(fù)雜度。第二個(gè)程序x從1到n是n的一次方

9、的復(fù)雜度。第三個(gè)程序有一個(gè)F開啟循環(huán)卻沒(méi)有E結(jié)束，語(yǔ)法錯(cuò)誤。第四個(gè)程序二重循環(huán)，n的平方的復(fù)雜度。第五個(gè)程序兩個(gè)一重循環(huán)，n的一次方的復(fù)雜度。第六個(gè)程序第一重循環(huán)正常，但第二重循環(huán)開始即終止（因?yàn)閚遠(yuǎn)大于100,100大于4）。第七個(gè)程序第一重循環(huán)無(wú)法進(jìn)入，故為常數(shù)復(fù)雜度。第八個(gè)程序第二重循環(huán)中的變量x與第一重循環(huán)中的變量重復(fù)，出現(xiàn)語(yǔ)法錯(cuò)誤,輸出ERR【輸入輸出樣例2】見(jiàn)選手目錄下的complexity/和complexity/。【數(shù)據(jù)規(guī)模與約定】對(duì)于30%的數(shù)據(jù)：不存在語(yǔ)法錯(cuò)誤，數(shù)據(jù)保證小明給出的每個(gè)程序的前L/2行一定為以F開頭的語(yǔ)句，第L/2+1行至第L行一定為以E開頭的語(yǔ)句，L<

10、=1Q若x、y均為整數(shù)，x一定小于y,且只有y有可能為n。對(duì)于50%的數(shù)據(jù)：不存在語(yǔ)法錯(cuò)誤，L<=100且若x、y均為整數(shù)，x一定小于y,且只有y有可能為n。對(duì)于70%的數(shù)據(jù)：不存在語(yǔ)法錯(cuò)誤，L<=100。對(duì)于100%的數(shù)據(jù):L<=100o【問(wèn)題描述】3.逛公園c/pas)策策同學(xué)特別喜歡逛公園。公園可以看成一張？?個(gè)點(diǎn)？?條邊構(gòu)成的有向圖，且沒(méi)有自環(huán)和重邊。其中1號(hào)點(diǎn)是公園的入口，？阿點(diǎn)是公園的出口，每條邊有一個(gè)非負(fù)權(quán)值，代表策策經(jīng)過(guò)這條邊所要花的時(shí)間。策策每天都會(huì)去逛公園，他總是從1號(hào)點(diǎn)進(jìn)去，從？?號(hào)點(diǎn)出來(lái)。策策喜歡新鮮的事物，他不希望有兩天逛公園的路線完全一樣，同時(shí)策策

11、還是一個(gè)特別熱愛(ài)學(xué)習(xí)的好孩子，他不希望每天在逛公園這件事上花費(fèi)太多的時(shí)間。如果1號(hào)點(diǎn)到？?號(hào)點(diǎn)的最短路長(zhǎng)為？，那么策策只會(huì)喜歡長(zhǎng)度不超過(guò)？+?的路線。策策同學(xué)想知道總共有多少條滿足條件的路線，你能幫幫他嗎？為避免輸出過(guò)大，答案對(duì)？?取模。如果有無(wú)窮多條合法的路線，請(qǐng)輸出？1?！据斎敫袷健枯斎胛募麨?。第一行包含一個(gè)整數(shù)？，代表數(shù)據(jù)組數(shù)。接下來(lái)？?組數(shù)據(jù)，對(duì)丁每組數(shù)第一行包含四個(gè)整數(shù)？,?,?,?,每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開。接下來(lái)？?行，每行三個(gè)整數(shù)？?,？?,?,代表編號(hào)為?,?的點(diǎn)之間有一條權(quán)值為?的有向邊，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開。【輸出格式】輸出文件名為。輸出文件包含？行，每行一

12、個(gè)整數(shù)代表答案【輸入輸出樣例1】2572101 212 404522 323 413521 532 20101 202 103-1見(jiàn)選手目錄下的park/和park/。對(duì)于第一組數(shù)據(jù)，最短路為3。1-5,1-2-4-5,1-2-3-5為3條合法路徑。【輸入輸出樣例2】見(jiàn)選手目錄下的park/和park/?！緮?shù)據(jù)規(guī)模與約定】對(duì)于不同的測(cè)試點(diǎn)，我們約定各種參數(shù)的規(guī)模不會(huì)超過(guò)如下測(cè)試點(diǎn)編號(hào)?是否有0邊155100否二25100020000否351000200050否451000200050否551000200050否651000200050是751000002000000否8310000020000

13、050否9310000020000050是10310000020000050是對(duì)丁100%的數(shù)據(jù)，1<?<109,1<?,?V?,0<?<1000。數(shù)據(jù)保證：至少存在一條合法的路線。CCF全國(guó)信息學(xué)奧林匹克聯(lián)賽（NOIP2017）復(fù)賽提高組day2（請(qǐng)選手務(wù)必仔細(xì)閱讀本貞內(nèi)容）.題目概況中文題目名稱奶酪寶藏列隊(duì)央文題目與子目錄名cheesetreasurephalanx可執(zhí)行文件名cheesetreasurephalanx輸入文件名輸出文件名每個(gè)測(cè)試點(diǎn)時(shí)限1秒1秒2秒測(cè)試點(diǎn)數(shù)目102020每個(gè)測(cè)試點(diǎn)分值1055附加樣例文件有有有結(jié)果比較方式全文比較（過(guò)濾行末空格及

14、文末回車）題目類型傳統(tǒng)傳統(tǒng)傳統(tǒng)運(yùn)行內(nèi)存上限256M256M512M.提交源程序文件名對(duì)于C+語(yǔ)言對(duì)于C語(yǔ)言對(duì)于pascal語(yǔ)言三.編譯命令（不包含任何優(yōu)化開關(guān)）對(duì)于C+語(yǔ)言g+-ocheese-lmg+-otreasure-lmg+-ophalanx-lm對(duì)于C語(yǔ)言gcc-ocheese-lmgcc-otreasure-lmgcc-ophalanx-lm對(duì)于pascal語(yǔ)言fpcfpcfpc注意事項(xiàng)：1、文件名（程序名和輸入輸出文件名）必須使用英文小寫。2、C/C+中函數(shù)main（）的返回值類型必須是int，程序正常結(jié)束時(shí)的返回值必須是0。3、全國(guó)統(tǒng)一評(píng)測(cè)時(shí)采用的機(jī)器配置為：CPUAMDAth

15、lon（tm）IIx2240processor,內(nèi)存4G,上述時(shí)限以此配置為準(zhǔn)。4、只提供Linux格式附加樣例文件。5、提交的程序代碼文件的放置位置請(qǐng)參照各省的具體要求。6、特別提醒：評(píng)測(cè)在當(dāng)前最新公布的NOILinux下進(jìn)行，各語(yǔ)言的編譯器版本以其為準(zhǔn)。c/pas)現(xiàn)有一塊大奶酪，它的高度為h,它的長(zhǎng)度和寬度我們可以認(rèn)為是無(wú)限大的，奶酪中間有許多半徑相同的球形空洞。我們可以在這塊奶酪中建立空間坐標(biāo)系，在坐標(biāo)系中，奶酪的下表面為z=0,奶酪的上表面為z=h?，F(xiàn)在，奶酪的下表面有一只小老鼠Jerry,它知道奶酪中所有空洞的球心所在的坐標(biāo)。如果兩個(gè)空洞相切或是相交，貝UJerry可以從其中一個(gè)空

16、洞跑到另一個(gè)空洞，特別地，如果一個(gè)空洞與下表面相切或是相交，Jerry則可以從奶酪下表面跑進(jìn)空洞；如果一個(gè)空洞與上表面相切或是相交，Jerry則可以從空洞跑到奶酪上表面。位丁奶酪下表面的Jerry想知道，在不破壞奶酪的情況下，能否利用已有的空洞跑到奶酪的上表面去？空間內(nèi)兩點(diǎn)？?1(?1,?1,?1)、?2(?2,?2,?2)的距離公式如下：dist(?1,?2)=V(?1?2)2+(?1?2)2+(?1?2)2【輸入格式】輸入文件名為。每個(gè)輸入文件包含多組數(shù)據(jù)。輸入文件的第一行，包含一個(gè)正整數(shù)T,代表該輸入文件中所含的數(shù)據(jù)組數(shù)。接下來(lái)是T組數(shù)據(jù)，每組數(shù)據(jù)的格式如下：第一行包含三個(gè)正整數(shù)n,h和

17、r,兩個(gè)數(shù)之間以一個(gè)空格分開，分別代表奶酪中空洞的數(shù)量，奶酪的高度和空洞的半徑。接下來(lái)的n行，每行包含三個(gè)整數(shù)x、y、z,兩個(gè)數(shù)之間以一個(gè)空格分開，表示空洞球心坐標(biāo)為(?,?,?)。【輸出格式】輸出文件名為。輸出文件包含T行，分別對(duì)應(yīng)T組數(shù)據(jù)的答案，如果在第i組數(shù)據(jù)中，Jerry能從下表面跑到上表面，則輸出“Yes”，如果不能，貝U輸出“No”(均不包含引號(hào))?！据斎胼敵鰳永?】3Yes241No001Yes003251001004252002204見(jiàn)選手目錄下的cheese/和cheese/?！据斎胼敵鰳永?說(shuō)明】第一組數(shù)據(jù)，由奶酪的剖面圖可見(jiàn)：第一個(gè)空洞在（0,0,0）與下表面相切第二個(gè)空

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

19、0,000。對(duì)于100%的數(shù)據(jù)，1<n<1,000,1<h,r<1,000,000,000,T<20,坐標(biāo)的絕對(duì)值不超過(guò)1,000,000,000?！締?wèn)題描述】2.寶藏（c/pas）參與考古挖掘的小明得到了一份藏寶圖，藏寶圖上標(biāo)出了n個(gè)深埋在地下的寶藏屋，也給出了這n個(gè)寶藏屋之間可供開發(fā)的m條道路和它們的長(zhǎng)度。小明決心親自前往挖掘所有寶藏屋中的寶藏。但是，每個(gè)寶藏屋距離地面都很遠(yuǎn)，也就是說(shuō)，從地面打通一條到某個(gè)寶藏屋的道路是很困難的，而開發(fā)寶藏屋之間的道路則相對(duì)容易很多。小明的決心感動(dòng)了考古挖掘的贊助商，贊助商決定免費(fèi)贊助他打通一條從地面到某個(gè)寶藏屋的通道，通往哪

20、個(gè)寶藏屋則由小明來(lái)決定。在此基礎(chǔ)上，小明還需要考慮如何開鑿寶藏屋之間的道路。已經(jīng)開鑿出的道路可以任意通行不消耗代價(jià)。每開鑿出一條新道路，小明就會(huì)與考古隊(duì)一起挖掘出由該條道路所能到達(dá)的寶藏屋的寶藏。另外，小明不想開發(fā)無(wú)用道路，即兩個(gè)已經(jīng)被挖掘過(guò)的寶藏屋之間的道路無(wú)需再開發(fā)。新開發(fā)一條道路的代價(jià)是：這條道路的長(zhǎng)度x從贊助商幫你打通的寶藏屋到這條道路起點(diǎn)的寶藏屋所經(jīng)過(guò)的寶藏屋的數(shù)量（包括贊助商幫你打通的寶藏屋和這條道路起點(diǎn)的寶藏屋）請(qǐng)你編寫程序?yàn)樾∶鬟x定由贊助商打通的寶藏屋和之后開鑿的道路，使得工程總代價(jià)最小，并輸出這個(gè)最小值?！据斎敫袷健枯斎胛募麨?。第一行兩個(gè)用空格分離的正整數(shù)n和m,代表寶藏屋

21、的個(gè)數(shù)和道路數(shù)。接下來(lái)m行，每行三個(gè)用空格分離的正整數(shù)，分別是由一條道路連接的兩個(gè)寶藏屋的編號(hào)（編號(hào)為1n），和這條道路的長(zhǎng)度Vo【輸出格式】輸出文件名為。輸出共一行，一個(gè)正整數(shù)，表示最小的總代價(jià)?！据斎胼敵鰳永?】451211331 412 343 414見(jiàn)選手目錄下的treasure/與treasure/【輸入輸出樣例1說(shuō)明】小明選定讓贊助商打通了1號(hào)寶藏屋。小明開發(fā)了道路1?2，挖掘了2號(hào)寶藏。開發(fā)了道路1?4，挖掘了4號(hào)寶藏。還開發(fā)了道路4?3，挖掘了3號(hào)寶藏。工程總代價(jià)為：1X1+1x1+1x2=4(1?2)(1?4)(4?3)【樣例輸入輸出2】451211331 412 343 4

22、25見(jiàn)選手目錄下的treasure/與treasure/?！据斎胼敵鰳永?說(shuō)明】小明選定讓贊助商打通了1號(hào)寶藏屋。小明開發(fā)了道路1?2，挖掘了2號(hào)寶藏。開發(fā)了道路1?3,挖掘了3號(hào)寶藏。還開發(fā)了道路1?4，挖掘了4號(hào)寶藏。工程總代價(jià)為：1x1+3x1+1x1=5(1?2)(1?3)(1?4)【輸入輸出樣例3】見(jiàn)選手目錄下的treasure/和treasure/【數(shù)據(jù)規(guī)模與約定】對(duì)于20%的數(shù)據(jù)：保證輸入是一棵樹，1Vn<8,v<5000且所有的v都相等。對(duì)于40%的數(shù)據(jù)：Kn<8,0<帕1000,v<5000且所有的v都相等。對(duì)于70%的數(shù)據(jù)：Kn<8,0&

23、lt;帕1000,v<5000對(duì)于100%的數(shù)據(jù)：Kn<12,0<詐1000,v<500000c/pas)Sylvia是一個(gè)熱愛(ài)學(xué)習(xí)的女孩子。前段時(shí)間,Sylvia參加了學(xué)校的軍訓(xùn)。眾所周知，軍訓(xùn)的時(shí)候需要站方陣。Sylvia所在的方陣中有nxm名學(xué)生，方陣的行數(shù)為n,歹0數(shù)為m。為了便丁管理，教官在訓(xùn)練開始時(shí)，按照從前到后，從左到右的順序給方陣中的學(xué)生從1到nxm編上了號(hào)碼(參見(jiàn)后面的樣例)。即：初始時(shí),第i行第j列的學(xué)生的編號(hào)是(i?1)xm+j。然而在練習(xí)方陣的時(shí)候，經(jīng)常會(huì)有學(xué)生因?yàn)楦鞣N各樣的事情需要離隊(duì)。在一天中，一共發(fā)生了q件這樣的離隊(duì)事件。每一次離隊(duì)事件可以用數(shù)對(duì)(?,?)(1<x<n,1<y<m#茁述，表示第x行第y歹U的學(xué)生離隊(duì)。在有學(xué)生離隊(duì)后，隊(duì)伍中出現(xiàn)了一個(gè)空位。為了