1、全國(guó)信息學(xué)奧林匹克聯(lián)賽（2017）復(fù)賽提高組1（請(qǐng)選手務(wù)必仔細(xì)閱讀本頁(yè)內(nèi)容）一.題目概況中文題目名稱小凱的疑惑時(shí)間復(fù)雜度逛公園央文題目與子目錄名:可執(zhí)行文件名輸入文件名輸出文件名每個(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ì)于語(yǔ)言對(duì)于C語(yǔ)言對(duì)于語(yǔ)言三.編譯命令（不包含任何優(yōu)化開(kāi)關(guān)）對(duì)于語(yǔ)言對(duì)于C語(yǔ)言對(duì)于語(yǔ)言注意事項(xiàng)：1、文件名（程序名和輸入輸出文件名）必須使用英文小寫。2、中函數(shù)（）的返回值類型必須是，程序正常結(jié)束時(shí)的返回值必須

2、是0。3、全國(guó)統(tǒng)一評(píng)測(cè)時(shí)采用的機(jī)器配置為：（）x2240,2.8,內(nèi)存4G,上述時(shí)限以此配置為準(zhǔn)。4、只提供格式附加樣例文件。5、提交的程序代碼文件的放置位置請(qǐng)參照各省的具體要求。下進(jìn)行，各語(yǔ)言的編譯6、特別提醒：評(píng)測(cè)在當(dāng)前最新公布的器版本以其為準(zhǔn)。1. 小凱的疑惑()【問(wèn)題描述】小凱手中有兩種面值的金幣，兩種面值均為正整數(shù)且彼此互素。每種金幣小凱都有無(wú)數(shù)個(gè)。在不找零的情況下，僅憑這兩種金幣，有些物品他是無(wú)法準(zhǔn)確支付的。現(xiàn)在小凱想知道在無(wú)法準(zhǔn)確支付的物品中，最貴的價(jià)值是多少金幣？注意：輸入數(shù)據(jù)保證存在小凱無(wú)法準(zhǔn)確支付的商品?！据斎敫袷健枯斎胛募麨椤］斎霐?shù)據(jù)僅一行，包含兩個(gè)正整數(shù)a和b,它們之

3、間用一個(gè)空格隔開(kāi)，表示小凱手中金幣的面值?！据敵龈袷健枯敵鑫募麨?。輸出文件僅一行，一個(gè)正整數(shù)N,表示不找零的情況下，小凱用手中的金幣不能準(zhǔn)確支付的最貴的物品的價(jià)值?！据斎胼敵鰳永?】3711見(jiàn)選手目錄下的1和1【輸入輸出樣例1說(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)選手目錄下的2和2。50。10,000。1,000,000,000?！緮?shù)據(jù)規(guī)模與約定】對(duì)于30%的數(shù)

4、據(jù)：1<a,b對(duì)于60%的數(shù)據(jù)：1<a,b對(duì)于100%的數(shù)據(jù)：1<a,b2.時(shí)間復(fù)雜度()【問(wèn)題描述】小明正在學(xué)習(xí)一種新的編程語(yǔ)言，剛學(xué)會(huì)循環(huán)語(yǔ)句的他激動(dòng)地寫了好多程序并給出了他自己算出的時(shí)間復(fù)雜度，可他的編程老師實(shí)在不想一個(gè)一個(gè)檢查小明的程序，于是你的機(jī)會(huì)來(lái)啦！下面請(qǐng)你編寫程序來(lái)判斷小明對(duì)他的每個(gè)程序給出的時(shí)間復(fù)雜度是否正確。語(yǔ)言的循環(huán)結(jié)構(gòu)如下：Fixy循環(huán)體堡中“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ù)

5、(x和y的大小關(guān)系不定)或變量non是一個(gè)表示數(shù)據(jù)規(guī)模的變量，在時(shí)間復(fù)雜度計(jì)算中需保留該變量而不能將其視為常數(shù)，該數(shù)遠(yuǎn)大于100?！癊T表示循環(huán)體結(jié)束。循環(huán)體結(jié)束時(shí)，這個(gè)循環(huán)體新建的變量也被銷毀。注：本題中為了書(shū)寫方便，在描述復(fù)雜度時(shí)，使用大寫英文字母“。表示通常意義下的概念。【輸入格式】輸入文件名為。輸入文件第一行一個(gè)正整數(shù)t,表示有t(tw10)個(gè)程序需要計(jì)算時(shí)間復(fù)雜度。每個(gè)程序我們只需抽取其中“Fixy”和“ET即可計(jì)算時(shí)間復(fù)雜度。注意：循環(huán)結(jié)構(gòu)允許嵌套。接下來(lái)每個(gè)程序的第一行包含一個(gè)正整數(shù)L和一個(gè)字符串，L代表程序行數(shù)，字符串表示這個(gè)程序的復(fù)雜度，“0（1）”表示常數(shù)復(fù)雜度，“0（&q

6、uot;w）”表示復(fù)雜度為？?”，其中w是一個(gè)小于100的正整數(shù)（輸入中不包含引號(hào)），輸入保證復(fù)雜度只有0（1）和0（nAw）兩種類型。接下來(lái)L行代表程序中循環(huán)結(jié)構(gòu)中的“Fixy”或者“E”。程序行若以“F'開(kāi)頭，表示進(jìn)入一個(gè)循環(huán)，之后有空格分離的三個(gè)字符（串）ixy,其中i是一個(gè)小寫字母（保證不為“n”），表示新建的變量名，x和y可能是正整數(shù)或n,已知若為正整數(shù)則一定小于100。程序行若以“E”開(kāi)頭，則表示循環(huán)體結(jié)束?！据敵龈袷健枯敵鑫募麨?。輸出文件共t行，對(duì)應(yīng)輸入的t個(gè)程序，每行輸出或或者（輸出中不包含引號(hào)），若程序?qū)嶋H復(fù)雜度與輸入給出的復(fù)雜度一致則輸出“”，不一致則輸出“”，若

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

8、四個(gè)程序二重循環(huán)，n的平方的復(fù)雜度。第五個(gè)程序兩個(gè)一重循環(huán)，n的一次方的復(fù)雜度。第六個(gè)程序第一重循環(huán)正常，但第二重循環(huán)開(kāi)始即終止（因?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ò)誤，輸出【輸入輸出樣例2】見(jiàn)選手目錄下的2和2?！緮?shù)據(jù)規(guī)模與約定】對(duì)于30%的數(shù)據(jù)：不存在語(yǔ)法錯(cuò)誤，數(shù)據(jù)保證小明給出的每個(gè)程序的前2行一定為以F開(kāi)頭的語(yǔ)句，第2+1行至第L行一定為以E開(kāi)頭的語(yǔ)句，L<=10,若x、y均為整數(shù)，x一定小于y,且只有y有可能為n。對(duì)于50%的數(shù)據(jù)：不存在語(yǔ)法錯(cuò)誤，L<=10Q且若

9、x、y均為整數(shù)，x一定小于y,且只有y有可能為n。對(duì)于70%的數(shù)據(jù)：不存在語(yǔ)法錯(cuò)誤，L<=100。對(duì)于100%的數(shù)據(jù)：L<=100。3. 逛公園()【問(wèn)題描述】策策同學(xué)特別喜歡逛公園。公園可以看成一張？?個(gè)點(diǎn)？?條邊構(gòu)成的有向圖，且沒(méi)有自環(huán)和重邊。其中1號(hào)點(diǎn)是公園的入口，?號(hào)點(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í)策策還是一個(gè)特別熱愛(ài)學(xué)習(xí)的好孩子，他不希望每天在逛公園這件事上花費(fèi)太多的時(shí)間。如果1號(hào)點(diǎn)到？?號(hào)點(diǎn)的最短路長(zhǎng)為？，那么策策只

10、會(huì)喜歡長(zhǎng)度不超過(guò)？+?的路線。策策同學(xué)想知道總共有多少條滿足條件的路線，你能幫幫他嗎？為避免輸出過(guò)大，答案對(duì)？?取模。如果有無(wú)窮多條合法的路線，請(qǐng)輸出-1?！据斎敫袷健枯斎胛募麨?。第一行包含一個(gè)整數(shù)？?，代表數(shù)據(jù)組數(shù)。接下來(lái)？酒數(shù)據(jù)，對(duì)于每組數(shù)據(jù)：第一行包含四個(gè)整數(shù)？?，?,?,?,每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開(kāi)。接下來(lái)？?行，每行三個(gè)整數(shù)?,?,?,代表編號(hào)為?,?的點(diǎn)之間有一條權(quán)值為?的有向邊，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開(kāi)?！据敵龈袷健枯敵鑫募麨椤］敵鑫募?？?行，每行一個(gè)整數(shù)代表答案?！据斎胼敵鰳永?】2572101 212 404522 323 413521 532 20101 2

11、02 103-1見(jiàn)選手目錄下的1和1。對(duì)于第一組數(shù)據(jù)，最短路為3。1-5,1-2-4-5,1-2-3-5為3條合法路徑。【輸入輸出樣例2】見(jiàn)選手目錄下的2和2?！緮?shù)據(jù)規(guī)模與約定】對(duì)于不同的測(cè)試點(diǎn)，我們約定各種參數(shù)的規(guī)模不會(huì)超過(guò)如下測(cè)試點(diǎn)編號(hào)?是否有0邊155100否25100020000否351000200050否451000200050否551000200050否651000200050是751000002000000否8310000020000050否9310000020000050是10310000020000050是對(duì)于100%的數(shù)據(jù),1W?W109,1W?,?W?0V?w1000O數(shù)

12、據(jù)保證：至少存在一條合法的路線。全國(guó)信息學(xué)奧林匹克聯(lián)賽（2017）復(fù)賽提高組2（請(qǐng)選手務(wù)必仔細(xì)閱讀本頁(yè)內(nèi)容）.題目概況中文題目名稱奶酪寶藏列隊(duì)央文題目與子目錄名:可執(zhí)行文件名輸入文件名輸出文件名每個(gè)測(cè)試點(diǎn)時(shí)限1秒1秒2秒測(cè)試點(diǎn)數(shù)目102020每個(gè)測(cè)試點(diǎn)分值1055附加樣例文件有有有結(jié)果比較方式全文比較（過(guò)濾行末空格及文末回車）題目類型傳統(tǒng)傳統(tǒng)傳統(tǒng)運(yùn)行內(nèi)存上限256M256M512M二.提交源程序文件名對(duì)于語(yǔ)言對(duì)于C語(yǔ)言對(duì)于語(yǔ)言三.編譯命令（不包含任何優(yōu)化開(kāi)關(guān)）對(duì)于語(yǔ)言對(duì)于C語(yǔ)言對(duì)于語(yǔ)言注意事項(xiàng)：1、文件名（程序名和輸入輸出文件名）必須使用英文小寫。2、中函數(shù)（）的返回值類型必須是，程序正常結(jié)束

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

14、洞跑到另一個(gè)空洞，特別地，如果一個(gè)空洞與下表面相切或是相交，則可以從奶酪下表面跑進(jìn)空洞；如果一個(gè)空洞與上表面相切或是相交，則可以從空洞跑到奶酪上表面。位于奶酪下表面的想知道，在不破壞奶酪的情況下，能否利用已有的空洞跑到奶酪的上表面去？空間內(nèi)兩點(diǎn)？1(?1,?1,?1)、?2(?2,?2,?2)的距離公式如下：(?1,?2)=(?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和r,兩個(gè)數(shù)之間以一個(gè)空格分開(kāi)，分別代

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

16、既不相交也不相切輸出第三組數(shù)據(jù)，由奶酪的剖面圖可見(jiàn)：兩個(gè)空洞相交且與上下表面相切或相交輸出【輸入輸出樣例2】見(jiàn)選手目錄下的2和2【數(shù)據(jù)規(guī)模與約定】對(duì)于20%的數(shù)據(jù)，n=1,1wh,r<10,000,坐標(biāo)的絕對(duì)值不超過(guò)10,000。對(duì)于40%的數(shù)據(jù)，1wn<8,1wh,r<10,000,坐標(biāo)的絕對(duì)值不超過(guò)10,000。對(duì)于80%的數(shù)據(jù)，1wnw1,000,1wh,rw10,000,坐標(biāo)的絕對(duì)值不超過(guò)10,000。對(duì)于100%的數(shù)據(jù)，1wnw1,000,1wh,rw1,000,000,000,TV20,坐標(biāo)的絕對(duì)值不超過(guò)1,000,000,000。、（）【問(wèn)題描述】參與考古挖掘的

17、小明得到了一份藏寶圖，藏寶圖上標(biāo)出了n個(gè)深埋在地下的寶藏屋，也給出了這n個(gè)寶藏屋之間可供開(kāi)發(fā)的m條道路和它們的長(zhǎng)度。小明決心親自前往挖掘所有寶藏屋中的寶藏。但是，每個(gè)寶藏屋距離地面都很遠(yuǎn)，也就是說(shuō)，從地面打通一條到某個(gè)寶藏屋的道路是很困難的，而開(kāi)發(fā)寶藏屋之間的道路則相對(duì)容易很多。小明的決心感動(dòng)了考古挖掘的贊助商，贊助商決定免費(fèi)贊助他打通一條從地面到某個(gè)寶藏屋的通道，通往哪個(gè)寶藏屋則由小明來(lái)決定。在此基礎(chǔ)上，小明還需要考慮如何開(kāi)鑿寶藏屋之間的道路。已經(jīng)開(kāi)鑿出的道路可以任意通行不消耗代價(jià)。每開(kāi)鑿出一條新道路，小明就會(huì)與考古隊(duì)一起挖掘出由該條道路所能到達(dá)的寶藏屋的寶藏。另外，小明不想開(kāi)發(fā)無(wú)用道路，即

18、兩個(gè)已經(jīng)被挖掘過(guò)的寶藏屋之間的道路無(wú)需再開(kāi)發(fā)。新開(kāi)發(fā)一條道路的代價(jià)是：這條道路的長(zhǎng)度x從贊助商幫你打通的寶藏屋到這條道路起點(diǎn)的寶藏屋所經(jīng)過(guò)的寶藏屋的數(shù)量（包括贊助商幫你打通的寶藏屋和這條道路起點(diǎn)的寶藏屋）。請(qǐng)你編寫程序?yàn)樾∶鬟x定由贊助商打通的寶藏屋和之后開(kāi)鑿的道路，使得工程總代價(jià)最小，并輸出這個(gè)最小值?！据斎敫袷健枯斎胛募麨?。第一行兩個(gè)用空格分離的正整數(shù)n和m,代表寶藏屋的個(gè)數(shù)和道路數(shù)。接下來(lái)m行，每行三個(gè)用空格分離的正整數(shù)，分別是由一條道路連接的兩個(gè)寶藏屋的編號(hào)（編號(hào)為1）,和這條道路的長(zhǎng)度V?！据敵龈袷健枯敵鑫募麨檩敵龉惨恍?，一個(gè)正整數(shù)，表示最小的總代價(jià)?！据斎胼敵鰳永?】454121

19、133141234341見(jiàn)選手目錄下的1與1【輸入輸出樣例1說(shuō)明】小明選定讓贊助商打通了1號(hào)寶藏屋。小明開(kāi)發(fā)了道路12,挖掘了2號(hào)寶藏。開(kāi)發(fā)了道路14,挖掘了4號(hào)寶藏。還開(kāi)發(fā)了道路43,挖掘了3號(hào)寶藏。工程總代價(jià)為：1X1+1X1+1X2=4(12)(14)(43)【樣例輸入輸出2】455121133141234342見(jiàn)選手目錄下的2與2【輸入輸出樣例2說(shuō)明】小明選定讓贊助商打通了1號(hào)寶藏屋。小明開(kāi)發(fā)了道路12,挖掘了2號(hào)寶藏。開(kāi)發(fā)了道路13,挖掘了3號(hào)寶藏。還開(kāi)發(fā)了道路14,挖掘了4號(hào)寶藏。工程總代價(jià)為：1X13X1+1X1=5(12)(13)(14)【輸入輸出樣例3】見(jiàn)選手目錄下的3和3。

20、【數(shù)據(jù)規(guī)模與約定】對(duì)于20%的數(shù)據(jù)：保證輸入是一棵樹(shù)，1WnW8,v<5000且所有的v都相等。對(duì)于40%的數(shù)據(jù)：KnW8,0<帷1000,v<5000且所有的v都相等。對(duì)于70%的數(shù)據(jù)：KnW8,0<帷1000,v<5000對(duì)于100%的數(shù)據(jù)：KnW12,0<帷1000,v<5000003.列隊(duì)()【問(wèn)題描述】是一個(gè)熱愛(ài)學(xué)習(xí)的女孩子。前段時(shí)間，參加了學(xué)校的軍訓(xùn)。眾所周知，軍訓(xùn)的時(shí)候需要站方陣。所在的方陣中有nx仙學(xué)生，方陣的行數(shù)為n,列數(shù)為m。為了便于管理，教官在訓(xùn)練開(kāi)始時(shí)，按照從前到后，從左到右的順序給方陣中的學(xué)生從1到nxm編上了號(hào)碼(參見(jiàn)后面的

21、樣例)。即：初始時(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ì)(?,?)(1wx<n,1wywm)描述，表示第x行第y列的學(xué)生離隊(duì)。在有學(xué)生離隊(duì)后，隊(duì)伍中出現(xiàn)了一個(gè)空位。為了隊(duì)伍的整齊，教官會(huì)依次下達(dá)這樣的兩條指令：1. 向左看齊。這時(shí)第一列保持不動(dòng)，所有學(xué)生向左填補(bǔ)空缺。不難發(fā)現(xiàn)在這條指令之后，空位在第x行第m列。2. 向前看齊。這時(shí)第一行保持不動(dòng)，所有學(xué)生向前填補(bǔ)空缺。不難發(fā)現(xiàn)在這條指令之后，空位在第n行第m列。教官規(guī)定不能有兩個(gè)或更多學(xué)生同時(shí)離隊(duì)。即在前一個(gè)離隊(duì)的學(xué)生歸隊(duì)之后，下一個(gè)學(xué)生才能離隊(duì)。因此在每一個(gè)離隊(duì)的學(xué)生要?dú)w隊(duì)時(shí)，隊(duì)伍中有且僅有第n行第m列一個(gè)空位,這時(shí)這個(gè)學(xué)生會(huì)自然地填補(bǔ)到這個(gè)位置。因?yàn)檎痉疥囌娴暮軣o(wú)聊，所以想要計(jì)算每一次離隊(duì)事件中，離隊(duì)的同學(xué)的編號(hào)是多少。注意：每一個(gè)同學(xué)的編號(hào)不會(huì)隨著離隊(duì)事件的發(fā)生而改變，在