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

CCF全國信息學(xué)奧林匹克聯(lián)賽(NOIP2021)復(fù)賽

提高組day11．生活大爆炸版石頭剪子布

(rps.cpp/c/pas)【問題描述】石頭剪子布是常見的猜拳游戲：石頭勝剪子，剪子勝布，布勝石頭。若是兩個(gè)人出拳一樣，那么不分輸贏。在《生活大爆炸》第二季第8集中顯現(xiàn)了一種石頭剪子布的升級版游戲。升級版游戲在傳統(tǒng)的石頭剪子布游戲的基礎(chǔ)上，增加了兩個(gè)新手勢：斯波克：《星際迷航》主角之一。蜥蜴人：《星際迷航》中的反面角色。這五種手勢的輸贏關(guān)系如表一所示，表中列出的是甲對乙的游戲結(jié)果。表一石頭剪子布升級版輸贏關(guān)系、 乙甲對乙的甲結(jié)果剪刀石頭布蜥蜴人斯波克剪刀平輸贏贏輸石頭平輸贏輸布平輸贏蜥蜴人平贏斯波克平此刻，小A和小B嘗試玩這種升級版的猜拳游戲。已知他們的出拳都是有周期性規(guī)律的，但周期長度不必然相等。例如：若是小A以“石頭-布-石頭-剪子-蜥蜴人-斯波克”長度為6的周期出拳，那么他的出拳序列確實(shí)是“石頭■布-石頭-剪子-蜥蜴人-斯波克-石頭-布-石頭-剪子-蜥蜴人-斯波克-……”，而若是小B以“剪子-石頭-布-斯波克-蜥蜴人”長度為5的周期出拳，那么他出拳的序列確實(shí)是“剪子-石頭-布-斯波克-蜥蜴人-剪子-石頭-布-斯波克-蜥蜴人-……”已知小A和小B一共進(jìn)行N次猜拳。每一次贏的人得1分，輸?shù)牡?分；平局兩人都得0分?，F(xiàn)請你統(tǒng)計(jì)N次猜拳終止以后兩人的得分?！据斎搿枯斎胛募麨閞ps.in。第一行包括三個(gè)整數(shù)：N，NA，NB，分別表示共進(jìn)行N次猜拳、小A出拳的周期長度，小B出拳的周期長度。數(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的得分?！据斎胼敵鰳永?】rps.inrps.out10560123403421062【輸入輸出樣例2】rps.inrps.out955440123410324【數(shù)聽說明】關(guān)于100%的數(shù)據(jù)，0<NW200,0<NA&200, 0<NB&200。2．聯(lián)合權(quán)值(link.cpp/c/pas)【問題描述】無向連通圖G有n個(gè)點(diǎn)，n-1條邊。點(diǎn)從1到n依次編號，編號為i的點(diǎn)的權(quán)值為Wi,每條邊的長度均為1。圖上兩點(diǎn)(u,v)的距離概念為u點(diǎn)到v點(diǎn)的最短距離。關(guān)于圖G上的點(diǎn)對(u,v)，假設(shè)它們的距離為2,那么它們之間會產(chǎn)生WuXWv的聯(lián)合權(quán)值請問圖G上所有可產(chǎn)生聯(lián)合權(quán)值的有序點(diǎn)對中，聯(lián)合權(quán)值最大的是多少？所有聯(lián)合權(quán)值之和是多少？【輸入】輸入文件名為link.in。第一行包括1個(gè)整數(shù)n。接下來n-1行，每行包括2個(gè)用空格隔開的正整數(shù)u、v,表示編號為u和編號為v的點(diǎn)之間有邊相連。最后1行，包括n個(gè)正整數(shù)，每兩個(gè)正整數(shù)之間用一個(gè)空格隔開，其中第i個(gè)整數(shù)表示圖G上編號為i的點(diǎn)的權(quán)值為Wi?！据敵觥枯敵鑫募麨閘ink.out。輸出共1行，包括2個(gè)整數(shù)，之間用一個(gè)空格隔開，依次為圖G上聯(lián)合權(quán)值的最大值和所有聯(lián)合權(quán)值之和。由于所有聯(lián)合權(quán)值之和可能專門大,輸出它時(shí)要對10007取余?！据斎胼敵鰳永縧ink.inlink.out5207412233445152310【樣例說明】

本例輸入的圖如上所示，距離為2的有序點(diǎn)對有（1,3）、（2,4）、（3,1）、（3,5）、（4,2）、（5,3）。其聯(lián)合權(quán)值別離為二、1五、二、20、1五、20。其中最大的是20,總和為74?！緮?shù)聽說明】關(guān)于30%的數(shù)據(jù)，1<W100;關(guān)于60%的數(shù)據(jù)，102000；關(guān)于100%的數(shù)據(jù)，10200,000,0<Wi410,000。3.飛揚(yáng)的小鳥

(bird.cpp/c/pas)【問題描述】點(diǎn)擊電話屏幕的頻率鳥一不警惕撞到了水道（忽略管數(shù)高度位FlappyBird是一款盛行一時(shí)的休閑電話游戲。玩家需要不斷操縱來調(diào)劑小鳥的飛行高度，讓小鳥順利通過畫面右方的管道裂縫。若是小管或掉在地上的話，便宣告失敗。點(diǎn)擊電話屏幕的頻率鳥一不警惕撞到了水道（忽略管數(shù)高度位為了簡化問題，咱們對游戲規(guī)那么進(jìn)行了簡化和改編：游戲界面是一個(gè)長為n,高為m的二維平面，其中有k個(gè)管道的寬度）。小鳥始終在游戲界面內(nèi)移動。小鳥從游戲界面最左側(cè)任意整置動身，抵達(dá)游戲界面最右邊時(shí)，游戲完成。小鳥每一個(gè)單位時(shí)刻沿橫坐標(biāo)方向右移的距離為1，豎直移動的距離由玩家操縱。若是點(diǎn)擊屏幕，小鳥就會上升必然高度X,每一個(gè)單位時(shí)刻能夠點(diǎn)擊多次，成效疊加；若是不點(diǎn)擊屏幕，小鳥就會下降必然高團(tuán)。小鳥位于橫坐標(biāo)方向不同位置時(shí)，上升的高度X和下降的高度Y可能互不相同。.小鳥高度等于0或小鳥碰著管道時(shí)，游戲失敗。小鳥高度為m時(shí)，無法再上升。此刻，請你判定是不是能夠完成游戲。若是能夠，輸出最少點(diǎn)擊屏幕數(shù)；不然，輸出小鳥最多能夠通過量少個(gè)管道裂縫?！据斎搿枯斎胛募麨閎ird.in。第1行有3個(gè)整數(shù)n，m，k，別離表示游戲界面的長度，高度和水管的數(shù)量，每兩個(gè)整數(shù)之間用一個(gè)空格隔開；接下來的n行，每行2個(gè)用一個(gè)空格隔開的整數(shù)X和Y，依次表示在橫坐標(biāo)位置0~n-1上玩家點(diǎn)擊屏幕后，小鳥在下一名置上升的高度X，和在那個(gè)位置上玩家不點(diǎn)擊屏幕時(shí)，小鳥在下一名置下降的高度Y。接下來k行，每行3個(gè)整數(shù)P，L，H，每兩個(gè)整數(shù)之間用一個(gè)空格隔開。每行表示一個(gè)管道，其中P表示管道的橫坐標(biāo)，L表示此管道裂縫的下邊沿高度為L，H表示管道裂縫上邊沿的高度（輸入數(shù)據(jù)保證P各不相同，但不保證依照大小順序給出）。【輸出】輸出文件名為bird.out。共兩行。第一行，包括一個(gè)整數(shù)，若是能夠成功完成游戲，那么輸出1，不然輸出0。第二行，包括一個(gè)整數(shù)，若是第一行為1，那么輸出成功完成游戲需要最少點(diǎn)擊屏幕數(shù)，不然，輸出小鳥最多能夠通過量少個(gè)管道裂縫?！据斎胼敵鰳永?】bird.inbird.out101061396991213121121211622127515635758879913【輸入輸出樣例2】bird.inbird.out

1010412312218183221212212102679914381003【輸入輸出樣例說明】如以下圖所示，藍(lán)色直線表示小鳥的飛行軌跡，紅色直線表示管道?！緮?shù)據(jù)范圍】關(guān)于30%的數(shù)據(jù)：5WnW10,5WmW10,k=0,保證存在一組最優(yōu)解使得同一單位時(shí)刻最多點(diǎn)擊屏幕3次;關(guān)于50%的數(shù)據(jù)：5WnW20,5WmW10,保證存在一組最優(yōu)解使得同一單位時(shí)刻最多點(diǎn)擊屏幕3次；關(guān)于70%的數(shù)據(jù)：5WnW1000,5WmW100；關(guān)于100%的數(shù)據(jù)：5WnW10000,5WmW1000,0Wk<n,0<X<m,0<Y<m,0<P<n,0WL<HWm,L+1<H。CCF全國信息學(xué)奧林匹克聯(lián)賽（NOIP2021）復(fù)賽提高組day2.無線網(wǎng)絡(luò)發(fā)射器選址（wireless.cpp/c/pas）【問題描述】隨著智能電話的日趨普及，人們對無線網(wǎng)的需求日趨增大。某城市決定對城市內(nèi)的公開場合覆蓋無線網(wǎng)。假設(shè)該城市的布局為由嚴(yán)格平行的129條東西向街道和129條南北向街道所形成的網(wǎng)格狀，而且相鄰的平行街道之間的距離都是恒定值1。東西向街道從北到南依次編號為0,1,2…128,南北向街道從西到東依次編號為0,1,2…128。東西向街道和南北向街道相交形成路口，規(guī)定編號為x的南北向街道和編號為y的東西向街道形成的路口的坐標(biāo)是（x,y）。在某些路口存在定數(shù)量的公共場所。

某些路口存在定數(shù)量的公共場所。由于政府財(cái)政問題，只能安裝一個(gè)大型無線網(wǎng)絡(luò)發(fā)射器。該無線網(wǎng)絡(luò)發(fā)射器的傳播范圍是一個(gè)以該點(diǎn)為中心，邊長為2*d的正方形。傳播范圍包括正方形邊界。例如以下圖是一個(gè)d=1的無線網(wǎng)絡(luò)發(fā)射器的覆蓋范圍示用意。今無線網(wǎng)絡(luò)發(fā)射器安裝地點(diǎn)口無線網(wǎng)絡(luò)發(fā)射器覆蓋范圍▲存在公共場所的路口此刻政府有關(guān)部門預(yù)備安裝一個(gè)傳播參數(shù)為d的無線網(wǎng)絡(luò)發(fā)射器，希望你幫忙他們在城市內(nèi)找出適合的安裝地址，使得覆蓋的公開場合最多?！据斎搿枯斎胛募麨閣ireless.in。第一行包括一個(gè)整數(shù)d，表示無線網(wǎng)絡(luò)發(fā)射器的傳播距離。第二行包括一個(gè)整數(shù)n，表示有公開場合的路口數(shù)量。接下來n行，每行給出三個(gè)整數(shù)x,y,k,中間用一個(gè)空格隔開，別離代表路口的坐標(biāo)(x,y)和該路口公開場合的數(shù)量。同一坐標(biāo)只會給出一次?！据敵觥枯敵鑫募麨閣ireless.out。輸出一行，包括兩個(gè)整數(shù)，用一個(gè)空格隔開，別離表示能覆蓋最多公開場合的安裝地址方案數(shù)，和能覆蓋的最多公開場合的數(shù)量。【輸入輸出樣例】wireless.inwireless.out1244101306620【數(shù)聽說明】關(guān)于100%的數(shù)據(jù)，1WdW20,1WnW20,0WxW128,0WyW128,0<kW1,000,000。.尋覓道路

(road.cpp/c/pas)【問題描述】在有向圖G中，每條邊的長度均為1,現(xiàn)給定起點(diǎn)和終點(diǎn)，請你在圖中找一條從起點(diǎn)到終點(diǎn)的途徑，該途徑知足以下條件:.途徑上的所有點(diǎn)的出邊所指向的點(diǎn)都直接或間接與終點(diǎn)連通。2.在知足條件1的情形下使途徑最短。注意：圖G中可能存在重邊和自環(huán)，題目保證終點(diǎn)沒有出邊。請你輸出符合條件的途徑的長度?！据斎搿枯斎胛募麨閞oad.in。第一行有兩個(gè)用一個(gè)空格隔開的整數(shù)n和m,表示圖有n個(gè)點(diǎn)和m條邊。接下來的m行每行2個(gè)整數(shù)x、y,之間用一個(gè)空格隔開，表示有一條邊從點(diǎn)x指向點(diǎn)y。最后一行有兩個(gè)用一個(gè)空格隔開的整數(shù)s、t,表示起點(diǎn)為s,終點(diǎn)為t。【輸出】輸出文件名為road.out。輸出只有一行，包括一個(gè)整數(shù)，表示知足題目描述的最短途徑的長度。若是如此的途徑不存在，輸出-1?！据斎胼敵鰳永?】road.inroad.out32-1122113【輸入輸出樣例說明】?3如上圖所示，箭頭表示有向道路，圓點(diǎn)表示城市。起點(diǎn)1與終點(diǎn)3不連通，因此知足題目描述的途徑不存在，故輸出一1?！据斎胼敵鰳永?】road.inroad.out66312132625453415【輸入輸出樣例說明】如上圖所示，知足條件的途徑為1->3->4->5。注意點(diǎn)2不能在答案途徑中，因?yàn)辄c(diǎn)2連了一條邊到點(diǎn)6,而點(diǎn)6不與終點(diǎn)5連通?！緮?shù)聽說明】關(guān)于30%的數(shù)據(jù)，0<nW10,0<mW20；關(guān)于60%的數(shù)據(jù)，0<nW100,0<mW2000；關(guān)于100%的數(shù)據(jù)，0<nW10,000,0<mW200,000,0<x,y,s,tWn,xWt。3.解方程(equation.cpp/c/pas)【問題描述】已知多項(xiàng)式方程：aoT-?1x+ +—+ =O求那個(gè)方程在［1,m］內(nèi)的整數(shù)解(n和m均為正整數(shù))?！据斎搿枯斎胛募麨閑quation.in。輸入共n+2行。第一行包括2個(gè)整數(shù)n、m,每兩個(gè)整數(shù)之間用一個(gè)空格隔開。接下來的n+1行每行包括一個(gè)整數(shù)，依次為a0,a1,a2,……，an?！据敵觥枯敵鑫募麨閑quation.out。第一行輸出方程在［1,m］內(nèi)的整數(shù)解的個(gè)數(shù)。

接下來每行一個(gè)整數(shù)，依照從小到大的順序依次輸出方程在［1,m］內(nèi)的一個(gè)整數(shù)解?！据斎胼敵鰳永?】equationinequationout210111-21【輸入輸出樣例2】 equation.in