1、CCF全國信息學奧林匹克聯賽（NOIP2014）復賽提高組 day1 1生活大爆炸版石頭剪刀布(rps.cpp/c/pas)【問題描述】石頭剪刀布是常見的猜拳游戲：石頭勝剪刀，剪刀勝布，布勝石頭。如果兩個人出拳一樣，則不分勝負。在生活大爆炸第二季第8集中出現了一種石頭剪刀布的升級版游戲。升級版游戲在傳統的石頭剪刀布游戲的基礎上，增加了兩個新手勢：斯波克：星際迷航主角之一。蜥蜴人：星際迷航中的反面角色。這五種手勢的勝負關系如表一所示，表中列出的是甲對乙的游戲結果。表一 石頭剪刀布升級版勝負關系 乙 甲對乙的甲 結果剪刀石頭布蜥蜴人斯波克剪刀平輸贏贏輸石頭平輸贏輸布平輸贏蜥蜴人平贏斯波克平現在，小

2、A和小B嘗試玩這種升級版的猜拳游戲。已知他們的出拳都是有周期性規律的，但周期長度不一定相等。例如：如果小A以“石頭-布-石頭-剪刀-蜥蜴人-斯波克”長度為6的周期出拳，那么他的出拳序列就是“石頭-布-石頭-剪刀-蜥蜴人-斯波克-石頭-布-石頭-剪刀-蜥蜴人-斯波克-”，而如果小B以“剪刀-石頭-布-斯波克-蜥蜴人”長度為5的周期出拳，那么他出拳的序列就是“剪刀-石頭-布-斯波克-蜥蜴人-剪刀-石頭-布-斯波克-蜥蜴人-”已知小A和小B一共進行N次猜拳。每一次贏的人得1分，輸的得0分；平局兩人都得0分。現請你統計N次猜拳結束之后兩人的得分。【輸入】輸入文件名為rps.in。第一行包含三個整數：N

3、，NA，NB，分 別 表 示 共 進 行N次猜拳、小A出拳的周期長度，小B出拳的周期長度。數與數之間以一個空格分隔。第二行包含NA個整數，表示小A出拳的規律，第三行包含NB個整數，表示小B出拳的規律。其中，0表示“剪刀”，1表示“石頭”，2表示“布”，3表示“蜥蜴人”， 4表示“斯波克”。數與數之間以一個空格分隔。【輸出】輸出文件名為rps.out。輸出一行， 包含兩個整數，以一個空格分隔，分別表示小A、小B的得分。【輸入輸出樣例1】rps.inrps.out10 5 60 1 2 3 40 3 4 2 1 06 2【輸入輸出樣例2】rps.inrps.out9 5 50 1 2 3 41 0

4、 3 2 44 4【數據說明】對于100%的數據，0 < N 200，0 < NA 200， 0 < NB 200。2聯合權值(link.cpp/c/pas)【問題描述】無向連通圖G有n個點，n-1條邊。點從1到n依次編號，編號為i的點的權值為Wi ，每條邊的長度均為1。圖上兩點(u, v)的距離定義為u點到v點的最短距離。對于圖G上的點對(u, v)，若它們的距離為2，則它們之間會產生Wu×Wv的聯合權值。請問圖G上所有可產生聯合權值的有序點對中，聯合權值最大的是多少？所有聯合權值之和是多少？【輸入】輸入文件名為link.in。第一行包含1個整數n。接下來n-1行

5、，每行包含2個用空格隔開的正整數u、v，表示編號為u和編號為v的點之間有邊相連。最后1行，包含n個正整數，每兩個正整數之間用一個空格隔開，其中第i個整數表示圖G上編號為i的點的權值為Wi。【輸出】輸出文件名為link.out。輸出共1行，包含2個整數，之間用一個空格隔開，依次為圖G上聯合權值的最大值和所有聯合權值之和。由于所有聯合權值之和可能很大，輸出它時要對10007取余。 【輸入輸出樣例】link.inlink.out51 22 33 44 51 5 2 3 1020 74【樣例說明】本例輸入的圖如上所示，距離為2的有序點對有(1,3)、(2,4)、(3,1)、(3,5)、(4,2)、(5

6、,3)。其聯合權值分別為2、15、2、20、15、20。其中最大的是20，總和為74。【數據說明】對于30%的數據，1<100；對于60%的數據，1<2000；對于100%的數據，1<200,000，0<Wi 10,000。3. 飛揚的小鳥（bird.cpp/c/pas)【問題描述】Flappy Bird 是一款風靡一時的休閑手機游戲。玩家需要不斷控制點擊手機屏幕的頻率來調節小鳥的飛行高度，讓小鳥順利通過畫面右方的管道縫隙。如果小鳥一不小心撞到了水管或者掉在地上的話，便宣告失敗。為了簡化問題，我們對游戲規則進行了簡化和改編：1. 游戲界面是一個長為n，高 為m的二維平面

7、，其中有k個管道（忽略管道的寬度）。2. 小鳥始終在游戲界面內移動。小鳥從游戲界面最左邊任意整數高度位置出發，到達游戲界面最右邊時，游戲完成。3. 小鳥每個單位時間沿橫坐標方向右移的距離為1，豎直移動的距離由玩家控制。如果點擊屏幕，小鳥就會上升一定高度X，每個單位時間可以點擊多次，效果疊加；如果不點擊屏幕，小鳥就會下降一定高度Y。小鳥位于橫坐標方向不同位置時，上升的高度X和下降的高度Y可能互不相同。4. 小鳥高度等于0或者小鳥碰到管道時，游 戲 失 敗 。小 鳥 高 度 為m時，無法再上升。現在，請你判斷是否可以完成游戲。如果可以，輸出最少點擊屏幕數；否則，輸出小鳥最多可以通過多少個管道縫隙。

8、【輸入】輸入文件名為 bird.in。第1行有3個整數n，m，k，分別表示游戲界面的長度，高度和水管的數量，每兩個整數之間用一個空格隔開；接下來的n行，每行2個用一個空格隔開的整數X和Y，依次表示在橫坐標位置0n-1上玩家點擊屏幕后，小鳥在下一位置上升的高度X，以及在這個位置上玩家不點擊屏幕時，小鳥在下一位置下降的高度Y。接下來k行，每行3個整數P，L，H，每兩個整數之間用一個空格隔開。每行表示一個管道，其中P表示管道的橫坐標，L表示此管道縫隙的下邊沿高度為L，H表示管道縫隙上邊沿的高度（輸入數據保證P各不相同，但不保證按照大小順序給出）。【輸出】輸出文件名為bird.out。共兩行。第一行，

9、包含一個整數，如果可以成功完成游戲，則輸出1，否則輸出0。第二行，包含一個整數，如果第一行為1，則輸出成功完成游戲需要最少點擊屏幕數，否則，輸出小鳥最多可以通過多少個管道縫隙。【輸入輸出樣例1】bird.inbird.out10 10 63 99 91 21 31 21 12 12 11 62 21 2 75 1 56 3 57 5 88 7 99 1 316【輸入輸出樣例2】bird.inbird.out10 10 41 23 12 21 81 83 22 12 12 21 21 0 26 7 99 1 43 8 1003【輸入輸出樣例說明】如下圖所示，藍色直線表示小鳥的飛行軌跡，紅色直線表

10、示管道。 【數據范圍】對于30%的數據：5n10，5m10，k=0，保證存在一組最優解使得同一單位時間最多點擊屏幕3次； 對于50%的數據：5n20，5m10，保證存在一組最優解使得同一單位時間最多點擊屏幕3次；對于70%的數據：5n1000，5m100；對于100%的數據：5n10000，5m1000，0k<n，0<X<m，0<Y<m，0<P<n，0L<H m，L+1<H。CCF全國信息學奧林匹克聯賽（NOIP2014）復賽提高組 day21無線網絡發射器選址(wireless.cpp/c/pas)【問題描述】隨著智能手機的日益普及，人們

11、對無線網的需求日益增大。某城市決定對城市內的公共場所覆蓋無線網。假設該城市的布局為由嚴格平行的129條東西向街道和129條南北向街道所形成的網格狀，并且相鄰的平行街道之間的距離都是恒定值1。東西向街道從北到南依次編號為0,1,2128,南北向街道從西到東依次編號為0,1,2128。東西向街道和南北向街道相交形成路口，規定編號為x的南北向街道和編號為y的東西向街道形成的路口的坐標是（x, y）。 在 某 些 路 口 存 在 一 定 數 量 的 公 共 場 所 。由于政府財政問題，只能安裝一個大型無線網絡發射器。該無線網絡發射器的傳播范圍是一個以該點為中心，邊長為2*d的正方形。傳播范圍包括正方形

12、邊界。例如下圖是一個d = 1的無線網絡發射器的覆蓋范圍示意圖。現在政府有關部門準備安裝一個傳播參數為d的無線網絡發射器，希望你幫助他們在城市內找出合適的安裝地點，使得覆蓋的公共場所最多。【輸入】輸入文件名為wireless.in。第一行包含一個整數d，表示無線網絡發射器的傳播距離。第二行包含一個整數n，表示有公共場所的路口數目。接下來n行，每行給出三個整數x, y, k, 中間用一個空格隔開，分別代表路口的坐標(x, y)以及該路口公共場所的數量。同一坐標只會給出一次。【輸出】輸出文件名為wireless.out。輸出一行，包含兩個整數，用一個空格隔開，分別表示能覆蓋最多公共場所的安裝地點方

13、案數，以及能覆蓋的最多公共場所的數量。【輸入輸出樣例】wireless.inwireless.out124 4 106 6 201 30【數據說明】對于100%的數據，1 d 20，1 n 20， 0 x 128, 0 y 128, 0 < k 1,000,000。2尋找道路(road.cpp/c/pas)【問題描述】在有向圖G中，每條邊的長度均為1，現給定起點和終點，請你在圖中找一條從起點到終點的路徑，該路徑滿足以下條件：1路徑上的所有點的出邊所指向的點都直接或間接與終點連通。2在滿足條件1的情況下使路徑最短。注意：圖G中可能存在重邊和自環，題目保證終點沒有出邊。請你輸出符合條件的路徑

14、的長度。【輸入】輸入文件名為road.in。第一行有兩個用一個空格隔開的整數n和m，表示圖有n個點和m條邊。接下來的m行每行2個整數x、y，之間用一個空格隔開，表示有一條邊從點x指向點y。最后一行有兩個用一個空格隔開的整數s、t，表示起點為s，終點為t。【輸出】輸出文件名為road.out。輸出只有一行，包含一個整數，表示滿足題目描述的最短路徑的長度。如果這樣的路徑不存在，輸出-1。【輸入輸出樣例1】road.inroad.out3 21 22 11 31【輸入輸出樣例說明】如上圖所示，箭頭表示有向道路，圓點表示城市。起點1與終點3不連通，所以滿足題目描述的路徑不存在，故輸出-1。【輸入輸出樣

15、例2】road.inroad.out6 61 21 32 62 54 53 41 53【輸入輸出樣例說明】如上圖所示，滿足條件的路徑為1->3->4->5。注意點2不能在答案路徑中，因為點2連了一條邊到點6，而點6不與終點5連通。【數據說明】對于30%的數據，0< n 10，0< m 20；對于60%的數據，0< n 100，0< m 2000；對于100%的數據，0< n 10,000，0< m 200,000，0< x,y,s,tn，xt。3解方程(equation.cpp/c/pas)【問題描述】已知多項式方程：求這個方程在1, m內的整數解（n和m均為正整數）。【輸入】輸入文件名為equation.in。輸入共n+2行。第一行包含2個整數n、m，每兩個整數之間用一個空格隔開。接下來的n+1行每行包含一個整數，依次為a0,a1,a2,an。【輸出】輸出文件名為equation.out。第一行輸出方程在1, m內的整數解的個數。接下來每行一個整數，按照從小到大的順序依次輸出方程在1, m內的一個整數解。【輸入輸出樣例1】equation.inequation.out2 101-2111