國家集訓(xùn)隊作業(yè)1

1、IOI2007 中國集訓(xùn)隊第二輪作業(yè)(截止時間：2007 年 4 月 30 日)：作業(yè)提交：r, liurjmail本次作業(yè)主要為算法討論。注意：所有表格的各列都是：題號、題目名稱、題目大意（如沒有填寫或者覺得寫得不夠詳細則請大家寫算法時請補充完整）、算法討論/說明。最果后一列在填寫時應(yīng)先刪除的說明文字。請選擇至少 50 道表格中的題目（表格中需填寫詳細內(nèi)容），提交帶注釋程序(Commented Program)。本文檔很長（50 頁），但并不是所有表格都需要填寫。事實上，只有小部分需要填寫。之所以有這么長的表格主要是提供一個做作業(yè)的靈活性，而題目大意也是給沒有做過這些題目的同學(xué)為選擇題目提供

2、便利。第一部分 算法討論題目為推薦（但不是必須）討論。鑒于完整性，一些重紅色題目至少需要寫一半。要比賽的簡單題目也列在表里，這些題目可以不寫，但如果碰巧做過，或者有做，也歡迎寫出。表格中已有的“題目大意”和“算法討論”是對此題的說明，以節(jié)約同學(xué)們的看題時間，可以有性的選擇感的題目研究。填寫表格之前不必編程通過測試數(shù)據(jù)，但如果通過，請注明。由于部分題目有相當(dāng)?shù)碾y度，僅靠完成的會比較大，希望大家多多交流與討論。表格需要完成寫，但是思路可以相互啟發(fā)。1. ACM/ICPC World Finals 2002-2006 (10 紅 21 藍)部分題目提交：()簡介：有不少有啟發(fā)意義的題目，不卡時間，值

3、得討論。另外不少的題目的細節(jié)比較關(guān)鍵，看上去比較簡單但實際上并不容易通過。World Finals 20063561LowCost Air Travel給一些機票信息與旅行安排，求花費最小的方案。最短路，但是容易想錯3562Remember theALa Mode!計算冰激凌派的最小和最大銷售額費用流3563Ars Longa由球關(guān)節(jié)連接的輕桿系統(tǒng)是否靜止、穩(wěn)定判定平衡的問題已經(jīng)很好的解決，時間復(fù)雜度、正確 性和編程復(fù)雜度都很好。但是，穩(wěn)定性的判定，我暫時沒有想到好的辦法。如 果穩(wěn)定是指附加一個力，仍然平衡的話，WC 的那個方法應(yīng)該是對的吧，只要 XYZ6 個方向都加個力試下就可以了，O（N4

4、）的。我試過這種算法，沒 TLE， 是 WA。如果不是精度問題，或者我寫錯的話，就是穩(wěn)定性理解錯了。物理上，穩(wěn)定還有另外一種理解（和重力勢能有關(guān)）：對此，WC 期間那個任意加一個力，方程組是否有解的方法是錯的：比如把某鉸鏈看成一個吊鐘，被一個輕桿垂直連接，豎直地吊著；此時，任意給一個水平的力，方程顯然都是無解的，但此是穩(wěn)定的。因此，不難想到一種物理上經(jīng)常用到的 穩(wěn)定性的方法：對于任何微小的擾動， 整個系統(tǒng)的中心是否下降，如果有下降，那么系統(tǒng)是不穩(wěn)定的；如果系 統(tǒng)的重心不論怎么動，只會上升的，那么系統(tǒng)是穩(wěn)定 的；如果系統(tǒng)對于某一擾動重心不變，那么這個系統(tǒng) 是隨遇平衡的（也就是擾動一下，系統(tǒng)就動一

5、下，擾 動停止，系統(tǒng)就馬上又靜止，比如光滑水平面上的一 個球，它是隨遇平衡的），這種情況在題目中，應(yīng)該也屬于平衡的狀態(tài)。3564Bipartite Numbers給出 n，求最小倍數(shù)使得它只包含兩個數(shù)字比較有啟發(fā)意義的數(shù)論題3565Bit Compressor給一種不可逆的壓縮方法， 給定壓縮后文本與壓縮前的長度與 1 的個數(shù)，是否可以解壓縮動態(tài)，理論上狀態(tài)比較多但實際用到的很少。有 的同學(xué)可以仔細研究一下。3566Building Clock給出一些不同類型的齒輪和無限量的軸（其中一個的轉(zhuǎn)速恒定），要求讓兩個軸的轉(zhuǎn)速分別等于時針和分針。每個軸上最多三個齒輪。細節(jié)不知道哪里處理錯了3567Pi

6、lgrimage一些人去朝圣，途中有人離開或者加入，每次需要分錢時總錢數(shù)恰好都是人數(shù)的整數(shù)倍，求原先的人數(shù)可能值一道看上去比較迷惑人的題3568Pockets把n*n 紙片折疊成1*1 后統(tǒng)計 Pockets 的個數(shù)我將每個正方形的信息都儲存下來了，總的復(fù)雜度是 O（N3）的，想起來感覺很簡單，正確性很顯然， 程序也很好寫，但就是 WA。YEAH！REJUDGE 了，AC 了，正確率有 90%，看來這題不應(yīng)該紅的3569Degreesof Separation求出無向無權(quán)圖最短路的最大值簡單題，不用寫了。3570Routing給出有向無權(quán)圖，求出點 1到點 2 與點 2 到點 2 的兩條路，使

7、得包含的總結(jié)點數(shù)盡量少。World Finals 20053269Eyeball Benders給出由水平垂直線段組成的兩幅圖， 第一幅是否為第二分局部放大得到。至少有一個端點同時出現(xiàn)在兩幅圖中。枚舉匹配的點 N2，難點就是找出比例 K。首先，為了方便起見，我對所有的線段，以及線段的 端點都進行了排序。事實證明，這是很明智的，否則 后面寫 if 很有可能寫到瘋狂。并且，排序以后，最后的匹配就成了 O（N）的，否則要 N2，感覺此題 N4 是要 TLE 的（N = 2*50 = 100）。方法找 K 是 O（N）的，最后匹配時先做一個排序 O（NLOGN），然后 O（N）看一次（有特殊情況，程序

8、里面有說明，不影響總的時間復(fù)雜度），所以總的復(fù)雜度是 O（N3LOGN）。為了方便，我默認枚舉的匹配點是橫線的端點，一次 搞好以后，對兩個圖都旋轉(zhuǎn) 90 度，重新排序，再檢查一次，就等于橫線豎線都枚舉到了。確定 K 分 4 個情況：1、 PUZZLE 中除了枚舉的點，還有其它的點，肯定是某線段端點。此時，尋找枚舉點到該點的射線 上離枚舉點最近的點，并尋找 SOLUTION 中同斜率射線上離枚舉點最近的點，既可知道 K。2、 否則，如果 PUZZLE 中有不經(jīng)過枚舉的點的直線（可以證明，該直線必定是極長的、頂牢邊框的）。 此時，找到這樣的直線中，離枚舉點距離大于 0 的最近的直線，與 SOLUT

9、ION 中離枚舉點最近的直線做對比，就可以得到 K。3、 否則，如果 PUZZLE 中只有一條線段。不用確定K，直接看 SOLUTION 中有無直線就可以。4、 否則，PUZZLE 只可能剩下一種情況，2 線段， 豎線經(jīng)過橫線枚舉的那個端點。也不用確定 K， 只要看 SOLUTION 中有無橫線與豎線相交即可。3270Simplified Network總是連接到最近的基站。給出起點和終點，求更換 網(wǎng)絡(luò)次數(shù)最少的路線。從概念上要先求 Voronoi 圖，但實際上不需要顯式的把它表示出來。3271The Traveling Judges Problem給出無，求連接其中某些點（Judge 和目的

10、地） 且總距離最小的方案?？梢悦杜e附加點，然后求 MST。有的同學(xué)可以討論一下有哪些方法可以減少計算量。3272cNteSahruP fefrlefe洗牌時每次最多犯一個錯誤（交換兩張牌）。給出洗牌后的結(jié)果，求出洗牌次數(shù)和犯的錯誤。如果多解則輸出犯錯誤最少的方案。如果還是多解則輸出字典序最小的方案。3273LotsofSunlight給出一些房子的層數(shù)和距離，計算每個房間被陽光照射的時間段3274Crossing Streets地圖上有一些街道，用線段表示。給出起點和終點，求出穿過街道最少的方案。不在街道的端點和交叉點處穿過。很傳統(tǒng)的題目，但要簡潔、無錯的寫出代碼也需要一 番工夫3275Til

11、ingthe Plane給出邊與坐標(biāo)軸平行的簡單多 ， 它是否能覆蓋整個平面。3276TheGreat Wall Game用最少移動棋子使得它們共線（行、列、主對角線）可以用二分圖最佳匹配求解，但也可以貪心。3277Workshops為一些 Workshop 安排房間，使得無法安排房間的Workshop 數(shù)量盡量少。如果 多 解 則 讓 參 加 這 些Workshop 的總?cè)藬?shù)盡量少類似上題，可以用二分圖最佳匹配求解，也可以貪心。3278Zones給出 n 個 tower 服務(wù)的人數(shù)和各個公共服務(wù)區(qū)域的人數(shù)，選擇其中一些 tower 使得被服務(wù)的總?cè)藬?shù)盡量大World Finals 20042

12、993Carlthe Ant給出第一只螞蟻 Carl 的路線，模擬所有螞蟻的移動?？梢杂懻撘幌鲁绦?qū)崿F(xiàn)細節(jié)和容易錯的地方2994Heliport給出各邊平行于坐標(biāo)軸的簡單多 ，在內(nèi)部放一個盡量大的圓。2995ImageIs Everythingn*n*n 的積木有的地方空心，其他 。實心塊都涂有顏色。同一個 塊各面顏色相同。給出從 6 個方向看到的圖案，求包含實心塊的總數(shù)的最大值方法比較有啟發(fā)性。2996Insecurein Prague給出一種加密方法，求出最長可能的原文。2997Intersecting Dates給出一些已提供股票價格的日期區(qū)間，以及需要信息的日期區(qū)間，計算出還有哪些日期

13、需要提供。日期都是1700 年以后。2998Merging根據(jù)規(guī)則把小地圖合并成Maps大地圖2999Navigation給出一些由移動信號源發(fā)出的信號（可能在不同時刻發(fā)出），確定 當(dāng)前位置與目標(biāo)位置所成的角度。信號源移動速度和信號速度已知。比賽的時候很少有隊伍提交此題，但耐心看完題后稍 加分析就會發(fā)現(xiàn)其實不難3000Tree-Lined Streets給一些街道，在上面種盡量多的樹。同一街道旁的樹距離不小于 50 米，且離街道的交叉口不超過 20 米。3001Suspense!在兩個大樓中間架一座橋， 使得任何一只寵物貓都不能通過橋 任何一只寵物鳥。要求橋上的繩索盡量長。一道很有意思的題目。

14、3002Air Traffic Control給出一些飛機的位置和一些中心。每個中心有一個半徑，所有距離在半徑內(nèi)的飛機被，恰好等于半徑的飛機可能被也可能不被。輸出恰好被 0, 1, 2個中心的飛機個數(shù)。關(guān)鍵在于邊界上的處理。雖然算法不難但其實細節(jié)是 比容易錯的。World Finals 20032721Building Bridges用盡量少的橋把所有物連在一起2722Light Bulbs每個開關(guān) 連續(xù) 。操作開關(guān)以到達目標(biāo)狀態(tài)。多 輸出十進制表示最小的一個。2723Ridingthe Bus給出 Bus 的遞歸描述，求兩點間的距離。2724Eurodiffusio n給出一些 和 之間的城

15、市，模擬歐元擴散的過程。2725Covering Whole Holes給出邊平行于坐標(biāo)軸的簡單多 洞和蓋子，問蓋子是否可以覆蓋洞。不能旋轉(zhuǎn)只能平移不錯的幾何題目。2726Combining Images給出兩個黑白圖形的 Hex四分樹表示，求二者的交2727ALinking Loader實現(xiàn) Linker 的部分功能。2728A Spy in the Metro從站 1 出發(fā)，必須在指定時刻到達站 n。設(shè)計路線使得他在站臺上等待的時間盡量短。2729TheSolar System給出太陽系內(nèi)兩個行星的長短半軸長度，行星 1 的周期，計算行星 2 在特定時刻的位置2730Toll從 A 地到達

16、 B 地需要經(jīng)過一些村莊和小鎮(zhèn)，夠成一個無 。若初始時的物品有X 個，則過村莊時要繳納 1 個 ， 過 小 鎮(zhèn) 時 要 繳 納ceil(X/4)個。為了到達 B 時有 Y 個物品，一開始需要帶多少個？World Finals 20022474Ballons in a Box求氣球的膨脹順序使得氣球的總體積最大。簡單枚舉即可。但不知道是否存在一種保證正確的貪 心方案。大家可以討論一下。2475Undecodable Codes給出一個 01 CodeSet，求出讓 方式不惟一的最短串，多 輸出字典序最小的。見算法藝術(shù)與信息學(xué)競賽p1322476Crossing the Desert在沙漠里走 則

17、消耗 一 。在綠洲里足量的水，也可以儲存 以備以后使用。要求在起點處至少要買多少食物。能帶的 與水的總量有限制。見算法藝術(shù)與信息學(xué)競賽p3102477Ferries連接兩地的路線有一些湖泊也有平地。穿過湖泊需要等待渡船，而在平地上可以按任意速度行進。在到達時刻最早的前提下讓最大速度盡量小?，F(xiàn)場比賽的時候的隊伍 WA 了無數(shù)次，至今也不知道錯在哪里。哎，過了這題就奪冠了2478Island Hopping修建最小生成 讓所有島嶼連接在一起并接入Internet。每條光纜的修建速度一樣（與長度成正比），計算所有居民接入 Internet 的平均時間。2479Toil for Oil給簡單多和一些漏

18、油點，問一共能裝多少油。不錯的幾何題。2480Partitions求兩個Partition 的交與并。先求輪廓交與并，然后再改造成合法的 Partition。比較有啟發(fā)性的題目。2481Silly Sort用交換元素的方法排序，每次交換的費用為兩數(shù)之和。用盡量少的總費用排序。見算法藝術(shù)與信息學(xué)競賽p2472482Merrily, We Roll Along!一個 在水平/垂直線段組成的路徑上滾動，求圓心移動的總距離。不錯的幾何題。思路有兩種，見 WinterCamp2007 教練的講稿2. ACM/ICPC Centrol European 2004-2006簡介：這三年的 CERC 從波蘭轉(zhuǎn)

19、移到了匈牙利，但題目的質(zhì)量沒有降低。而且命題者和以前比較起來更加幽默（大家可以從題目的文字中感受到這一點）。2004 年的題目更是出人意料的全部和中國有關(guān)。CERC 20063713Astronauts給三個任務(wù)分配人選。任務(wù) A 人選的 需要大于等于平均 ， 任務(wù) B 需要小于平均，任務(wù) C 沒有限制。相互討厭的人不能分配到同一任務(wù)。3714Bridges把 2n 個工廠分配到河的，各 n 個工廠。一些工廠之間必須直接相連，可以造橋（必須在不同岸），也可以空運。橋不能交叉，只有兩架直升飛機可以用來空運，求一種可行方案。3715Chimes有若干個正弦波發(fā)生器，給出疊加后的采樣點，確定各種類型

20、的發(fā)生器有多少個在工作。第i 個發(fā)生器的頻率為10*2iHz，采樣頻率恰好最后一個發(fā)生器頻率的兩倍。3716DNA Regions給出兩條 DNA 鏈，找出最長的區(qū)域使得該區(qū)域的突變位不超過p%3717Education Radio Programme在(0,0)處最多放 m 個天線，每個天線可以廣播一定角度的范圍。求出讓 n 個點都被廣播到的最小花費。每個天線的費用為它的角度的平方。3718Fast Track給出 n 個城市的位置和人口，建立一個直線鐵軌使得能乘坐火車的人數(shù)盡量多。城市離鐵軌的直線距離不超過 1km 時可以乘坐火車。3719Grass is Green每個人都用所有的錢買土

21、地、種草和修籬笆。土地的價格是統(tǒng)一的，但每個人買的草和的價格不一樣。每個人的土地必須是正方形。給出每個人的錢和草與 的價格，統(tǒng)計有多少人的土地比你大3720Highways統(tǒng)計 n*m 網(wǎng)格全連接后有多少條非水平和垂直的線3721Islands給出網(wǎng)格，確定每個島嶼（四連塊）并計算出最小/ 最大的面積/ 周長。島嶼可以包含湖泊（ 內(nèi)邊界算在周長中），但湖泊中如果還有其他陸地，則算作不同的島。3722Jewel-eating Monsters題目說了一個很幼稚的故事：一個人在一個洞里過了 n 個晚上，每個晚上扔一枚金幣到湖里第二天金幣就變?yōu)樵瓉恚ㄈ拥艚饚藕螅?的 a 倍。后來他到珠寶行里換了珠寶

22、，每個珠寶價值 c 個金幣，他換了盡量多的珠寶。最后他遇到了吃珠寶的怪獸，把他所有的珠寶全都吃了。問他最后還剩多少硬幣=.=3723Knowledge Transfer給 n 個學(xué)生安排 d 天的課程，每天有兩個班，長度均為 2 小時，必須在 22:00 之前開班。兩個班的時間可以重疊。給出每個學(xué)生每天可以學(xué)習(xí)的時間（為一個區(qū)間），安排每天的兩個班的開始時間， 并給每個學(xué)生分配一個班CERC 2005 (CII)測試數(shù)據(jù)：3523Knightsofthe Round Table每次圓桌會議由至少3 個騎士參加，騎士的數(shù)目必須為偶數(shù)，且在圓桌旁坐下后相鄰騎士不能相互憎恨。統(tǒng)計有多少個騎士不可能參

23、加任何一個會議。3524The Cow Doctor有一些測試原料可以用來檢測瘋牛病。每個原料用一個集合表示。有多少個原料可以由其他原料得到（即：它等于其他若干集合的并）？3525Wild West每個人用一個三元組(a,b,c) 表 示 ， 1=a,b,ca要么 bb要么cc。3510Pixel Shuffle在一個 n*n 黑白圖象上做一個最多包含 32 個動作的 pixel shuffle（旋轉(zhuǎn)、對稱、行混合等）序列，問重復(fù)做幾次后會得到原圖象？3527Find the Clones給 n 個長度為 m 的DNA 串，統(tǒng)計恰好出現(xiàn) i 次的串的個數(shù)3528The Warehouse在一個

24、迷宮中，每次可以移動一格也可以把一個高度為 h 的 box 放倒（然后將占據(jù)連續(xù)h 個格子）。求到達出口的最小步數(shù)。3529Widget Factory給出一些制造 widget 的信息：開始時間、結(jié)束時間（均用 weekday 表示） 和制造的各widget 類型，求每個widget 的制造時間（保證為 3 到 9）3530Martian Mining給出 n*m 網(wǎng)格中每個格子的 A 礦和 B 礦的數(shù)量，A 礦必須由右向左 ，B 礦必須由下向上 。管子不能拐彎或者間斷。要求收集到的 AB 礦總量盡量大。3531Word Rings把一些單詞組成一個word ring，每個單詞的后兩個字母與

25、后一個單詞的前兩個字母相同。要求單詞的平均長度盡量大。3532Nuclear Plants有兩種圓：半徑 0.58 和 1.31，求覆蓋的總面積CERC 2004 (CII)3176Art of War給出地圖（用線段集合表示，每條線段的兩側(cè)必為不同區(qū)域），每個的為首都所在區(qū)域哪些在發(fā)假設(shè)相鄰必然發(fā)）算法不難但不好寫3177Guards給一個圈，圈上第 i 個人想要 i 種不同的東西。相鄰兩個人不能有同種東西。一共需要多少種東西才能滿足所有人的需要？3212Crime給一個無 可能有重邊），選擇一些點，使得所有邊恰好有一個端點被選擇。要求所選點盡量少。可能無解初看起來不可做，但仔細3179De

26、sert在 n 個點中選 3 個安裝 ，使得所有點都能收到這三個臺的電視 。每個需要選擇一個信號發(fā)射方向，則 45 度內(nèi)的點都可以收到 。要求總安裝費用盡量小。雖然點不太多，但是也要考慮時間復(fù)雜度3180Explore給平面上 n 個村莊，選一個開始旅行，每天最多走 30km，可以在任何村莊過夜但不能在野外過夜。每個村莊都有一定數(shù)量的修道院， 要求可以到的修道院總數(shù)盡量多。3181Fixing the Great Wall被看作一條直線段，有 n 個點需要修復(fù)。每個點的修復(fù)費用為 ci+tidi，其中 ti 為修的時間，(ci,di)為描述該損壞點的參數(shù)。要求修復(fù)總費用盡量小。比較經(jīng)典的動態(tài)了

27、。3182Gambling在一個 中，你有四種方法可以修改你的pebble 個數(shù)。每次操作后的 pebble 數(shù)目不得超過最初的個數(shù)。要求用 最 少 的 費 用 讓pebble 數(shù)目變?yōu)?03183History兩個人分別寫了 n1 和n2 章歷史書，但其中有一些 即相同歷史 的發(fā)生時間不一致）。扔掉盡量少的章使得余下的部分不3. Polish Olympiad in Informatics XIIXIII簡介：不用多說，這兩年的題目難度較以前又有提高。POI XIII 2005-20061-1 KRAThe Disks有一個各高度半徑不同的空心 Tube，依次扔一些實心圓盤，求每個圓盤在何處

28、停止。1-2 OKRPeriod of Words給一個串，求它的所有前綴的最長重復(fù)子串長度之和1-3 PROProfessor Szu給有，可能有重邊和自環(huán)。其中一個點是主樓，其他點是別墅。選一個別墅使得它到主樓的不同道路個數(shù)盡量多。一個點可以經(jīng)過多次（包括主樓）。如果有多解輸出全部。如果解超過 36500 則認為是無窮大。1-4 TETTetris 3D模擬一些長方體的下落，計算最后的高度。雖然是很經(jīng)典的數(shù)據(jù)結(jié)構(gòu)題。但如果相關(guān)知識不扎實也是做不出來的1-5 ZABFrogs在田里放一些嚇唬青蛙的 scarefrog，給青蛙計算一條從 A 到 B 的路徑，使得離最近的scarefrog 盡量

29、遠。2-1 LISThe postman給有 ，求一條從 1開始到 1 結(jié)束的回路，包含一些給定的連續(xù)頂點序列，或報告不存在。2-2 MAGWarehouse網(wǎng)格上有 n 個 shop， 每個 shop 需要經(jīng)過 ti 次 。 尋 找 一 個warehouse 使得總路程盡量小。只能沿著網(wǎng)格走。2-3 METSubway給一棵樹，用 L 條無。3184I cant read it!把每個單詞的各個字母倒過來公共點的路徑覆蓋盡量多的結(jié)點。2-4 NAJThe invasion在 n 個頂點中選出三個組成三角形，使得三角形內(nèi)的 factory 權(quán)和盡量大。每個 factory 的 可負。2-5 O

30、RKPloughing給一個 n*m 網(wǎng)格，每個格子有個非負整數(shù)。每次切下一個寬度為1 的 slice，里面的數(shù)之和不得超過 k。每次切完后剩下的部分仍應(yīng)是個矩形。要求切成盡量少的 slice。2-6 SZKSchools給出 n 個 1n 之間的整數(shù)，把它變成 1n 的排列。每個新數(shù) mi 必須在區(qū)間ai bi內(nèi)， 改變費用為ki|mi-mi|， 其中 mi 為第 i 個數(shù)原來的值。3-1 ESTAesthetic Text把 n 個單詞分成若干行，每行的各個單詞由一個空格隔開，要求相鄰兩行長度差的絕對值之和 sum|Li-Li+1| 盡量小。其中 Li 為第 i 行的長度（即所有單詞長度和

31、加上單詞的個數(shù)減 1）3-2 KRYCrystals給 出 n 和m1,m2,mn，求方程a1 xor a2 xor xor an=0 的 解 ， 要 求0=ai=n-10)。POI XII 2004-20051-1Bankomat (ban)給出某client 輸入的 n 個場景，統(tǒng)計它的有多少種可能1-2Points (pun)給兩個點集是否相似1-3Toy cars (sam)一個孩子要依次玩一些玩具。每次玩時需要把玩具放在地上，地上放不下時就必須把一些玩具放回到架子上。讓從架子上拿玩具的次數(shù)盡量小。1-4Piggy banks (ska)有兩種方式可以拿到罐里的東西：用鑰匙開、 打碎。

32、每個罐都有一把鑰匙，并且放在某個罐里。打碎盡量少的罐使得所有其他罐都可以用鑰匙打開。1-5Knights (sko)給 knight 的 n(=3)種移動方式，保證能移動到的格子不共線。把它化簡成兩個移動方式， 使得能到達的格子集合不變。2-1A journey to Mars (lot)給出圓周上 n 個點的位置和油量從每個點出走（可以從兩個方向中選擇一個） 是否可以回到起點（假設(shè)油箱無限大）。2-2Bank notes (ban1)給一些面值的相應(yīng)的數(shù)量，找一個付 x 錢的方法。2-3FibonacciSums (sum)給兩個數(shù)的 Fibonacci 進制表示，求它們的和。2-4Temp

33、late (sza)找一個盡量短的字符串作為 pattern，把墻涂成一個指定的圖案。每次涂的時候必須把整個 pattern 涂上去， 不能只涂一部分。若同一個地方，每次涂的字母應(yīng)相同后綴數(shù)組+線段樹思路：枚舉K，將所有的后綴（滿足它們和的 LCP 大于等于 K） 到線段 ，統(tǒng)計他們間隔的最大值，如果該值小于等于 K，那么說明 K 為一個可行解?？倳r間復(fù)雜度 O(NLogN)用 CENA 測試時，最慢的一個點要 3.59sec，不知道POI 時限是多少后來用了 KMP 擴展算法代替了 SA，速度顯著提高， 1.5sec 左右就過了2-5Dicing (kos)給出 n 場比賽，設(shè)計它們的結(jié)果使

34、得你獲勝場數(shù)不比其他人少。滿足此條件下要求你獲勝的場數(shù)盡量少。二分+網(wǎng)絡(luò)流網(wǎng)絡(luò)流用最簡單的 BFS，只要開始的時候加個貪心就可以了，和 NOI 那題一樣3-1Hollows (dzi)兩棵參天大樹上各有一些洞，你的任務(wù)是給n 只鳥安排一些洞居住。要求相互熟悉的鳥在不同的樹上住，且所在 的連線不交叉（可以有公共點）。鳥住得盡量低。求方案總數(shù)。該題沒什么技術(shù)含量，關(guān)鍵是要把問題想清楚， 想完整。容易遺漏的地方： 星形圖形兩個度為一的點相連連通塊之間的全排列度為 0 的點可能出現(xiàn)在任何地方3-2Double-row (dwu)給兩排數(shù)，每次可以交換相同列的兩個數(shù)。要求用最少的交換次數(shù)使得每排的各個數(shù)

35、都不相同。保證有解。3-3Two parties (dwa)把 n 個人分到兩個party，使得“有偶數(shù)個朋友與 分到同XOR 方程組一個 party”的人數(shù)盡量多.其中一個party 沒有人。每個人不是 的朋友。朋友關(guān)系是對稱的。3-4SpecialForces Manoeuvres (akc)平面上依次放置 n 個圓，求最小的 i 使得前i 個圓沒有公共點。3-5Dextrogyrate camel (pra)平面上有 n 個點，初始時在點 1，面朝點 2。每次只能右轉(zhuǎn)（0 到180 度），線路不能交叉，最后回到點 1。要求 盡量多的其他點。由于走過的點有極角序，所以可以 DP。最樸素的

36、DP 是 N3 的，但是遞推的時候，可以確定中間的點，然后對可能的兩邊的點進行排序，然后利用 單調(diào)性使得原先比較兩邊的點從 O（N2）降到 O（N）。最后，總時間復(fù)雜度為 O（N2LOGN）3-6The Bus (aut)一個網(wǎng)格，從左下角(0,0) 走 到 右 上 角(m,n)，每次只能往上或者往右走一格。有 k 個交叉點上有正整數(shù)， 要求經(jīng)過的數(shù)之和盡量大。 1=m,n=109, 1=k=105。3-7Mirror trap (lus)給一個 圍成的trap， 求有多少個格點，使得從中心往它射出激光后，激光將走盡量遠的距離后返回中心（用 Manhattan 距離衡量）。4. El Judg

37、e說明：雖然 IOI2004但重點是后面的紅色和集訓(xùn)隊討論過前面的題目，這里還是留出位置，以便大家補充。題目（都給出了題目大意）。題目描述有很多語法錯誤，大家忍耐一下惟一的一道俄文題目下面翻譯出了題目大意。數(shù)學(xué)題和的同學(xué)可以試試。題比較多，對這方面感000Sumoftwo integers001Max of Integers002Set intersection003Contest Table004Athletes005Random descending a tree006Three Squares007Space Zoo008Brackets009Fibonacci numbers010Ne

38、wYearcongratulations011Brackets II012Correct dictionary013Boxes014War-cry015One rectangle016Two ractangles017Arithmetica v1.3018Whatisthe number?019Bridges020Island of straight roads021Fraction022Regular Expression I023Way among sticks024Arithmetica 1.0025The optimal path026Operations027Odd number02

39、8Circle Game029Stormina Rectangle030Disclosingof parentheses031Minimalsumof distances032Star War (episode V)033Triangles034Rain給地面的描述，下一場雨后求積水深度。035Camelot036Two cubes037um profit038Roots of polynom039CalculatingXOR via AND040Murder of Mister C041RubiksCube 2x2x2求解魔方042LCS problem043Intervals044Fram

40、e paving045Picture segments046Best clustering047Self-describing sequence048Chess end-game國際象棋中+后對黑單王，要求不。讓黑王堅持盡量長的時間。049Minimizing number of steps050Tworegular expressions051Strange Tower052Permutation complexity053Love cycle054Mine Field從 A 到 B，路上離最近的地雷盡量遠。055Trip abroad056Best segmentation057Hacke

41、rs attack058Alise and Balisio猜數(shù) 。假設(shè) Alise 要用 1, 2, , N 各 ni 次，寫程序讓猜測的總次數(shù)盡量少。每次程序重啟（無記憶的）059CD060Defragmentation061Reconstructing permutation062Regular Expression II063Casket給一個棋盤做盡量少的修改使它對稱。064Max product065Queue for tickets066Counting figures067Good permutations0682x1-paving069Graph coloring070Squa

42、rerootof permutation071Cables072Chess cube073Enclosingpoint with polygon給 n 個點和點 P，選一些點組成多 ，使得P 在它的內(nèi)部。多各 不能超過 K，要求多 周長盡量小。074Spheres intersectionn 個球是否有公共點075Rootofthe equation解方程=A。076Bracketstructure correction077Queens078Next word079FenceNEERC 1998 那題080Japanese Crossword給 01 矩陣各行各列的連續(xù) 1 的長度，求解的總

43、數(shù)。081Swimming pool在矩形中放置一個盡量大圓。有一些圓形障礙點。082Clusterizationof binary words把 01 串分成若干組， 使得每組的任意兩個串的 hamming distance 不超過 D。只需找較優(yōu)解。083SAT-2如題。084Farthest points085Triangle Approximation給 平 面 上 三 個 點ABC，找一個等邊三角形 ABC ，使得maxAA,BB,CC 盡量小。086Anti-factorial087Tautology088p-adic numbers把有理數(shù) a/b 寫成p-adic number

44、 的形式。0898-puzzle090Graph Planarity無 是否為可平 面 圖 V3000, E1000009115-puzzle用不超過 1000 步解決15 數(shù)碼問題。092Stations093What is the number (Part II)?094PS-scheme095Directed PS-graphs一個有 是否為 PS-graph. 即可以從一條邊經(jīng)過若干次double 和 split 操作得到。096Undirected PS-graphs類似上題，但是無向圖。097Cut Rectangle把 n=20 個矩形拼成一個大矩形，要求用一種特殊的方式輸出。0

45、98Upgradingto strongly connected在有填加盡量少的邊，使它強連通099PS-scheme II用一些 R=1 的電阻組成 R=M/N 的電阻，可以串聯(lián)和并聯(lián)。(這是094 的逆問題)100Nim Game - who is the winner?101Stone Game - who is the winner?102Stone Game II - who is the winner?103Nim Game - Give Away!104CamoGame - who is the winner?105MRQ problem106k-harmonious group

46、107Infix to Posfix form給中綴表，轉(zhuǎn)換成后綴形式。108Grammarofa great game給出 8 種產(chǎn)生規(guī)則(S 0|1S|2SS|3SSS)，給出串 s，求以它為子序列的最小串，使得它可以由該文法產(chǎn)生。109Half Planes I給一些半平面（包含分界線），從中選盡量少的半平面覆蓋整個平面。n=100110Graph Existance給無 任兩點的最短距離 它是否可能是一棵樹或森林（邊長為非負整數(shù)）111Reductionto common denominator化簡有理式之和，寫成p(x)/q(x)或p(x)或 0 的形式。112 (Maze)一個 n

47、*m 迷宮有 K 個出口，有些格子不能經(jīng)過?？梢酝膫€方向移動。還有一些瞬間轉(zhuǎn)移裝置。求從初始位置到任意出口的最短路。俄語題目描述翻譯過來以后讓我很失望，不做也罷， 沒啥意思113Plane Partition給 n 條線段，它們把平面分成了多少部分？114Unique Radix給一些 X*Y=Z 或X+Y=Z 的等式，找一個進位制使得它們同時為真。115The Landing給一個由 dot, hyphen 和 0 組成的表 ，其中 0 表示未知（可能是dot 也 可 能 是hyphen）?；謴?fù)盡量多的 0 使得所有連續(xù)hyphen 的長度為給定值。比如“.-0.-”，連續(xù)-的長度為 2 1，則那個 0 一定是-，“000”連續(xù)的“-”長度為 2， 則只