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

CCF全國(guó)信息學(xué)奧林匹克聯(lián)賽（NOIP2014）復(fù)賽提高組dayl（請(qǐng)選手務(wù)必仔細(xì)閱讀本頁(yè)內(nèi)容）.題目概況中文題目名稱(chēng)生活大爆炸版石頭剪刀布聯(lián)合權(quán)值飛揚(yáng)的小鳥(niǎo)英文題目與子目錄名rpslinkbird可執(zhí)行文件名rpslinkbird輸入文件名rps.inlink.inbird.in輸出文件名rps.outlink.outbird.out每個(gè)測(cè)試點(diǎn)時(shí)限1秒1秒1秒測(cè)試點(diǎn)數(shù)目101020每個(gè)測(cè)試點(diǎn)分值10105附加樣例文件有有有結(jié)果比較方式全文比較（過(guò)濾行末空格及文末回車(chē)）題目類(lèi)型傳統(tǒng)傳統(tǒng)傳統(tǒng)運(yùn)行內(nèi)存上限128M128M128M二.交源程序文件名對(duì)于C++語(yǔ)言rps.cpplink.cppbird.cpp對(duì)于C語(yǔ)言rps.clink.cbird.c對(duì)于pascal語(yǔ)言rps.paslink.pasbird.pas三.編譯命令（不包含任何優(yōu)化開(kāi)關(guān)）對(duì)于C++語(yǔ)言g++-orpsrps.cpp-lmg++-olinklink.cpp-lmg++-obirdbird.cpp-lm對(duì)于C語(yǔ)言gcc-orpsrps.c-lmgcc-olinklink.c-lmgcc-obirdbird.c-lm對(duì)于pascal語(yǔ)言fpcrps.pasfpclink.pasfpcbird.pas注意事項(xiàng)：1、文件名（程序名和輸入輸出文件名）必須使用英文小寫(xiě)。2、C/C++中函數(shù)main（）的返回值類(lèi)型必須是int,程序正常結(jié)束時(shí)的返回值必須是0。3、全國(guó)統(tǒng)一評(píng)測(cè)時(shí)采用的機(jī)器配置為：CPUAMDAthlon（tm）64x2DualCoreCPU5200+,2.71GHz,內(nèi)存2G,上述時(shí)限以此配置為準(zhǔn)。4、只供Linux格式附加樣例文件。5、特別提醒：評(píng)測(cè)在當(dāng)前最新公布的NOILinux下進(jìn)行，各語(yǔ)言的編譯器版本以其為準(zhǔn)。.生活大爆炸版石頭剪刀布(rps.cpp/c/pas)【問(wèn)題描述】石頭剪刀布是常見(jiàn)的猜拳游戲：石頭勝剪刀，剪刀勝布，布勝石頭。如果兩個(gè)人出拳一樣，則不分勝負(fù)。在《生活大爆炸》第二季第8集中出現(xiàn)了一種石頭剪刀布的升級(jí)版游戲。升級(jí)版游戲在傳統(tǒng)的石頭剪刀布游戲的基礎(chǔ)上，增加了兩個(gè)新手勢(shì)：斯波克：《星際迷航》主角之一。蜥蜴人：《星際迷航》中的反面角色。這五種手勢(shì)的勝負(fù)關(guān)系如表一所示，表中列出的是甲對(duì)乙的游戲結(jié)果。表一石頭剪刀布升級(jí)版勝負(fù)關(guān)系\甲對(duì)乙的-甲、結(jié)果剪刀石頭布蜥蜴人斯波克剪刀平輸贏贏輸石頭平輸贏輸布平輸贏蜥蜴人平贏斯波克平現(xiàn)在，小A和小B嘗試玩這種升級(jí)版的猜拳游戲。已知他們的出拳都是有周期性規(guī)律的，但周期長(zhǎng)度不一定相等。例如：如果小A以“石頭-布-石頭-剪刀-蜥蜴人-斯波克”長(zhǎng)度為6的周期出拳，那么他的出拳序列就是“石頭■布-石頭-剪刀-蜥蜴人-斯波克-石頭-布-石頭-剪刀-蜥蜴人-斯波克-……”，而如果小B以“剪刀-石頭-布-斯波克-蜥蜴人”長(zhǎng)度為5的周期出拳，那么他出拳的序列就是“剪刀-石頭-布-斯波克-蜥蜴人-剪刀-石頭-布-斯波克-蜥蜴人-”已知小A和小B一共進(jìn)行N次猜拳。每一次贏的人得1分，輸?shù)牡?分；平局兩人都得0分。現(xiàn)請(qǐng)你統(tǒng)計(jì)N次猜拳結(jié)束之后兩人的得分?！据斎搿枯斎胛募麨閞ps.in。第一行包含三個(gè)整數(shù)：N，NA，NB，分別表示共進(jìn)行N次猜拳、小A出拳的周期長(zhǎng)度，小B出拳的周期長(zhǎng)度。數(shù)與數(shù)之間以一個(gè)空格分隔。第二行包含NA個(gè)整數(shù)，表示小A出拳的規(guī)律，第三行包含NB個(gè)整數(shù)，表示小B出拳的規(guī)律。其中，0表示“剪刀”，1表示“石頭”，2表示“布”，3表示“蜥蜴人”，4表示“斯波克”。數(shù)與數(shù)之間以一個(gè)空格分隔。【輸出】輸出文件名為rps.out。輸出一行，包含兩個(gè)整數(shù)，以一個(gè)空格分隔，分別表示小A、小B的得分。【輸入輸出樣例1】rps.inrps.out10560123403421062【輸入輸出樣例2】rps.inrps.out955012341032444【數(shù)據(jù)說(shuō)明】對(duì)于100%的數(shù)據(jù)，0<NW200,0<NAW200,0<NBW200。.聯(lián)合權(quán)值(link.cpp/c/pas)【問(wèn)題描述】無(wú)向連通圖G有n個(gè)點(diǎn)，n-1條邊。點(diǎn)從1到n依次編號(hào)，編號(hào)為i的點(diǎn)的權(quán)值為Wi，每條邊的長(zhǎng)度均為1。圖上兩點(diǎn)(u,v)的距離定義為u點(diǎn)到v點(diǎn)的最短距離。對(duì)于圖G上的點(diǎn)對(duì)(u,v)，若它們的距離為2,則它們之間會(huì)產(chǎn)生WuXWv的聯(lián)合權(quán)值。請(qǐng)問(wèn)圖G上所有可產(chǎn)生聯(lián)合權(quán)值的有序點(diǎn)對(duì)中，聯(lián)合權(quán)值最大的是多少？所有聯(lián)合權(quán)值之和是多少？【輸入】輸入文件名為link.in。第一行包含1個(gè)整數(shù)n。接下來(lái)n-1行，每行包含2個(gè)用空格隔開(kāi)的正整數(shù)u、v，表示編號(hào)為u和編號(hào)為v的點(diǎn)之間有邊相連。最后1行，包含n個(gè)正整數(shù)，每?jī)蓚€(gè)正整數(shù)之間用一個(gè)空格隔開(kāi)，其中第i個(gè)整數(shù)表示圖G上編號(hào)為i的點(diǎn)的權(quán)值為Wi。【輸出】輸出文件名為link.out。

輸出共1行，包含2個(gè)整數(shù)，之間用一個(gè)空格隔開(kāi)，依次為圖G上聯(lián)合權(quán)值的最大值和所有聯(lián)合權(quán)值之和。由于所有聯(lián)合權(quán)值之和可能很大，輸出它時(shí)要對(duì)10007取余?！据斎胼敵鰳永縧ink.inlink.out523451523102074【樣例說(shuō)明】本例輸入的圖如上所示，距離為2的有序點(diǎn)對(duì)有（1,3）、（2,4）、（3,1）、（3,5）、（4,2）、（5,3）。其聯(lián)合權(quán)值分別為2、15、2、20、15、20。其中最大的是20，總和為74。【數(shù)據(jù)說(shuō)明】對(duì)于30%的數(shù)據(jù)，1<W100；對(duì)于60%的數(shù)據(jù)，1?2000；對(duì)于100%的數(shù)據(jù)，1?200,000，0<Wi<10,00003.飛揚(yáng)的小鳥(niǎo)

(bird.cpp/c/pas)【問(wèn)題描述】FlappyBird是一款風(fēng)靡一時(shí)的休閑手機(jī)游戲。玩家需要不斷控制點(diǎn)擊手機(jī)屏幕的頻率來(lái)調(diào)節(jié)小鳥(niǎo)的飛行高度，讓小鳥(niǎo)順利通過(guò)畫(huà)面右方的管道縫隙。如果小鳥(niǎo)一不小心撞到了水管或者掉在地上的話，便宣告失敗。為了簡(jiǎn)化問(wèn)題，我們對(duì)游戲規(guī)則進(jìn)行了簡(jiǎn)化和改編：游戲界面是一個(gè)長(zhǎng)為n，高為m的二維平面，其中有k個(gè)管道（忽略管道的寬度）。小鳥(niǎo)始終在游戲界面內(nèi)移動(dòng)。小鳥(niǎo)從游戲界面最左邊任意整數(shù)高度位置出發(fā)，到達(dá)游戲界面最右邊時(shí)，游戲完成。小鳥(niǎo)每個(gè)單位時(shí)間沿橫坐標(biāo)方向右移的距離為1，豎直移動(dòng)的距離由玩家控制。如果點(diǎn)擊屏幕，小鳥(niǎo)就會(huì)上升一定高度X，每個(gè)單位時(shí)間可以點(diǎn)擊多次，效果疊加；如果不點(diǎn)擊屏幕，小鳥(niǎo)就會(huì)下降一定高度Y。小鳥(niǎo)位于橫坐標(biāo)方向不同位置時(shí)，上升的高度X和下降的高度Y可能互不相同。小鳥(niǎo)高度等于0或者小鳥(niǎo)碰到管道時(shí)，游戲失敗。小鳥(niǎo)高度為m時(shí)，無(wú)法再上升?，F(xiàn)在，請(qǐng)你判斷是否可以完成游戲。如果可以，輸出最少點(diǎn)擊屏幕數(shù)；否則，輸出小鳥(niǎo)最多可以通過(guò)多少個(gè)管道縫隙。【輸入】輸入文件名為bird.in。第1行有3個(gè)整數(shù)n，m，k，分別表示游戲界面的長(zhǎng)度，高度和水管的數(shù)量，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開(kāi)；接下來(lái)的n行，每行2個(gè)用一個(gè)空格隔開(kāi)的整數(shù)X和Y，依次表示在橫坐標(biāo)位置0~n-1上玩家點(diǎn)擊屏幕后，小鳥(niǎo)在下一位置上升的高度X，以及在這個(gè)位置上玩家不點(diǎn)擊屏幕時(shí)，小鳥(niǎo)在下一位置下降的高度Y。接下來(lái)k行，每行3個(gè)整數(shù)P，L，H，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開(kāi)。每行表示一個(gè)管道，其中P表示管道的橫坐標(biāo)，L表示此管道縫隙的下邊沿高度為L(zhǎng)，H表示管道縫隙上邊沿的高度（輸入數(shù)據(jù)保證P各不相同，但不保證按照大小順序給出）?！据敵觥枯敵鑫募麨閎ird.out。共兩行。第一行，包含一個(gè)整數(shù)，如果可以成功完成游戲，則輸出1，否則輸出0。第二行，包含一個(gè)整數(shù)，如果第一行為1，則輸出成功完成游戲需要最少點(diǎn)擊屏幕數(shù)，否則，輸出小鳥(niǎo)最多可以通過(guò)多少個(gè)管道縫隙。

【輸入輸出樣例1】bird.inbird.out101063999121321216212715355879136【輸入輸出樣例2】bird.inbird.out10104231218821212121026799148100【輸入輸出樣例說(shuō)明】如下圖所示，藍(lán)色直線表示小鳥(niǎo)的飛行軌跡，紅色直線表示管道。

【數(shù)據(jù)范圍】對(duì)于30%的數(shù)據(jù)：5WnW10,5WmW10,k=0,保證存在一組最優(yōu)解使得同一單位時(shí)間最多點(diǎn)擊屏幕3次；對(duì)于50%的數(shù)據(jù)：5WnW20,5WmW10，保證存在一組最優(yōu)解使得同一單位時(shí)間最多點(diǎn)擊屏幕3次；對(duì)于70%的數(shù)據(jù)：5WnW1000,5WmW100；對(duì)于100%的數(shù)據(jù)：5WnW10000,5WmW1000,0Wk<n,0<X<m,0<Y<m,0<P<n,0WL<HWm,L+1<H。CCF全國(guó)信息學(xué)奧林匹克聯(lián)賽（NOIP2014）復(fù)賽提高組day2（請(qǐng)選手務(wù)必仔細(xì)閱讀本頁(yè)內(nèi)容）.題目概況中文題目名稱(chēng)無(wú)線網(wǎng)路發(fā)射器選址尋找道路解方程英文題目與子目錄名wirelessroadequation可執(zhí)行文件名wirelessroadequation輸入文件名wireless.inroad.inequation.in輸出文件名wireless.outroad.outequation.out每個(gè)測(cè)試點(diǎn)時(shí)限1秒1秒1秒測(cè)試點(diǎn)數(shù)目101020每個(gè)測(cè)試點(diǎn)分值10105附加樣例文件有有有結(jié)果比較方式全文比較（過(guò)濾行末空格及文末回車(chē)）題目類(lèi)型傳統(tǒng)傳統(tǒng)傳統(tǒng)運(yùn)行內(nèi)存上限128M128M128M二.交源程序文件名對(duì)于C++語(yǔ)言wireless.cpproad.cppequation.cpp對(duì)于C語(yǔ)言wireless.croad.cequation.c對(duì)于pascal語(yǔ)言wireless.pasroad.pasequation.pas三.編譯命令（不包含任何優(yōu)化開(kāi)關(guān)）對(duì)于C++語(yǔ)言g++-owirelesswireless.cpp-lmg++-oroadroad.cpp-lmg++-oequationequation.cpp-lm對(duì)于C語(yǔ)言gcc-owirelesswireless.c-lmgcc-oroadroad.c-lmgcc-oequationequation.c-lm對(duì)于pascal語(yǔ)言fpcwireless.pasfpcroad.pasfpcequation.pas注意事項(xiàng)：1、文件名（程序名和輸入輸出文件名）必須使用英文小寫(xiě)。2、C/C++中函數(shù)main（）的返回值類(lèi)型必須是int,程序正常結(jié)束時(shí)的返回值必須是0。3、全國(guó)統(tǒng)一評(píng)測(cè)時(shí)采用的機(jī)器配置為：CPUAMDAthlon（tm）64x2DualCoreCPU5200+,2.71GHz,內(nèi)存2G,上述時(shí)限以此配置為準(zhǔn)。4、只供Linux格式附加樣例文件。5、特別提醒：評(píng)測(cè)在當(dāng)前最新公布的NOILinux下進(jìn)行，各語(yǔ)言的編譯器版本以其為準(zhǔn)。

1.無(wú)線網(wǎng)絡(luò)發(fā)射器選址(wireless.cpp/c/pas)【問(wèn)題描述】隨著智能手機(jī)的日益普及，人們對(duì)無(wú)線網(wǎng)的需求日益增大。某城市決定對(duì)城市內(nèi)的公共場(chǎng)所覆蓋無(wú)線網(wǎng)。假設(shè)該城市的布局為由嚴(yán)格平行的129條東西向街道和129條南北向街道所形成的網(wǎng)格狀，并且相鄰的平行街道之間的距離都是恒定值1。東西向街道從北到南依次編號(hào)為0,1,2…128,南北向街道從西到東依次編號(hào)為0,1,2?128。東西向街道和南北向街道相交形成路口，規(guī)定編號(hào)為x的南北向街道和編號(hào)為y的東西向街道形成的路口的坐標(biāo)是(x,y)。在某些路口存在一定數(shù)量的公共場(chǎng)所。由于政府財(cái)政問(wèn)題，只能安裝一個(gè)大型無(wú)線網(wǎng)絡(luò)發(fā)射器。該無(wú)線網(wǎng)絡(luò)發(fā)射器的傳播范圍是一個(gè)以該點(diǎn)為中心，邊長(zhǎng)為2*d的正方形。傳播范圍包括正方形邊界。例如下圖是一個(gè)d=1的無(wú)線網(wǎng)絡(luò)發(fā)射器的覆蓋范圍示意圖。亨無(wú)線網(wǎng)絡(luò)發(fā)射器安裝地點(diǎn)L.J無(wú)線網(wǎng)絡(luò)發(fā)射器覆蓋范圍▲存在公共場(chǎng)所的路口現(xiàn)在政府有關(guān)部門(mén)準(zhǔn)備安裝一個(gè)傳播參數(shù)為d的無(wú)線網(wǎng)絡(luò)發(fā)射器，希望你幫助他們?cè)诔鞘袃?nèi)找出合適的安裝地點(diǎn)，使得覆蓋的公共場(chǎng)所最多?！据斎搿枯斎胛募麨閣ireless.in。第一行包含一個(gè)整數(shù)d，表示無(wú)線網(wǎng)絡(luò)發(fā)射器的傳播距離。第二行包含一個(gè)整數(shù)n，表示有公共場(chǎng)所的路口數(shù)目。接下來(lái)n行，每行給出三個(gè)整數(shù)x,y,k,中間用一個(gè)空格隔開(kāi)，分別代表路口的坐標(biāo)(x,y)以及該路口公共場(chǎng)所的數(shù)量。同一坐標(biāo)只會(huì)給出一次。【輸出】輸出文件名為wireless.out。輸出一行，包含兩個(gè)整數(shù)，用一個(gè)空格隔開(kāi)，分別表示能覆蓋最多公共場(chǎng)所的安裝地點(diǎn)方案數(shù)，以及能覆蓋的最多公共場(chǎng)所的數(shù)量?！据斎胼敵鰳永縲ireless.inwireless.outwireless.in244106620130【數(shù)據(jù)說(shuō)明】對(duì)于100%的數(shù)據(jù)，1WdW20,1WnW20,0WxW128,0WyW128,0<kW1,000,000。2.尋找道路(road.cpp/c/pas)【問(wèn)題描述】在有向圖G中，每條邊的長(zhǎng)度均為1,現(xiàn)給定起點(diǎn)和終點(diǎn)，請(qǐng)你在圖中找一條從起點(diǎn)到終點(diǎn)的路徑，該路徑滿足以下條件：路徑上的所有點(diǎn)的出邊所指向的點(diǎn)都直接或間接與終點(diǎn)連通。在滿足條件1的情況下使路徑最短。注意：圖G中可能存在重邊和自環(huán)，題目保證終點(diǎn)沒(méi)有出邊。請(qǐng)你輸出符合條件的路徑的長(zhǎng)度?！据斎搿枯斎胛募麨閞oad.in。第一行有兩個(gè)用一個(gè)空格隔開(kāi)的整數(shù)n和m，表示圖有n個(gè)點(diǎn)和m條邊。接下來(lái)的m行每行2個(gè)整數(shù)x、y，之間用一個(gè)空格隔開(kāi)，表示有一條邊從點(diǎn)x指向點(diǎn)y。最后一行有兩個(gè)用一個(gè)空格隔開(kāi)的整數(shù)s、t，表示起點(diǎn)為s，終點(diǎn)為t。【輸出】輸出文件名為road.out。輸出只有一行，包含一個(gè)整數(shù)，表示滿足題目描述的最短路徑的長(zhǎng)度。如果這樣的路徑不存在，輸出-1?！据斎胼敵鰳永?】road.inroad.out32-1122113【輸入輸出樣例說(shuō)明】如上圖所示，箭頭表示有向道路，圓點(diǎn)表示城市。起點(diǎn)1與終點(diǎn)3不連通，所以滿足題目描述的路徑不存在，故輸出-1?！据斎胼敵鰳永f(shuō)明】連了一條邊到點(diǎn)6,而點(diǎn)6不與終點(diǎn)5連通?！緮?shù)據(jù)說(shuō)明】對(duì)于30%的數(shù)據(jù)，0<n<10,0<m<20；對(duì)