第二十六屆全國信息學(xué)奧林匹克競賽

1、第二十六屆全國信息學(xué)奧林匹克競賽NOI 2009第二試競賽時間：2009年7月29日上午8:00-13:00題目名稱植物大戰(zhàn)僵尸管道取珠描邊目錄pvzballpath可執(zhí)行文件名pvzballN/A輸入文件名pvz.inball.inpath1.inpath10.in輸出文件名pvz.outball.outpath1.outpath10.out每個測試點時限2秒2秒N/A測試點數(shù)目101010每個測試點分值101010是否有部分分無無有題目類型傳統(tǒng)傳統(tǒng)提交答案提交源程序須加后綴對于Pascal語言pvz.pasball.pasN/A對于C 語言pvz.cball.cN/A對于C+ 語言pvz.

2、cppball.cppN/A注意：最終測試時，所有編譯命令均不打開任何優(yōu)化開關(guān)植物大戰(zhàn)僵尸【問題描述】Plants vs. Zombies（PVZ）是最近十分風(fēng)靡的一款小游戲。Plants（植物）和Zombies（僵尸）是游戲的主角，其中Plants防守，而Zombies進(jìn)攻。該款游戲包含多種不同的挑戰(zhàn)系列，比如Protect Your Brain、Bowling等等。其中最為經(jīng)典的，莫過于玩家通過控制Plants來防守Zombies的進(jìn)攻，或者相反地由玩家通過控制Zombies對Plants發(fā)起進(jìn)攻。現(xiàn)在，我們將要考慮的問題是游戲中Zombies對Plants的進(jìn)攻，請注意，本題中規(guī)則與實際

3、游戲有所不同。游戲中有兩種角色，Plants和Zombies，每個Plant有一個攻擊位置集合，它可以對這些位置進(jìn)行保護(hù)；而Zombie進(jìn)攻植物的方式是走到植物所在的位置上并將其吃掉。游戲的地圖可以抽象為一個N行M列的矩陣，行從上到下用0到N1編號，列從左到右用0到M1編號；在地圖的每個位置上都放有一個Plant，為簡單起見，我們把位于第r行第c列的植物記為Pr, c。Plants分很多種，有攻擊類、防守類和經(jīng)濟(jì)類等等。為了簡單的描述每個Plant，定義Score和Attack如下：ScorePr, cZombie擊潰植物Pr, c可獲得的能源。若ScorePr, c為非負(fù)整數(shù)，則表示擊潰植物

4、Pr, c可獲得能源ScorePr, c，若為負(fù)數(shù)表示擊潰Pr, c需要付出能源 -ScorePr, c。AttackPr, c植物Pr, c能夠?qū)ombie進(jìn)行攻擊的位置集合。Zombies必須從地圖的右側(cè)進(jìn)入，且只能沿著水平方向進(jìn)行移動。Zombies攻擊植物的唯一方式就是走到該植物所在的位置并將植物吃掉。因此Zombies的進(jìn)攻總是從地圖的右側(cè)開始。也就是說，對于第r行的進(jìn)攻，Zombies必須首先攻擊Pr, M-1；若需要對Pr, c（0c<M-1）攻擊，必須將Pr,M-1, Pr, M-2 Pr, c+1先擊潰，并移動到位置(r, c)才可進(jìn)行攻擊。在本題的設(shè)定中，Plant

5、s的攻擊力是無窮大的，一旦Zombie進(jìn)入某個Plant的攻擊位置，該Zombie會被瞬間消滅，而該Zombie沒有時間進(jìn)行任何攻擊操作。因此，即便Zombie進(jìn)入了一個Plant所在的位置，但該位置屬于其他植物的攻擊位置集合，則Zombie會被瞬間消滅而所在位置的植物則安然無恙（在我們的設(shè)定中，Plant的攻擊位置不包含自身所在位置，否則你就不可能擊潰它了）。Zombies的目標(biāo)是對Plants的陣地發(fā)起進(jìn)攻并獲得最大的能源收入。每一次，你可以選擇一個可進(jìn)攻的植物進(jìn)行攻擊。本題的目標(biāo)為，制定一套Zombies的進(jìn)攻方案，選擇進(jìn)攻哪些植物以及進(jìn)攻的順序，從而獲得最大的能源收入?！据斎胛募枯斎?/p>

6、文件pvz.in的第一行包含兩個整數(shù)N, M，分別表示地圖的行數(shù)和列數(shù)。接下來N×M行描述每個位置上植物的信息。第r×M + c + 1行按照如下格式給出植物Pr, c的信息：第一個整數(shù)為ScorePr, c, 第二個整數(shù)為集合AttackPr, c中的位置個數(shù)w，接下來w個位置信息（r, c），表示Pr, c可以攻擊位置第r 行第c 列。【輸出文件】輸出文件pvz.out僅包含一個整數(shù)，表示可以獲得的最大能源收入。注意，你也可以選擇不進(jìn)行任何攻擊，這樣能源收入為0?！据斎霕永? 210 020 0-10 0-5 1 0 0100 1 2 1100 0【輸出樣例】25【樣

7、例說明】在樣例中, 植物P1,1可以攻擊位置(0,0), P2, 0可以攻擊位置(2,1)。一個方案為，首先進(jìn)攻P1,1, P0,1，此時可以攻擊P0,0 。共得到能源收益為(-5)+20+10 = 25。注意, 位置(2,1)被植物P2,0保護(hù)，所以無法攻擊第2行中的任何植物?！敬笾聰?shù)據(jù)規(guī)模】約20%的數(shù)據(jù)滿足1 N, M 5；約40%的數(shù)據(jù)滿足1 N, M 10；約100%的數(shù)據(jù)滿足1 N 20，1 M 30，-10000 Score 10000管道取珠【問題描述】管道取珠是小X很喜歡的一款游戲。在本題中，我們將考慮該游戲的一個簡單改版。游戲畫面如圖1所示：(圖1)游戲初始時，左側(cè)上下兩個

8、管道分別有一定數(shù)量的小球（有深色球和淺色球兩種類型），而右側(cè)輸出管道為空。每一次操作，可以從左側(cè)選擇一個管道，并將該管道中最右側(cè)的球推入右邊輸出管道。例如，我們首先從下管道中移一個球到輸出管道中，將得到圖2所示的情況。(圖2)假設(shè)上管道中有n個球, 下管道中有m個球，則整個游戲過程需要進(jìn)行n + m次操作，即將所有左側(cè)管道中的球移入輸出管道。最終n + m個球在輸出管道中從右到左形成輸出序列。愛好數(shù)學(xué)的小X知道，他共有C(n+m, n)種不同的操作方式，而不同的操作方式可能導(dǎo)致相同的輸出序列。舉個例子，對于圖3所示的游戲情形：(圖3)我們用A表示淺色球，B表示深色球。并設(shè)移動上管道右側(cè)球的操作

9、為U, 移動下管道右側(cè)球的操作為D，則共有C(2+1,1)=3種不同的操作方式, 分別為UUD, UDU, DUU；最終在輸出管道中形成的輸出序列（從右到左）分別為BAB，BBA，BBA?？梢园l(fā)現(xiàn)后兩種操作方式將得到同樣的輸出序列。假設(shè)最終可能產(chǎn)生的不同種類的輸出序列共有K種，其中第i種輸出序列的產(chǎn)生方式(即不同的操作方式數(shù)目)有ai個。聰明的小X早已知道，因此，小X希望計算得到你能幫助他計算這個值么？由于這個值可能很大，因此只需要輸出該值對1024523的取模即可(即除以1024523的余數(shù))。說明：文中C(n + m, n)表示組合數(shù)。組合數(shù)C(a, b)等價于在a個不同的物品中選取b個的

10、選取方案數(shù)?！据斎胛募枯斎胛募all.in第一行包含兩個整數(shù)n, m，分別表示上下兩個管道中球的數(shù)目。第二行為一個AB字符串，長度為n，表示上管道中從左到右球的類型。其中A表示淺色球，B表示深色球。第三行為一個AB字符串，長度為m，表示下管道中的情形?！据敵鑫募枯敵鑫募all.out僅包含一行，即為除以1024523的余數(shù)?！据斎霕永? 1ABB【輸出樣例】5【樣例說明】樣例即為文中(圖3)。共有兩種不同的輸出序列形式，序列BAB有1種產(chǎn)生方式，而序列BBA有2種產(chǎn)生方式，因此答案為5?！敬笾聰?shù)據(jù)規(guī)?！考s30%的數(shù)據(jù)滿足 n, m 12；約100%的數(shù)據(jù)滿足n, m 500。描邊【問

11、題描述】小Z自幼就酷愛數(shù)學(xué)。聰明的他特別喜歡研究一些數(shù)學(xué)小問題。有一天，小Z在一張紙上選擇了n個點，并用鉛筆將它們兩兩連接起來，構(gòu)成n(n-1)/2條線段。由于鉛筆很細(xì)，可以認(rèn)為這些線段的寬度為0。望著這些線段，小Z陷入了冥想中。他認(rèn)為這些線段中的一部分比較重要，需要進(jìn)行強(qiáng)調(diào)。因此小Z拿出了毛筆，將它們重新進(jìn)行了描邊。毛筆畫在紙上，會形成一個半徑為r的圓。在對一條線段進(jìn)行描邊時，毛筆的中心(即圓心)將從線段的一個端點開始，沿著該線段描向另一個端點。下圖即為在一張4個點的圖中，對其中一條線段進(jìn)行描邊強(qiáng)調(diào)后的情況?，F(xiàn)在，小Z非常想知道在描邊之后紙面上共有多大面積的區(qū)域被強(qiáng)調(diào)，你能幫助他解答這個問題

12、么？【輸入文件】這是一道提交答案型試題，所有的輸入文件 path1.inpath10.in 已在相應(yīng)目錄下。輸入文件 path*.in 第一行包含一個正整數(shù)n，表示選擇的點的數(shù)目。第2至第n+1行，第i+1行有兩個實數(shù)xi, yi，表示點i的坐標(biāo)為(xi, yi)。第n+2行有一個正整數(shù)m，表示小Z認(rèn)為比較重要的線段的條數(shù)。第n+3至第n+m+2行，每行有兩個正整數(shù)a, b表示一條線段。a, b兩個數(shù)分別表示該線段的兩個端點的編號。第n+m+3行，有一個實數(shù)r，表示毛筆在紙上形成的圓的半徑。第n+m+4行，有四個實數(shù)p1, p2, p3, p4，為評分使用的參數(shù)?！据敵鑫募枯敵鑫募ath*.out僅包含一行，即為描邊后被強(qiáng)調(diào)區(qū)域的總面積。【輸入樣例】21 11 211 210.00001 0.001 0.1 1【輸出樣例】5.1415927【樣例說明】如下圖所示?！驹u分標(biāo)準(zhǔn)】每個測試點單獨評分。本題設(shè)有4個評分參數(shù)p1,p2,p3,p4 (p1< p2