第一屆機房病毒杯NOIP提高組模擬賽試題+題解

現在距離第一屆機房病毒杯的舉行（2008年11月9日）已經過去了將近一年的時間。我也順利獲得了當年的NOIP一等獎，現在我以文化課作為主要努力方向。

為了更好的造福廣大OIer，我決定逐漸公開和整理一些OI資料，於是就從《第一屆機房病毒杯NOIP提高組模擬賽》開始吧。因為這是第一屆（或許是最後一屆？）我自己主辦的NOIP比賽，所以具有一定的紀念意義。值得說明的是，當初這屆比賽就是為了模擬NOIP，所以難度很低。

題目一、十一月十五日的快樂

背景 Background

終於到了一年一度的11月15日，神牛OIer 們又可以去刷題了。今年參加NOIP的人特別多。某省的參賽地點排滿了長隊。人們在路上驚奇的發現，有很多老同學、老朋友也參加了比賽。一路上，人們談笑風生，興奮不已……考完了NOIP，大家又一路同行回到了各自的家，開始了狂歡夜。

多麼令人期待和興奮的一天！不過其實，人們最高興的還不是遇見老朋友，而是結交新朋友。可是結交新的朋友就需要很多時間，而除了考試之外時間並不多。例如小L，他在NOIP的入口處等待開門時，決定趁機和其它市縣的牛們多套近乎。可是隊伍太長，且人們都很自覺的站成僅僅一列，而小L又很想多交不同地方的朋友，因此小L想知道他在哪一個區域內可以結交到最多的不同地方的朋友。當然，這個區域不能太大，否則還沒考試他就累死了。

題目描述 Description

現在有n個人，題目給出了他們每個人所在市縣的編號。他們站在一個從左向右的隊伍中。小L不在隊列中。他想找到一個長度不超過D的區域，使他能夠找到最多的不同地方的朋友。要求輸出能找到的朋友所在不同市縣的最大數和找到這些朋友的最小區間長度。比如在整個隊伍內他按從左向右順序找到了3個A地朋友，1個B地朋友，1個C地朋友。假設D = 5，那麼不同市縣的最大數為3（A地、B地、C地），最小區間長度為3（只須結交A地的最右面的一個人即可得到最大市縣數3，因此區間長度不是5而是3）。假設在隊伍內的人他都還沒有結交。

數據範圍

對於 100% 的數據，保證5<=n<=1000000, 1<=D<=n, 所有市縣編號不超過32767。

輸入格式

輸入文件第一行為兩個正整數n，D。分別表示隊伍人數和他想找到的最長的區間長度。 接下來的n行，每行有一個整數，表示每個人所在市縣的編號（從左向右）。

輸出格式

輸出數據為一行，這行有兩個整數，用空格分開，按順序分別代表能找到的朋友所在不同市縣的最大數和找到這些朋友的最小區間長度。

樣例輸入

5 4 1 1 1 2 3

樣例輸出

3 3

解題報告

本題有O(n)的算法。我們發現，區間長度最小時，一定是從一組相同市縣的最後一個開始，到另一組相同市縣的第一個結束。因為這兩個向前後延伸，都是相同的市縣，對找到朋友數沒有貢獻，還增加了區間長度。 故我們可以採用逐個掃描各人的市縣編號，並維護一個數組，用以保存當前最大不超過d的長度下各市縣的人數。用首尾指針記錄當前區間位置。用一個計數變量計算當前不同的市縣編號個數，若大於當前最優值，則立即更新;若相等，則選擇區間長度小的。 維護數組頭指針：人數標記數組頭指針對應元素加一。若原來為零，即原來不存在這個市縣，市縣計數變量加一，表示這個市縣被選中。 維護數組尾指針：1、如果尾指針對應市縣對應的人數大於一，則最末端的人沒有必要，尾指針向前推一位。2、若首尾指針之差大於d，則區間過長，不滿足題意，尾指針前移;若發現「必須去掉」的尾指針對應元素不再存在，即數組值為零，計數變量減一，表示這個市縣不再被選中。 注意，必須先維護頭指針再維護尾指針，否則在首尾對應元素恰好相等的情況下，尾指針查詢對應市縣人數時可能出錯，由於未加上頭指針對應元素。應該先維護與當前狀態無關的頭指針。 具體實現時，利用頭指針一一增加的特性，用一個循環變量i充當頭指針。尾指針則由初值為1的變量j充當。注意長度是i-j+1，不是i-j。根據以上分析，程序就不難寫出了。 由於C語言運算較快，易於通過。Pascal語言的程序需要常數級優化才能通過。

考察內容

看題能力、建模和優化算法的能力、根據數據範圍確定時間複雜度要求的能力、隊列數據類型和指針的應用。

題目二、機房病毒

背景 Background 我們機房中了病毒，因此幾乎什麼都無法正常進入。為了解決這個病毒，我們花了好幾天。終於在大家的共同努力下，病毒不再猖狂了。 題目描述 Description 我們的機房的所有計算機組成了一棵樹，這是由於病毒，計算機無法兩兩完全連通的結果。所以，每臺計算機能夠直接連通的是它的孩子計算機和父親計算機。話說某天晚上，我們發現病毒絕跡了，但是我們無法確認是否真的消滅乾淨了。因此我們需要派一些同學犧牲上課時間看守住所有的電腦兩個小時，以確認沒有任何病毒痕跡才能放心。我們當然想少耽誤同學們的學習時間。因此我們需要找出一種方案，使所需要的看守人員最少。直接連通的兩臺計算機只需要一個人即可看守住。

數據範圍對於 100% 的數據，保證n≤1500。

輸入文件中數據表示一棵樹，描述如下： 第一行 N，表示樹中結點的數目。 從第二行開始，每行描述每個結點信息，依次為：該結點標號i，k(後面有k條邊與結點I相連)，接下來k個數，分別是每條邊的另一個結點標號r1，r2，…，rk。 對於一個n(1 < n <= 1500)個結點的樹，結點標號在0到n-1之間，在輸入文件中每條邊只出現一次。

輸出數據只有一行，表示至少需要耽誤多少學生的學習時間。

關於本題目的特別說明

因原題解有問題，而本題是本屆中最有難度的一道題，為了給大家留下思考空間（當然，實際上這套題最有難度的本題也很簡單），暫時不放上新題解。只提醒大家這是一道樹形DP。

題目三、風月提序

背景 Background

蘭亭臨帖 行書如行雲流水 月下門推 心細如你腳步碎 忙不迭 千年碑易拓 卻難拓你的美 真跡絕 真心能給誰 牧笛橫吹 黃酒小菜有幾碟 夕陽餘暉 如你的羞怯似醉 摹本易寫 而墨香不退與你共留餘味 一行硃砂 到底圈了誰 無關風月 我題序等你回 懸筆一絕 那岸邊浪千疊 情字何解 怎落筆都不對 而我獨缺 你一生的瞭解 彈指歲月 傾城頃刻間煙滅 青石板街 回眸一笑你婉約 恨了沒 你搖頭輕嘆誰讓你蹙著眉 而深閨 徒留胭脂味 人雁南飛 轉身一瞥你噙淚 掬一把月 手攬回憶怎麼睡 又怎麼會 心事密縫繡花鞋針針怨懟 若花怨蝶 你會怨著誰 無關風月 我題序等你回 手書無愧 無懼人間是非 雨打蕉葉 又瀟瀟了幾夜 我等春雷 來提醒你愛誰 題目描述 Description 現李風正使毛筆而題序，臨風月而賦詩。詩長而情切，然以之長而視之亂，無心以斷行。望神牛幫之。（現已斷句） 本題沒有明確的數據範圍，但輸入數據保證你所寫的代碼中的正確、完整的純文件輸入和輸出操作在運行時用時不會超過時限的二分之一。

備註 Tip

提示：漢字的兩個字節的每個字節的ASCII碼均和空格及四種英文標點不同。不用考慮其它標點符號。 由於輸入文件可能是一本長篇小說，因此請注意防止變量和數組的溢出。 最後一行內容後可以輸出也可以不輸出換行符。

輸入輸出數據

第一行有一個數字，表示他希望每一行擁有多少字符。（不超過500字符） 剩下的輸入文件中的數據表示一篇序或一首詩。 輸入數據保證不包含換行符(字符13或字符10)。

輸出數據表示你幫李風題的序或賦的詩斷行後的結果。如果行的末尾的詞語或短句沒有結束（即其後字符不是空格或標點(只考慮,.?!四個半角英文符號。)），則需要等該詞結束後在換行。 輸出數據要儘量使每行字符數接近輸入要求，但不能刪除任何字符，也不能小於要求字符，最後一行除外。

樣例輸入

10

無關風月 我題序等你回

 手書無愧 無懼人間是非

 雨打蕉葉 又瀟瀟了幾夜

 我等春雷 來提醒你愛誰

樣例輸出

無關風月 我題序等你回 手書無愧 無懼人間是非 雨打蕉葉 又瀟瀟了幾夜 我等春雷 來提醒你愛誰 (樣例說明 請注意觀察樣例輸出從第二行起，每行開頭為一個空格，請仔細思考這是為什麼。)

解題報告

沒什麼好解釋的，送分題目。細心即可。

題目四、心靈的撫慰

背景 Background 病毒問題解決後，神牛們的心靈久久不能平靜。有個神牛因此已經「亂了」。他腦子中滿是程序（否則怎麼會成為神牛呢），而且他可以從一個程序聯想到一些相似的程序。比如從程序1聯想到2，從2聯想到4，從4聯想到6，從6聯想到9……躺就像搜索一樣一步一步越陷越深。不過同一種聯想他只會聯想一次。比如1、2之間他進行了一次聯想，那麼他不會再重新聯想1到2，或2到1。眼看他又要亂了，有人突然想到，如果他剛開始時想到的程序能夠經過聯想若干次後聯想回到原程序，那不就亂回來了嗎？由於神牛馬上就要開亂，請在1秒內告訴他，他需要想哪個程序，以便亂回來。 題目描述 Description 給出一些程序和他們互相聯想的關係（如果兩個程序A、B有聯繫，神牛可以從A聯想到B，也可以從B聯想到A，但A、B之間神牛最多聯想一次），請告訴神牛他需要想哪個程序，以便在最短的時間內亂回來，並輸出這個最短時間。 數據範圍 對於100% 的數據，n≤250。

輸入第一行有兩個正整數N，M，分別表示程序個數和有多少對程序可以被神牛直接互相聯想。 以下M行，每行三個正整數，分別表示一種聯想的兩端的程序的編號（從1開始），以及進行這種聯想所需要的最短時間。

輸出：如果神牛無論如何都再也亂不回來了，輸出「He will never come back.」。 如果神牛能夠亂回來，請輸出神牛會亂多長時間。

例如輸入：

4 3 1 2 10 1 3 20 1 4 30

輸出：

He will never come back.

題解

本題是一個典型的求圖中最小環算法。 算法的主旨是： 1、用Floyed算法求出點到點最短距離。枚舉中間節點，再枚舉兩邊節點（注意枚舉順序），若兩邊節點到其距離之和比原來兩點之和小，則執行鬆弛操作，更新兩邊節點距離。 2、再枚舉三個節點，看這三個點繞一圈所需時間（d

\[a,b\]

+dis

\[b,c\]

+d

\[c,a\]

），更新最小值。可以證明，任意一個環都可以經過Floyed點對點簡化後形成一個由一條鬆弛後的邊和兩條原始邊構成的三角形。注意，三條邊至多有一條是鬆弛後的，否則有可能重複路徑，形成直線往返。若環不存在，則輸出無解。 此算法同樣適用於有向圖，只是需要注意繞圈方向嚴格（下面的程序中不是嚴格繞圈，應修改為首尾相接）

更多信息請到 RQNOJ (點擊進入) 查閱。