NOIP2014提高組復賽試題day1+day2

./CCF全國信息學奧林匹克聯(lián)賽〔NOIP2014復賽提高組day11．生活大爆炸版石頭剪刀布<rps.cpp/c/pas>[問題描述]石頭剪刀布是常見的猜拳游戲：石頭勝剪刀,剪刀勝布,布勝石頭.如果兩個人出拳一樣,則不分勝負.在《生活大爆炸》第二季第8集中出現(xiàn)了一種石頭剪刀布的升級版游戲.升級版游戲在傳統(tǒng)的石頭剪刀布游戲的基礎(chǔ)上,增加了兩個新手勢：斯波克：《星際迷航》主角之一.蜥蜴人：《星際迷航》中的反面角色.這五種手勢的勝負關(guān)系如表一所示,表中列出的是甲對乙的游戲結(jié)果.表一石頭剪刀布升級版勝負關(guān)系乙甲對乙的甲結(jié)果剪刀石頭布蜥蜴人斯波克剪刀平輸贏贏輸石頭平輸贏輸布平輸贏蜥蜴人平贏斯波克平現(xiàn)在,小A和小B嘗試玩這種升級版的猜拳游戲.已知他們的出拳都是有周期性規(guī)律的,但周期長度不一定相等.例如：如果小A以"石頭-布-石頭-剪刀-蜥蜴人-斯波克"長度為6的周期出拳,那么他的出拳序列就是"石頭-布-石頭-剪刀-蜥蜴人-斯波克-石頭-布-石頭-剪刀-蜥蜴人-斯波克-……",而如果小B以"剪刀-石頭-布-斯波克-蜥蜴人"長度為5的周期出拳,那么他出拳的序列就是"剪刀-石頭-布-斯波克-蜥蜴人-剪刀-石頭-布-斯波克-蜥蜴人-……"已知小A和小B一共進行N次猜拳.每一次贏的人得1分,輸?shù)牡?分；平局兩人都得0分.現(xiàn)請你統(tǒng)計N次猜拳結(jié)束之后兩人的得分.[輸入]輸入文件名為rps.in.第一行包含三個整數(shù)：N,NA,NB,分別表示共進行N次猜拳、小A出拳的周期長度,小B出拳的周期長度.數(shù)與數(shù)之間以一個空格分隔.第二行包含NA個整數(shù),表示小A出拳的規(guī)律,第三行包含NB個整數(shù),表示小B出拳的規(guī)律.其中,0表示"剪刀",1表示"石頭",2表示"布",3表示"蜥蜴人",4表示"斯波克".數(shù)與數(shù)之間以一個空格分隔.[輸出]輸出文件名為rps.out.輸出一行,包含兩個整數(shù),以一個空格分隔,分別表示小A、小B的得分.[輸入輸出樣例1]rps.inrps.out10560123403421062[輸入輸出樣例2]rps.inrps.out955012341032444[數(shù)據(jù)說明]對于100%的數(shù)據(jù),0<N≤200,0<NA≤200,0<NB≤200.2．聯(lián)合權(quán)值<link.cpp/c/pas>[問題描述]無向連通圖G有n個點,n-1條邊.點從1到n依次編號,編號為i的點的權(quán)值為Wi,每條邊的長度均為1.圖上兩點<u,v>的距離定義為u點到v點的最短距離.對于圖G上的點對<u,v>,若它們的距離為2,則它們之間會產(chǎn)生Wu×Wv的聯(lián)合權(quán)值.請問圖G上所有可產(chǎn)生聯(lián)合權(quán)值的有序點對中,聯(lián)合權(quán)值最大的是多少？所有聯(lián)合權(quán)值之和是多少？[輸入]輸入文件名為link.in.第一行包含1個整數(shù)n.接下來n-1行,每行包含2個用空格隔開的正整數(shù)u、v,表示編號為u和編號為v的點之間有邊相連.最后1行,包含n個正整數(shù),每兩個正整數(shù)之間用一個空格隔開,其中第i個整數(shù)表示圖G上編號為i的點的權(quán)值為Wi.[輸出]輸出文件名為link.out.輸出共1行,包含2個整數(shù),之間用一個空格隔開,依次為圖G上聯(lián)合權(quán)值的最大值和所有聯(lián)合權(quán)值之和.由于所有聯(lián)合權(quán)值之和可能很大,輸出它時要對10007取余.[輸入輸出樣例]link.inlink.out5122334451523102074[樣例說明]本例輸入的圖如上所示,距離為2的有序點對有<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ù)說明]對于30%的數(shù)據(jù),1<≤100；對于60%的數(shù)據(jù),1<≤2000；對于100%的數(shù)據(jù),1<≤200,000,0<Wi≤10,000.3.飛揚的小鳥〔bird.cpp/c/pas>[問題描述]FlappyBird是一款風靡一時的休閑手機游戲.玩家需要不斷控制點擊手機屏幕的頻率來調(diào)節(jié)小鳥的飛行高度,讓小鳥順利通過畫面右方的管道縫隙.如果小鳥一不小心撞到了水管或者掉在地上的話,便宣告失敗.為了簡化問題,我們對游戲規(guī)則進行了簡化和改編：游戲界面是一個長為n,高為m的二維平面,其中有k個管道〔忽略管道的寬度.小鳥始終在游戲界面內(nèi)移動.小鳥從游戲界面最左邊任意整數(shù)高度位置出發(fā),到達游戲界面最右邊時,游戲完成.小鳥每個單位時間沿橫坐標方向右移的距離為1,豎直移動的距離由玩家控制.如果點擊屏幕,小鳥就會上升一定高度X,每個單位時間可以點擊多次,效果疊加；如果不點擊屏幕,小鳥就會下降一定高度Y.小鳥位于橫坐標方向不同位置時,上升的高度X和下降的高度Y可能互不相同.小鳥高度等于0或者小鳥碰到管道時,游戲失敗.小鳥高度為m時,無法再上升.現(xiàn)在,請你判斷是否可以完成游戲.如果可以,輸出最少點擊屏幕數(shù)；否則,輸出小鳥最多可以通過多少個管道縫隙.[輸入]輸入文件名為bird.in.第1行有3個整數(shù)n,m,k,分別表示游戲界面的長度,高度和水管的數(shù)量,每兩個整數(shù)之間用一個空格隔開；接下來的n行,每行2個用一個空格隔開的整數(shù)X和Y,依次表示在橫坐標位置0~n-1上玩家點擊屏幕后,小鳥在下一位置上升的高度X,以及在這個位置上玩家不點擊屏幕時,小鳥在下一位置下降的高度Y.接下來k行,每行3個整數(shù)P,L,H,每兩個整數(shù)之間用一個空格隔開.每行表示一個管道,其中P表示管道的橫坐標,L表示此管道縫隙的下邊沿高度為L,H表示管道縫隙上邊沿的高度〔輸入數(shù)據(jù)保證P各不相同,但不保證按照大小順序給出.[輸出]輸出文件名為bird.out.共兩行.第一行,包含一個整數(shù),如果可以成功完成游戲,則輸出1,否則輸出0.第二行,包含一個整數(shù),如果第一行為1,則輸出成功完成游戲需要最少點擊屏幕數(shù),否則,輸出小鳥最多可以通過多少個管道縫隙.[輸入輸出樣例1]bird.inbird.out101063999121312112121162212751563575887991316[輸入輸出樣例2]bird.inbird.out1010412312218183221212212102679914381003[輸入輸出樣例說明]如下圖所示,藍色直線表示小鳥的飛行軌跡,紅色直線表示管道.[數(shù)據(jù)范圍]對于30%的數(shù)據(jù)：5≤n≤10,5≤m≤10,k=0,保證存在一組最優(yōu)解使得同一單位時間最多點擊屏幕3次；對于50%的數(shù)據(jù)：5≤n≤20,5≤m≤10,保證存在一組最優(yōu)解使得同一單位時間最多點擊屏幕3次；對于70%的數(shù)據(jù)：5≤n≤1000,5≤m≤100；對于100%的數(shù)據(jù)：5≤n≤10000,5≤m≤1000,0≤k<n,0<X<m,0<Y<m,0<P<n,0≤L<H≤m,L+1<H.CCF全國信息學奧林匹克聯(lián)賽〔NOIP2014復賽提高組day21．無線網(wǎng)絡發(fā)射器選址<wireless.cpp/c/pas>[問題描述]隨著智能手機的日益普及,人們對無線網(wǎng)的需求日益增大.某城市決定對城市內(nèi)的公共場所覆蓋無線網(wǎng).假設該城市的布局為由嚴格平行的129條東西向街道和129條南北向街道所形成的網(wǎng)格狀,并且相鄰的平行街道之間的距離都是恒定值1.東西向街道從北到南依次編號為0,1,2…128,南北向街道從西到東依次編號為0,1,2…128.東西向街道和南北向街道相交形成路口,規(guī)定編號為x的南北向街道和編號為y的東西向街道形成的路口的坐標是〔x,y.在某些路口存在一定數(shù)量的公共場所.由于政府財政問題,只能安裝一個大型無線網(wǎng)絡發(fā)射器.該無線網(wǎng)絡發(fā)射器的傳播范圍是一個以該點為中心,邊長為2*d的正方形.傳播范圍包括正方形邊界.例如下圖是一個d=1的無線網(wǎng)絡發(fā)射器的覆蓋范圍示意圖.現(xiàn)在政府有關(guān)部門準備安裝一個傳播參數(shù)為d的無線網(wǎng)絡發(fā)射器,希望你幫助他們在城市內(nèi)找出合適的安裝地點,使得覆蓋的公共場所最多.[輸入]輸入文件名為wireless.in.第一行包含一個整數(shù)d,表示無線網(wǎng)絡發(fā)射器的傳播距離.第二行包含一個整數(shù)n,表示有公共場所的路口數(shù)目.接下來n行,每行給出三個整數(shù)x,y,k,中間用一個空格隔開,分別代表路口的坐標<x,y>以及該路口公共場所的數(shù)量.同一坐標只會給出一次.[輸出]輸出文件名為wireless.out.輸出一行,包含兩個整數(shù),用一個空格隔開,分別表示能覆蓋最多公共場所的安裝地點方案數(shù),以及能覆蓋的最多公共場所的數(shù)量.[輸入輸出樣例]wireless.inwireless.out1244106620130[數(shù)據(jù)說明]對于100%的數(shù)據(jù),1≤d≤20,1≤n≤20,0≤x≤128,0≤y≤128,0<k≤1,000,000.2．尋找道路<road.cpp/c/pas>[問題描述]在有向圖G中,每條邊的長度均為1,現(xiàn)給定起點和終點,請你在圖中找一條從起點到終點的路徑,該路徑滿足以下條件：1．路徑上的所有點的出邊所指向的點都直接或間接與終點連通.2．在滿足條件1的情況下使路徑最短.注意：圖G中可能存在重邊和自環(huán),題目保證終點沒有出邊.請你輸出符合條件的路徑的長度.[輸入]輸入文件名為road.in.第一行有兩個用一個空格隔開的整數(shù)n和m,表示圖有n個點和m條邊.接下來的m行每行2個整數(shù)x、y,之間用一個空格隔開,表示有一條邊從點x指向點y.最后一行有兩個用一個空格隔開的整數(shù)s、t,表示起點為s,終點為t.[輸出]輸出文件名為road.out.輸出只有一行,包含一個整數(shù),表示滿足題目描述的最短路徑的長度.如果這樣的路徑不存在,輸出-1.[輸入輸出樣例1]road.inroad.out32122113－1[輸入輸出樣例說明]如上圖所示,箭頭表示有向道路,圓點表示城市.起點1與終點3不連通,所以滿足題目描述的路徑不存在,故輸出-1.[輸入輸出樣例2]road.inroad.out66121326254534153[輸入輸出樣例說明]如上圖所示,滿足條件的路徑為1->3->4->5.注意點2不能在答案路徑中,因為點2連了一條邊到點6,而點6不與終點5連通.[數(shù)據(jù)說明]對于30%的數(shù)據(jù),0<n≤10,0<m≤20；對于60%的數(shù)據(jù),0<n≤100,0<m≤2000；對于100%的數(shù)據(jù),0<n≤10,000,0<m≤200,000,0<x,y,s,t≤n,x≠t.3．解方程<equation.cpp/c/pas>[問題描述]已知多項式方程：求這個方程在[1,m]內(nèi)的整數(shù)解〔n和m均為正整數(shù).[輸入]輸入文件名為equation.in.輸入共n+2行.第一行包含2個整數(shù)n、m,每兩個整數(shù)之間用一個空格隔開.接下來的n+1行每行包含一個整數(shù),依次為a0,a1,a2,……,an.[輸出]輸出文件名為equation.out.第一行輸出方程在[1,m]內(nèi)的整數(shù)解的個數(shù).接下來每行一個整數(shù),按照從小到大的順序依次輸出方程在[1,m]內(nèi)的一個整數(shù)解.[輸入輸出樣例1]equation.inequation.out2101-2111[輸入輸