noip提高組復(fù)賽試題

《noip提高組復(fù)賽試題》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、全國(guó)信息學(xué)奧林匹克聯(lián)賽（NOIP2018）復(fù)賽提高組day2CCF全國(guó)信息學(xué)奧林匹克聯(lián)賽（NOIP2018）復(fù)賽提高組day2（請(qǐng)選手務(wù)必仔細(xì)閱讀本頁(yè)內(nèi)容）一．題目概況中文題目名稱旅行填數(shù)游戲保衛(wèi)王國(guó)英文題目與子目錄名travelgamedefense可執(zhí)行文件名travelgamedefense輸入文件名travel.ingame.indefense.in輸出文件名travel.outgame.outdefense.out每個(gè)測(cè)試點(diǎn)時(shí)限1s1s2s測(cè)試點(diǎn)數(shù)目252025每個(gè)測(cè)試點(diǎn)分值454附加樣例文件有有

2、有結(jié)果比較方式全文比較（過(guò)濾行末空格及文末回車）題目類型傳統(tǒng)傳統(tǒng)傳統(tǒng)運(yùn)行內(nèi)存上限512MB512MB512MB二．提交源程序文件名對(duì)于C++語(yǔ)言travel.cppgame.cppdefense.cpp對(duì)于C語(yǔ)言travel.cgame.cdefense.c對(duì)于pascal語(yǔ)言travel.pasgame.pasdefense.pas三．編譯命令（不包含任何優(yōu)化開(kāi)關(guān)）對(duì)于C++語(yǔ)言g++-otravelg++-ogamegame.cppg++-odefensetravel.cpp-lm-lmdefense.

3、cpp-lm對(duì)于C語(yǔ)言gcc-otraveltravel.cgcc-ogamegame.cgcc-odefense-lm-lmdefense.c-lm對(duì)于pascal語(yǔ)言fpctravel.pasfpcgame.pasfpcdefense.pas注意事項(xiàng)：1、文件名（程序名和輸入輸出文件名）必須使用英文小寫(xiě)。2、C/C++中函數(shù)main()的返回值類型必須是int，程序正常結(jié)束時(shí)的返回值必須是0。3、全國(guó)統(tǒng)一評(píng)測(cè)時(shí)采用的機(jī)器配置為：Intel(R)Core(TM)i7-8700KCPU@3.70GHz，內(nèi)存

4、32GB。上述時(shí)限以此配置為準(zhǔn)。4、只提供Linux格式附加樣例文件。5、特別提醒：評(píng)測(cè)在當(dāng)前最新公布的NOILinux下進(jìn)行，各語(yǔ)言的編譯器版本以其為準(zhǔn)。第1頁(yè)共8頁(yè)全國(guó)信息學(xué)奧林匹克聯(lián)賽（NOIP2018）復(fù)賽提高組day21．旅行(travel.cpp/c/pas)【問(wèn)題描述】小Y是一個(gè)愛(ài)好旅行的OIer。她來(lái)到X國(guó)，打算將各個(gè)城市都玩一遍。小Y了解到，X國(guó)的?個(gè)城市之間有?條雙向道路。每條雙向道路連接兩個(gè)城市。不存在兩條連接同一對(duì)城市的道路，也不存在一條連接一個(gè)城市和它本身的道路。并且，從任意一個(gè)城

5、市出發(fā)，通過(guò)這些道路都可以到達(dá)任意一個(gè)其他城市。小Y只能通過(guò)這些道路從一個(gè)城市前往另一個(gè)城市。小Y的旅行方案是這樣的：任意選定一個(gè)城市作為起點(diǎn)，然后從起點(diǎn)開(kāi)始，每次可以選擇一條與當(dāng)前城市相連的道路，走向一個(gè)沒(méi)有去過(guò)的城市，或者沿著第一次訪問(wèn)該城市時(shí)經(jīng)過(guò)的道路后退到上一個(gè)城市。當(dāng)小Y回到起點(diǎn)時(shí)，她可以選擇結(jié)束這次旅行或繼續(xù)旅行。需要注意的是，小Y要求在旅行方案中，每個(gè)城市都被訪問(wèn)到。為了讓自己的旅行更有意義，小Y決定在每到達(dá)一個(gè)新的城市（包括起點(diǎn)）時(shí)，將它的編號(hào)記錄下來(lái)。她知道這樣會(huì)形成一個(gè)長(zhǎng)度為?的序列。她

6、希望這個(gè)序列的字典序最小，你能幫幫她嗎？對(duì)于兩個(gè)長(zhǎng)度均為?的序列A和B，當(dāng)且僅當(dāng)存在一個(gè)正整數(shù)x，滿足以下條件時(shí)，我們說(shuō)序列A的字典序小于B。?對(duì)于任意正整數(shù)1≤i

7、?！据敵龈袷健枯敵鑫募麨閠ravel.out。輸出文件包含一行，?個(gè)整數(shù)，表示字典序最小的序列。相鄰兩個(gè)整數(shù)之間用一個(gè)空格分隔?！据斎胼敵鰳永?】travel.intravel.out651325461323253446見(jiàn)選手目錄下的travel/travel1.in和travel/travel1.ans。第2頁(yè)共8頁(yè)全國(guó)信息學(xué)奧林匹克聯(lián)賽（NOIP2018）復(fù)賽提高組day2【輸入輸出樣例2】travel.intravel.out66132456132325344546見(jiàn)選手目錄下的travel/tra

8、vel2.in和travel/travel2.ans。【輸入輸出樣例3】見(jiàn)選手目錄下的travel/travel3.in和travel/travel3.ans。這組樣例滿足?=??1?！据斎胼敵鰳永?】見(jiàn)選手目錄下的travel/travel4.in和travel/travel4.ans。這組樣例滿足?=?。【數(shù)據(jù)規(guī)模與約定】對(duì)于100%的數(shù)據(jù)和所有樣例，1≤?≤5000且?=??1或?=?。對(duì)于不同的測(cè)試點(diǎn)，我