國家集訓(xùn)隊(duì)作業(yè)cdq

1、IOI2008 年中國集訓(xùn)隊(duì)第二輪作業(yè)雅禮中學(xué) 陳丹琦IOI2008 中國集訓(xùn)隊(duì)第二輪作業(yè)(截止時間：2008 年 5 月 3 日)：劉汝佳作業(yè)提交：rujia.liuOverview1. ACM ICPC 歐洲賽區(qū)Neerc07, Nwerc05, Nwerc06, Nwerc07, Seerc06, Seerc05 共 6 套完整比賽, 提交 Accepted 代碼 57 個2. ACM ICPC 亞洲賽區(qū)共Taipei2007, Taejon 2002, Dhaka2007, Danang2007,2007, Japan 2005,Japan 2006, Japan 2007 共 8 套

2、完整比賽以及若干單題, 填寫了部分沒有數(shù)據(jù)的題目共提交 Accepted 代碼 76 個3. SPOJ 提交 Accepted 代碼 5 個(紅題)4. Ural Championship 2008(填表格), 提交 Accepted 代碼 10 個5. Uva Sultans Contest(填表格), 提交 Accepted 代碼 10 個6. World Final 2008 Report, CERC 2004 Report, 共提交Accepted 代碼 19 個7. WinterCamp Trip 和 Password 解題報(bào)告8. 專題研究：Dancing Links9. 附 Wo

3、rld Finals 2004, Swerc2007 code雅禮中學(xué)陳丹琦2008 年, 5 月IOI2008 年中國集訓(xùn)隊(duì)第二輪作業(yè)雅禮中學(xué) 陳丹琦1. ACM/ICPC部分題目提交：(歐洲賽區(qū))提示：由于上次已經(jīng)討論過 CERC20042006，這次沒有寫在里面。如果準(zhǔn)備填寫，請自行把去年的表格粘貼過來。NEERC 2007歷屆 NEERC 題目和測試數(shù)據(jù)、參考程序：4043Ants給 n 個白點(diǎn)和 n 個黑點(diǎn)的坐標(biāo), 要求用線段把他們連接起來, 要求每個白點(diǎn)恰好連接一個黑點(diǎn),且每個黑點(diǎn)恰好連接一個白點(diǎn).n<=100【Accepted】如果兩條線段 a1 - b1 與 a2 - b

4、2 相交, 那么 dist(a1, b1)+dist(a2, b2)一定大于 dist(a1, b2) + dist(a2, b1). 因此以黑點(diǎn)和白點(diǎn)之間的距離為權(quán)值, 求二分圖的最小權(quán)匹配后得到的方案, 所有的線段一定是不相交的, KM 算法的時間復(fù)雜度為 O(n3).POI 以前有過一道一模一樣的題目Rockets, 不過數(shù)據(jù)范圍大了很多, 利用分治思想可以做到平均 O(nlog2n)4044Building for UN有 N 個 ,設(shè)計(jì)一幢 H 層樓, 每樓是 W*L 網(wǎng)格的 ,每格恰好屬于一個 .要求任意兩個不同 都有一對相鄰的格子（要么是同層中有公共邊的格子,要么是相鄰層的同一個

5、格子）.你設(shè)計(jì)的 最多不能超過 1,000,000 個格子【Accepted】構(gòu)建 2 * N * (N 1)的：共 N 層, 每層為一個 2 * (N - 1)的矩形, 第一排全部為 i(1 <= i <= N), 第二排為 N-1 個不同的數(shù)即所有的 j(j <> i), 正確性顯然, 時間復(fù)雜度為 O(N2).4045Cactus Reloaded給一個 n 個點(diǎn)的cactus,求它的直徑 , 即 兩 點(diǎn) 距 離 的 最 大值.n<=50000【Accepted】參考了周冬同學(xué)的Cactus 問題的總結(jié)J.無向Cactus 即 通的無向圖, 且每條邊最多屬于

6、一個環(huán). 算法大致是在Cactus 的DFS 樹上作動態(tài), 我們規(guī)定 Cactus 中,一個環(huán)的起始點(diǎn)就是這個環(huán)中 dfn 值最小的那個點(diǎn), 而一條橋的起始點(diǎn)就是這條橋連接的兩個點(diǎn)中 dfn 值較小的那個點(diǎn), 規(guī)定以 i 為根的子圖為包括i 本身和以i 通過以它為起始點(diǎn)的環(huán)和橋能夠走到的所有的點(diǎn)為根的子圖.設(shè) fi表示 i 的子圖中到達(dá)點(diǎn) i 的最短距離的最大值.然后分為橋和環(huán)IOI2008 年中國集訓(xùn)隊(duì)第二輪作業(yè)雅禮中學(xué) 陳丹琦分別處理：1) 橋<i, j>, 可以用 fi + fj + 1 來更新 , 并用fj + 1 來更新 fi.2) 一個環(huán)<c1, c2, , ck

7、>, 那么用 fci + fcj + min|i-j|, k-|i-j|,來更新 把環(huán)的序列擴(kuò)大到 2k, ck+i=ci, 這樣問題轉(zhuǎn)化為 fci + fcj + j i, j i <= k/2, 這個就可以用隊(duì)列來進(jìn)行維護(hù), 在枚舉 i 的過程中得到最優(yōu)的 j.如果 c1 = i, 那么用 fci + min|i-1|, k - |i-1|來更新 fi值.整個算法的時間復(fù)雜度為 O(m) = O(n).4046Diver潛水員需要從深度為 d 的水里順著繩子往上爬.有一些鯊魚, 在 di 的深度,以 vs 的速度作從繩子開始,最大距離為 w 的往復(fù)運(yùn)動.在任何時刻,潛水員與 任

8、何一條鯊魚的距離不得小于r. 潛水員可以以不超過 vd 的速度沿著繩子上移或下移,但不能移到初始位置以下.求到達(dá)睡眠的最短時間.【無代碼】構(gòu)建新的直角坐標(biāo)系：以時間為 x 軸, 當(dāng)前的深度為 y 軸(最頂部為 d)問題等價于坐標(biāo)系中有很多個圓為限制的不可通過的區(qū)域, 你現(xiàn)在從(0, 0)出發(fā), 目標(biāo)到達(dá)(x, d), 要求 x 盡可能地小, 不能穿過任何一個圓的限制區(qū)域且任何時候斜率不能超過 vd而路線一定是由若干條線段+圓上的若干段弧組成由于圓的區(qū) 域是周期性出現(xiàn)的, 可以對任何兩個圓求切線, 計(jì)算切點(diǎn)位于每個圓的哪個角度, 而每次相當(dāng)于從一個圓的某個角度到達(dá)另一個圓的某個角度, 而不需要當(dāng)

9、前位于第幾周期的圓上這樣求起點(diǎn)到目標(biāo)點(diǎn)的最 短路即可,我沒有程序?qū)崿F(xiàn), 應(yīng)該大概思路就這樣吧4047Equation解方程 f(x)=0,其中 f(x)用后綴表達(dá)式表示,包含四則運(yùn)算符.x 最多出現(xiàn)一次.保證 出現(xiàn)除以常數(shù)0 的情況,即至少存在一個 x,使得 f(x) 除 0.【Accepted】對輸入的后綴表達(dá)式建立后綴表達(dá)式樹, 有些節(jié)點(diǎn)的值已經(jīng)確定(比如根節(jié)點(diǎn)為 0 及所有的常數(shù)節(jié)點(diǎn)). 正向DFS 一遍然后反向 DFS 一遍, 如果 節(jié)點(diǎn)的值已知能夠計(jì)算出父親節(jié)點(diǎn)的值, 如果父親節(jié)點(diǎn)和父親的另一個孩子的值已知, 可以計(jì)算當(dāng)前節(jié)點(diǎn)的值. 這樣就可以把整棵樹每個節(jié)點(diǎn)的值計(jì)算出來, * 0,

10、 / 0 這些特殊情況要尤其注意, 因此需要考慮的細(xì)節(jié)還是很多的.4048Fund Manageme你有 c,但沒有股票.給你m 天時間和n 支股票供你.【Accepted】這個題 n 和 k 都非常小, 當(dāng) n = 8, k = 8 的時候狀I(lǐng)OI2008 年中國集訓(xùn)隊(duì)第二輪作業(yè)雅禮中學(xué) 陳丹琦nt每天持有的總 lot 數(shù)都不能超過 k,且最后一天結(jié)束時不能持有任何股票.第 i 只股票的一個lot 是 si 股,且每天持有的lot 數(shù)不能超過 ki.已知每個股票每天的價格,每天只能買一只股票或賣一只股票的一 lot,最后最多能剩 ？ c<=108, m<=100, n<=8

11、, k<=8, Si<=106,ki<=k, 0<pi,j<=1000態(tài)總數(shù)不超過 15000 個, 通過一遍搜索將所有可行的狀態(tài)用一個 9 進(jìn)制數(shù)在 Hash 表中存下來動態(tài)： 設(shè) fij表示前 i 天, 當(dāng)前股票的持有情況為 j 這個狀態(tài)下最多能剩轉(zhuǎn)移的時候根據(jù)買一lot 的股票, 賣一lot 的股票, 不操作三種情況, 枚舉n 計(jì)算新的狀態(tài)值在Hash 表中進(jìn)行查找進(jìn)行轉(zhuǎn)移即可時間復(fù)雜度為 O(n2 * tot)4049Gamen 個人圍成一圈,一開始第 k 個人手上有一個球.然后每個人隨機(jī)往左或往右傳球（往右傳的概率為 pi,往左為 1-pi）.所有人至少

12、拿過一次球時 結(jié)束,最后一個拿到球的人獲勝. 求第 n 個人的獲勝概率.n<=50【Accepted】當(dāng) n <= 3 的時候, 特殊處理, 比較簡單對于相鄰的三個人 a, b, c, 假設(shè)球在 a, 在球傳到 a 的左邊之前 a 通過 b 把球傳給 c 的概率為 pa * pb / (1 + pa * pb - pa)：設(shè)這個概率為 x, 假設(shè)球在 b, 球傳到 a 的左邊之前傳給 c 的概率為 y, 那么 x = pa * y, y = pb + (1 pb) * x, 解 x 即可同理可以計(jì)算出球在 c, 在球傳到 c 的右邊之前 c 通過 b 把球傳給 a 的概率可以用這兩

13、個概率來替換 pa和 1 pc, 這樣問題是等價的, 相當(dāng)于把 b 從圈中給刪除, 數(shù)據(jù)規(guī)模減少 1這樣就可以不斷地通過替換和刪除的操作, 將圈中的點(diǎn)一個一個刪除, 直到最后剩下 1, n, n-1, k若 k 先往右傳給 1, 將 k 從圈中刪除后, 等于 1 往左傳的概率; 若 k 往左傳給 n-1, 將 k 從圈中刪除后,等于 n-1 往右傳的概率考慮兩種特殊情況, k = 1 或 n 1若 k = 1, 則將2 . n 2 依次刪除后 為 1 往右傳的概率, k = n 1 同理算法的時間復(fù)雜度為 O(n)這個題精度要求非常高, 要特別注意4050Hanoi TowersHanoi 塔

14、問題的構(gòu)造解法：把六種移動（AB,AC,BA,BC,CA,CB ）排序后選擇第一個能用的操作.【Accepted】這個題其實(shí)挺有意思的設(shè) fij表示當(dāng)前有 i 個盤子, 在柱子 j 上, 將它們?nèi)恳苿拥搅硪桓由系牟綌?shù), 以及移動到哪根柱子IOI2008 年中國集訓(xùn)隊(duì)第二輪作業(yè)雅禮中學(xué) 陳丹琦另外不能連續(xù)移動同一個盤子.給出 n 和六種移動的順序, 求解Hanoi 問題的步數(shù).最終所有盤子可以都在B 也可以都在C. n<=30上為 gijfij由 fi-1k轉(zhuǎn)移而來, 相當(dāng)于將 i-1 個盤子移動到 p = gi-1j之后, 將第 i 個盤子移動到 3 j p 后, 再將前 i-1

15、個盤子移動到 gi-1p上如果 3 j p 不等于 gi-1p, 那么將 i-1 個盤子繼續(xù)移動 . 直到 i 個盤子全部在一個柱子上了時間復(fù)雜度為 O(n)4051I18nInternationalization 可以簡寫為I18n,表示I 和n 中間有 18 個字符.給一篇壓縮后的文章,進(jìn)行展開.注意展開后的單詞必須是以前出現(xiàn)過的,且恰好只有一個展開的可能性.大小寫不敏感.【Accepted】簡單題, 模擬即可用數(shù)組 fLRlen存取第一個字母為 L, 最后一個字母為 R, 字符串的長度為 len 的字符串4052Japanese Writing給一個字的正確寫法（筆劃集合）,某個寫法是否

16、正確. 要求各筆劃（八個方向的直線段）端點(diǎn)可以做一一,使得后所有筆劃（包括方向）相同,且任何兩個端點(diǎn)的相對位置（八個方向）不變.【Accepted】將每個圖中的所有線段排序(按 x0, y0, x1, y1 的優(yōu)先順序), 那么如果兩個筆畫可以, 那么排序后的線段端點(diǎn)一定可以一一對應(yīng)點(diǎn)對應(yīng)好了之后, 只需要點(diǎn)兩兩之間的相對關(guān)系即可知道是否可以一一映射了4053Kingdom Partitionin g有 n 個人,每個人期望得到 mi 個不相交（但可以接觸）的圓型土地.給每個人一塊不相交的凸多邊形土地,使得每個人都至少得到了它期望得到的1/n 面積.n<=30, mi<=30【Ac

17、cepted】由 于 所 有 的 圓 的 覆 蓋 區(qū) 域 在 -2000 . 2000-2000 . 2000之間, 考慮來切割這個矩形, 每個人得到的區(qū)域?yàn)長 . R-2000 . 2000的形式考慮如何分割可以滿足題目要求：設(shè)左界為 L(初始 L = -2000), 每次二分一個右界R, 滿足至少有一個未分配的人得到了 1/n 的面積, 這個可以在 O(nlog2R)的時間內(nèi)得到, 將這個人分配L . R-2000 . 2000的一段矩形首先這個人得到的解一定合法, 剩下的 n-1 個人至少還有(n-1)/n 的面積沒有被覆蓋將 L 設(shè)置為 R, 對剩余的 n-1 個人遞歸求解, 這樣做相

18、當(dāng)于 n 個人的時候每個人至少可以得到 1/n,n-1 個人的時候每個人至少可以得到 1/(n-1), 而每個IOI2008 年中國集訓(xùn)隊(duì)第二輪作業(yè)雅禮中學(xué) 陳丹琦NWERC 2007測試數(shù)據(jù)、參考程序：3971Assemble有 b 塊錢, 要組裝一臺電腦.分別給出 n 個配件的種類、質(zhì)量和價格,要求每種類型的配件各買一個,總價格不超過 b,且質(zhì)量的最小值盡量大.【Accepted】二分p,對于每種配件,選擇質(zhì)量 p 的價格最小的一個,價格之和是否不超過 b.時間復(fù)雜度為 O(nlog2R).3972Marchof the Penguins網(wǎng)格上有 n 片荷葉, 坐標(biāo)為(xi,yi),上面有

19、 ni 只企鵝,最多能有 mi 只企鵝能從上面跳走.要求所有企鵝在同一片荷葉上集合,哪些荷葉可以成為這個匯合地點(diǎn)?一只企鵝每次最多跳D 距離.【Accepted】將每片荷葉拆成兩個點(diǎn) i, i¢ ,構(gòu)最大流的模型：1. Si, 容量為 ni; 2.ii¢ , 容量為 mi;3. i¢ ® j , Dist(i, j) D, 容量為+¥ .枚舉企鵝的匯合點(diǎn)i,以S 為源點(diǎn),i 為匯點(diǎn)求最大流是否等于企鵝的總數(shù), 求最大流使用 Dinic 能夠在非常短的時間內(nèi)通過測試數(shù)據(jù).人至少還有原面積的(n-1)/n, 所以剩余的 n-1 人每個人至少也得到了

20、(n-1)/n*1/(n-1) = 1 / n 的面積, 因此解是合法的算法的時間復(fù)雜度為 O(n2*m * log2R)4054Language Recognitio n給一個 n 個字符串組成的集合, 設(shè)計(jì)一個狀態(tài)數(shù)最少的DFA,使得它們接受該集合對應(yīng)的語言 , 例如 fix, foo, ox.n<=5000, 串長均不超過30.【Accepted】首先將 n 個串的 DFA 構(gòu)建出來, 問題相當(dāng)于要求這棵樹中哪些點(diǎn)是同構(gòu)的如果兩個點(diǎn)同構(gòu), 那么可以將它們合并起來, 數(shù)據(jù)規(guī)模減少 1我使用Hash 函數(shù)來判重：25Hashi = å (HashC(i, k )* pk )

21、mod MODk =0C(i, k)表示i 的第k 個孩子, 如果C(i, k)不存在, 這一項(xiàng)記為 0如果 i 是一個單詞的結(jié)束結(jié)點(diǎn), 那么Hashi xor a 否則 Hashi xor b利用這個 Hash 函數(shù)判重就可以通過全部的測試數(shù)據(jù)了時間復(fù)雜度為O(n * L)IOI2008 年中國集訓(xùn)隊(duì)第二輪作業(yè)雅禮中學(xué) 陳丹琦3973Containers有 n 個 containers, 每一個長40, 寬 8(圖中的灰色部分).現(xiàn)在要找一個容器把它們裝下, 兩行之間間隔為 2, 兩列之間間隔為 4,使得容器的面積盡量小,如果有多個面積最小,要求寬度盡量小.【Accepted】設(shè)堆積了 a

22、* b 個 containers,那么a *b ³ é n ù ,且(10a + 2) * (44b+ 4)要求最小.如果不考ê 5 ú慮 a, b 是整數(shù)的條件,利用bax +³ 2 ab 均 值 不 等 式 可 以 求 出 函 數(shù)x44nf (x) = (10x + 2) *(+ 4) 的最小值.要求 a, b 是整數(shù),x那么在取得 f (x)最優(yōu)的 x 上下范圍內(nèi)進(jìn)行枚舉即可.3974Youth Hostel Dorm一個 m * n 的地圖,要求給每個格子選擇空地. , 床B 和 E 中的一個,滿足以下條件：1) E 有且僅有

23、一個,且必須在地圖的邊界上2) 對于每個B, 一定存在至少一條不經(jīng)過其它 B 的 E 到 B 它的路徑3) B 要盡可能多【Accepted】哈哈o, 基于連通性狀態(tài)壓縮的動態(tài) 問題. 通過找規(guī)律, 一定可以構(gòu)建一組最優(yōu)解滿足以下條件：1) 所有的空地和 E 為 通塊.2) 每個 B 一定至少一個 E 或空地相鄰.有了這樣的限制后, 就可以逐格遞推進(jìn)行動態(tài) , 動態(tài) 的時候把 E 默認(rèn)為一個空格, 設(shè)狀態(tài)為 f(i, j, S, P)表示當(dāng)前轉(zhuǎn)移完(i, j)這個格子后輪廓線上方的 n 個格子的連通狀態(tài)為 S(S 使用最小表示法, 如果是 B 標(biāo)記為 0), 輪廓線上所有的 B 是否已經(jīng)至少和

24、一個空地相鄰的二進(jìn)制狀態(tài)為 P.m, n 的規(guī)模最大為 8, 擴(kuò)展的狀態(tài)總數(shù)比較少, 程序效率是很高的.注意最后任意選擇一個位于邊界上的空地作為 E 即可(邊界上至少會有一個空地, 否則角落里的 B 不能滿足至少和一個空地相鄰).3975Escape from Enemy Territory一個 m * n 的地圖,有一些格子為敵人的領(lǐng)域, 兩個格子(x0, y0), (x1, y1)的距離為它們的曼哈頓距離| x0 - x1| + | x1 y1|.現(xiàn)在給一個起點(diǎn)(sx, sy)和一個終點(diǎn)(tx, ty),要求你找一條起點(diǎn)到終點(diǎn)的路徑,使得任何時候與【Accepted】先 BFS 一遍計(jì)算出

25、 Distij表示格子(i,j)距離敵子的最小距離.從大到小枚舉 Dist 值,如果兩個格子能夠通過一些 Dist 值 當(dāng)前枚舉的 K 的點(diǎn)互相到達(dá),那么 所有這樣的格子進(jìn)行合并.初始的時候每個格子屬于一個集合,在枚舉 K 的過程中, 將所有Dist 值 = K 的格子與其相鄰的格子 Dist 值K 的格子所在的集合合并.如果枚舉到 K 的時候,(sx, sy), (tx, ty)IOI2008 年中國集訓(xùn)隊(duì)第二輪作業(yè)雅禮中學(xué) 陳丹琦任何一個敵子的最小距離最大,在這個前提下要求路徑盡可能地短.合并到了一個集合中,那么即為 K.最后 BFS 一遍求出在 K 的前提下的最短路徑.集合合并使用并查集

26、來實(shí)現(xiàn),時間復(fù)雜度為 O(mn).3976Flight Safety有 C 塊互不相交、由簡單多邊形 的大陸,邊數(shù)為 M,航線是由 N 條線段 的折線段, 求航線上的點(diǎn)離大陸的最近距離的最大值.【Accepted】二分 R 后, 將所有的多邊形進(jìn)行擴(kuò)充：即對每條邊擴(kuò)充成一個寬度為 R 的長方形, 原多邊形保留以及每個點(diǎn)擴(kuò)充成一個半徑為 R 的圓.計(jì)算每條線段 L 是否完全被這些圖形所包含：1) 計(jì)算線段與每個多邊形的交, 計(jì)算它與多邊形每條邊的交點(diǎn), 排序后相鄰的一段要 全在多邊形內(nèi)部, 要 全在其外部, 取這一段的中點(diǎn)判斷在多邊形內(nèi)部還是外部, 如果在內(nèi)部, 將這一段加入到集合 S 中.2)

27、 計(jì)算線段與圓的交, 如果與圓的交點(diǎn)加上線段的兩端排序后,相鄰的一段是否在圓內(nèi)部, 如果是, 加入到集合 S 中.對于集合 S 中的所有線段,這些線段是否完全覆蓋了 L, 這個只需要利用一個排序+區(qū)間并即可. 具體還是參見集訓(xùn)隊(duì) 2008 程芃琪的吧, 這里不再贅述J.3977Summits一個 m * n 的地圖,每個格子有一個海拔高度,求 d-summit 的個數(shù).d-summit 的定義為：設(shè)這個格子海拔為 h,如果這個格子必須至少經(jīng)過一個海拔h-d 的格子才能到達(dá)一個>h 的格子,則稱它為 d-summit.【Accepted】和 E 的做法差不多,首先將所有格子按照高度從大到小

28、排序.依次枚舉每一個高度,設(shè)置一個指針 k,表示 k 是最后一個格子,k 高度>當(dāng)前枚舉高度-d.在枚舉的過程中, k 指針不斷向后移動,并且將k 與其相鄰的高度不小于它的格子所在的集合進(jìn)行合并.如果當(dāng)前枚 舉的格子所在的集合內(nèi)格子最高的海拔高度不超過它 的高度,那么當(dāng)前格子為一個 d-summit.時間復(fù)雜度為O(mn log2 (mn) .3978Obfuscation給你一本詞典,然后給你一句話,這句話本來由若干個單詞組成,每個單詞除了首字母和末字母外,中間的字母可能被打亂順序,單詞之間的空格被【Accepted】動態(tài).設(shè)fi表示字符串前i 位進(jìn)行還原的方案總數(shù)(可以只記錄 f 值

29、= 0, 1 或>1).f i = å f j* S ( j + 1, i), j < i .IOI2008 年中國集訓(xùn)隊(duì)第二輪作業(yè)雅禮中學(xué) 陳丹琦刪去.現(xiàn)在問是否可以利用詞典上的單詞來還原這句話,如果唯一解,輸出,如果無解,輸出impossible, 如果多解 , 輸出ambiguous.其中S(l, r)表示l . r 這一段有多少種解釋的方法,方法是利用四元組來唯一確定一個單詞(首尾字母 a,b, 長度 L, 以及將字符串的字母按字典序排序后得到的新串).對于讀入的所有單詞以這四個信息存入 Hash 表中, 對于每一個 l . r, 將這一個子串處理后在 Hash

30、表中進(jìn)行查找即可得到 S(l, r)值.3979Tower Parking有一個 Parking Tower,共 h 層, 每層有一個長為 l 的 conveyor belts, 塔 的 有 一 個elevator,每次 belts 通過逆時針或順時針旋轉(zhuǎn)后將某個 car 運(yùn)到 再利用 elevator 運(yùn)輸?shù)絫ower 的底部.elevator 升降一層需要 10s, belt 轉(zhuǎn)一格5s,要求模擬這個過程,問最后完成整個任務(wù)的時間.【Accepted】模擬 belt 和 elevator 運(yùn)轉(zhuǎn)的過程即可,時間復(fù)雜度為O(nl).3980Walk有很多條等高線,每個等高線對應(yīng)了一個高度和一個

31、多邊形.多邊形 自交,任意兩個多邊形也 相交.現(xiàn)在有兩個人, Alice 位于(0, 0), Bob 位于(100000, 0).如果從一個海拔高度經(jīng)過某個等高線到達(dá)另一個高度,那么可能需要上山或下山,現(xiàn)在要求找一條 Alice 到Bob 的路徑使得Climbed 海拔之和與 descended 海拔之和盡量小.【Accepted】多邊形之間只有包含和相離兩種關(guān)系, 如果兩個多邊形 A, B, A 包含 B 且不存在一個 C, A 包含 C, C 包含 B, 那么稱 A 為 B 的父親結(jié)點(diǎn).n 個多邊形之間的邊恰好 了一棵森林, 假設(shè)建立一個虛擬 0 號節(jié)點(diǎn)向所有沒有父親結(jié)點(diǎn)的點(diǎn)連邊, 森林-

32、>樹.那么 Alice 所在的最小的多邊形到Bob 所在的最小的多邊形之間的距離恰好對應(yīng)了樹中的唯一路徑.計(jì)算每個節(jié)點(diǎn)的父 親節(jié)點(diǎn), 我們只需要在這個多邊形上任意選一點(diǎn), 選擇包含它的面積最小的多邊形即為其父親節(jié)點(diǎn), 這樣把樹構(gòu)造出來的時間復(fù)雜度為 O(n * Points), Points 為總的點(diǎn)個數(shù) <= 20w, 代價太高了.而事實(shí)上我們只需要關(guān)心兩個點(diǎn) u, v 之間的路徑, 即找到 u 的所有祖先和 v 的所有祖先即可而不需要構(gòu)造出整棵樹出來.而 u 的祖先節(jié)點(diǎn)為包含點(diǎn)(0, 0)的所有多邊形按照面積從小到大排序即依次為u 的祖先節(jié)點(diǎn), v 同理.因此算法的復(fù)雜度降低為

33、 O(Points + nlog2n).IOI2008 年中國集訓(xùn)隊(duì)第二輪作業(yè)雅禮中學(xué) 陳丹琦NWERC2006測試數(shù)據(jù)、參考程序:3633Sudoku3*3 Sudoku Puzzle: 每行,每列,9 個 3*3 的子矩陣中 19 的每個數(shù)恰好出現(xiàn)一次.現(xiàn)在給一個正確的 Sudoku Puzzle 和一個 Unsolved Puzzle,問是否可以將 Unsolved Puzzle 空的格子填滿后通過給定的 5 種操作得到那個 Sudoku Puzzle.操作共有 5 種：1) 順時針或逆時針旋轉(zhuǎn).2) 交 換 任 一 個 column segment 中的任意兩列.3) 交換任意個 ro

34、w segment中的任意兩行.4) 交 換 任 意 兩 個 row segments 或 column segments.5) 19 的數(shù)字作一個置換.【Accepted】不考慮 操作, 枚舉第二個 Puzzle 做了哪些操作后 第二個Puzzle 對應(yīng)的位置的數(shù)是否可以與第一個Puzzle 一一對應(yīng).枚舉量為O(4 * 63 * 63 * 62)= O(6718464), O(81)來, 代價太高. 改變一下枚舉的順序：首先枚舉旋轉(zhuǎn)和交換 row segments 和交換column segments,枚舉量為 6 * 6 * 4, 然后依次對第二個 Puzzle 的每一個非空數(shù)字進(jìn)行枚舉

35、：枚舉它的 row 在其 row segment 中的位置以及 column 在其 column segment 中的位置, 這樣就可以確定當(dāng)前數(shù)字對應(yīng)第一個 Puzzle 的哪一個位置, 如果不對, 可以立刻舍去.相同的數(shù)字應(yīng)該放在一起進(jìn)行搜索, 因?yàn)樗鼈兊氖窍嗤? 如果有一個無法對應(yīng), 就可以立刻舍去.此外, 可以按照數(shù)字出現(xiàn)的次數(shù)從大到小來搜索每個數(shù)字, 比如第二個Puzzle 中有 6 個 9, 1 個 5, 那么優(yōu)先搜索所有的 9. 這樣算法的效率已經(jīng)非常好了J.3634The SetStack Computer模擬一個棧,初始的時候棧為空,有以下幾種操作：1) PUSH：Push

36、()2) DUP：x = Pop(), Push(x), Push(x)3) UNION：x = Pop(), y = Pop(),Push(x y)4) INTERSECT: x = Pop(), y= Pop(), Push(x y)5) ADD: 將 x 加入到 y 中得到集合 z,Push(z)每次操作后輸出當(dāng)前棧頂集合S 的|S|.【Accepted】因?yàn)椴僮骺倲?shù)最多只有 2000, 給每一個出現(xiàn)過的不同的集合標(biāo)記上不同的數(shù), 最多只有2000 個不同的集合, 每個集合又由若干個集合組成, 集合用組成它的集合的標(biāo)號來表示.PUSH, DUP：O(1)UNION, INTERSECT,

37、 ADD：O(n)計(jì)算操作后的集合,查找新的集合的標(biāo)號注意 的時候, 每一個集合的標(biāo)號組成保證嚴(yán)格遞增.如果使用 Hash 表來 每個集合的標(biāo)號, 查找新標(biāo)號的時間復(fù)雜度為 O(n), 整個算法的時間復(fù)雜度為O(n2).Code 沒有使用 Hash, 每次 查找, 雖說理論上是 O(n3), 但是實(shí)際上遠(yuǎn)遠(yuǎn)達(dá)不到, 在 CII 上測試 0.035s.IOI2008 年中國集訓(xùn)隊(duì)第二輪作業(yè)雅禮中學(xué) 陳丹琦3635Pie有 n 個圓,m+1 個人來分這些圓,每個人得到圓的面積要相同且每個人得到的“部分圓” 只能取自其中的一個圓,問每個人最多能得到多少面積的圓.【Accepted】n êp

38、 r 2 ú二分ans,åê i ú 是否大于等于m+1,時間i=1 ë ans û復(fù)雜度為 O(nlog2R).3636Ticketto Ride給一個帶權(quán)無向圖和其中的 8 個頂點(diǎn) p1,p2,p3,p8, 要求選擇權(quán)值之和最小的一些邊使得p1, p2 連通, p3, p4 連通, p5, p6 連通,p7,p8 連通.【Accepted】動態(tài), 設(shè)狀態(tài) f(i, S)表示 8 個點(diǎn)與點(diǎn) i 是否連通這個狀態(tài)下選擇邊的最小權(quán)值.轉(zhuǎn)移分兩種情況：1) f(i, S0) + f(i, S -S0) f(i, S), 其中 S0 是 S

39、 的子集.2) f(i, S) + C(i, j) f(j, S), 其中 C(i, j)表示有一條 i-j的無向邊, 權(quán)值為 C(i, j).從小到大枚舉 S, 轉(zhuǎn)移 1)直接進(jìn)行枚舉,轉(zhuǎn)移 2)對于每一個 S, 對整個圖求最短路即可.初始狀態(tài)為 f(i, 0) = 0, f (pi, i) = 0.設(shè) g(S) =minf(i, S),為將 8 個點(diǎn)劃分到 4 個集合S0, S1, S2, S3, 其中第 1, 2 點(diǎn), 第 3,4 點(diǎn), 第 5,6 點(diǎn),第 7,8點(diǎn)分別屬于同一個集合, g(S0)+g(S1)+g(S2)+g(S3)的最小值.時間復(fù)雜度為 O(n * 38 + 28 *

40、m).IOI2008 年中國集訓(xùn)隊(duì)第二輪作業(yè)雅禮中學(xué) 陳丹琦3637The Bookcase有 n 本書,每本書有一個高度Hi(150<=Hi<=300),寬度 Wi(5<=Wi<=30).現(xiàn)在要構(gòu)建一個三層的書架,你可以選擇將 n 本書放在書架的哪一層,使得滿足最小.【Accepted】動態(tài) ：將所有的書按照高度從大到小排序, 不妨設(shè)高度最大的書安排在第一層, 設(shè)狀態(tài) f ijk 表示安排完前 i 本書, 第二層的書的寬度之和為 j, 第三層的書的寬度之和為 k 這個狀態(tài)下第二層高度最大值和第三層書高度最大值之和的最小值(好拗口L).轉(zhuǎn)移有以下幾種：1) f ijk

41、f i+1jk, 安排在第一層.2) f ijk + G(j, Hi) f i+1j+Wik, 安排在第二層.3) f ijk + G(k, Hi) f i+1jk+Wi, 安排在第三層.其中a = 0, G(a, b) = b 否則為0.狀態(tài)總數(shù)為70 * 2100 * 2100, 無法承受, 必須優(yōu)化：1) 枚舉的時候只要枚舉 j + k <= Sumi的有效狀態(tài),其中 Sumi表示前 i 本書的寬度之和.2) 由于所有的轉(zhuǎn)移全部是 fijk f i+1pq, i<= p, j <= q, 因此 j, k 均從大往小枚舉, 因此 i 那一維的空間可以省去.3) 高度最大的

42、書放在了第一層,不妨設(shè)第二層的書的最大高度不小于第三層書的最大高度.如果第二層的 書的寬度之和>第一層的寬度之和+30, 那么選第二層的一本書放到第一層來, 高度最大值之和 變大, 寬度之和的最大值也 變大, 因此第二層寬度之和<=第一層寬度之和+30, 第三層寬度之和<=第二層寬度之和+30.因此 j<=(2100+30)/2 = 1065, k<=(2100+60)/3 = 720, 比(2100, 2100)減少了很多, 算法效率已經(jīng)大大提高了.3638Printer Queue隊(duì)列中有 n 個任務(wù),每個任務(wù)有一個優(yōu)先級 19,現(xiàn)在要模擬一個過程：取出隊(duì)首元

43、素 J,如果隊(duì)列中至少有一個任務(wù)比 J 的優(yōu)先級高,將 J 移動到隊(duì)列末尾,否則輸出J.問第K 個任務(wù)是【Accepted】n <= 100, 直接模擬即可, 時間復(fù)雜度為 O(n2).IOI2008 年中國集訓(xùn)隊(duì)第二輪作業(yè)雅禮中學(xué) 陳丹琦第幾個輸出的.3639Prime Path給你兩個四位的質(zhì)數(shù) A, B,問 A 最少需要通過幾步操作到達(dá) B. 操作的定義是：修改質(zhì)數(shù) X 的其中一位得到另一個質(zhì)數(shù) Y,整個過程中不 有前導(dǎo) 0.【Accepted】以每個四位質(zhì)數(shù)為圖中的點(diǎn),如果一個質(zhì)數(shù)可以通過一次操作得到另一個質(zhì)數(shù)則連一條有向邊,對這個圖 BFS 求 A 到 B 的最短路.時間復(fù)雜度

44、為 O(10000).3640Linelands Airport給你一個折線(x1, y1), (x2, y2) ., (xn, yn),xi<xi+1.要求在圖形中刪掉一些使得出現(xiàn)一個長度至少為 L 的水平線且刪除的面積盡量的少.(ps : 看題目的圖J,不好解釋清楚 )【Accepted】假設(shè)選取的水平線為x, x+L, 坐標(biāo)為 y.枚舉 i, j, x 屬于折線(xi,yi)-(xi+1,yi+1), x+L 屬于(xj,yj)-(xj+1,yj+1). 設(shè) f(x) = y0, f(x+L) = y1,H = minyi+1 . yj, 那么 y 需要滿足: y <= mi

45、n(y0, y1, H).對于一段折線(a, b)-(c, d),刪去的面積為上面為(c - a) * (abs(d - b) / 2上面三角形的面積 + (c - a) * (min(b, d) y).考慮 y = y0 或 y = y1 或 y = H 分三類情況進(jìn)行討論, 可以得到 x 的取值范圍,列出刪去的面積的式子 S(由 x)表示, 很明顯是一個關(guān)于 x 的一元二次函數(shù),求這個函數(shù)在區(qū)間L, R的最值可以 O(1)計(jì)算出來(由于函數(shù)比較麻煩, 避免分情況進(jìn)行討論,Code用了三分),時間復(fù)雜度為 O(n2log3R).3641Leonardos Notebook給一個 126 的置

46、換 B,問是否存在一個置換 A,A2=B.【Accepted】經(jīng)典問題, 是否存在一個置換 A, Al=B：將 B 寫成若干個循環(huán)的形式, 對于每一個長度 x, 設(shè)有 k 個長度為 x 的循環(huán), 那么 是否存在一個 t(即 t 個循環(huán)在置換A 中為一個循環(huán))滿足：t | k, t | l, (x, l / t) = 1.而對于本題來說, l = 2, 那么對于每一個長度 x, t = 1 或 t = 2, A 存在的充要條件是：將 B 寫成若干個循環(huán)的形式后不存在一個偶數(shù)的循環(huán)長度 x, 長度為 x 的循環(huán)的個數(shù)為奇數(shù), 時間復(fù)雜度為 O(26).IOI2008 年中國集訓(xùn)隊(duì)第二輪作業(yè)雅禮中學(xué)

47、 陳丹琦NWERC 2005測試數(shù)據(jù)、參考程序：3408Unequalle d Consumpti on有 n 種糖果,每種糖果有無限多個,第 i 種糖果重量為 Ai,設(shè) f (x)表示用這n 種糖果稱出重量 x 的方案總數(shù).然后有 m 個詢問,每次詢問一個 P,要求輸出一個最小的 x 滿足f (x) P. 數(shù)據(jù)規(guī)模：n5, Ai10, m10, 1P1015.【Accepted】本題參考了參考程序的解答. 如果 P 沒有那么大的話,可以用背包動態(tài) 來解決：設(shè) Optij表示前 i 種糖果,稱出重量 j 的方案總數(shù),Optij = Opti-1j + Optij-Ai,fj = OptNj.P

48、 很大,無法直接計(jì)算,而 f 滿足一個性質(zhì)：設(shè) L=lcm(A1, ., An), 那么對于每一個r(0 r<L), f x * L + r是一個關(guān)于 x 的 n-1 次的多項(xiàng)式 (這個結(jié)論我不知道怎么得來的K).這樣只需要動態(tài)規(guī) 劃計(jì)算出 x = 0 . n 1 這 n 個數(shù)的 fx *L + r后利用Lagrange Interpolation 即可在 n2 的時間復(fù)雜度內(nèi)計(jì)算出任何一個 fx *L + r的值.拉格朗日多項(xiàng)式的定義如下：Given a set of k + 1 data points(x0 , y0 ), (x1, y1 ),., (xk , yk )where n

49、o two xj are the same, the interpolation polynomial in the Lagrange form is a linear combination：kL(x) = å y jl j (x)j =0of Lagrange basis polynomialskl ji將xj, yj=j, fj * L + r和x 代入即可計(jì)算出L(x).對于每一個詢問 P,設(shè) v = minA1, ., An,很明顯 fk fk + v,即 fk * v+ r(0r<v)是非遞減的.那么枚舉 r,對 k 二分,利用拉格朗日多項(xiàng)式即可解決本題,時間復(fù)雜度

50、為 O(L *n2 + m * v * log2P * n2).3409Declaratio nofContent有 n 個 ,m 種材料.告訴你每種 按照含有比率從大到小的材料組成,有的材料在這個 中的具體的比率已知, 注意所有的比率一定是【Accepted】對于每個 ,計(jì)算出每種材料比率的上界和下界值：它要大于等于比它比率小的材料中確定比率的最 大值,小于等于比它比率大的材料中確定比率的最小值.估算最大值：比如 10 種材料,IOI2008 年中國集訓(xùn)隊(duì)第二輪作業(yè)雅禮中學(xué) 陳丹琦一個整數(shù).有 q 個詢問,每個詢問是 most S 或 least S 表示詢問可能含有材料 S 的比率最大或最

51、小的 有哪些.1 ? ? 10 ? ? ? ? 30 ? 估算第6 種材料的最大值即1 + 1 +1 + 10 + 10 + x + x + x + 30 + 30 = 100,同理估算最小值即可.注意題目說每個不確定比率的材料至少比率為 1,但是確定比率的可能為 0%,我因?yàn)檫@個 wa 了好久 .3410Laserbox有一個 n * n 的棋盤,現(xiàn)在有一些格子里裝了 right-turner.現(xiàn)在有一個激光從棋盤的上方, 下方,左方或右方射入,如果激光遇到了一個 right-turner 那么方向順時針轉(zhuǎn) 90 度,問最后激光從哪個地方射出棋盤或者激光一直會在棋盤內(nèi).【Accepted】模

52、擬激光的傳遞過程即可,時間復(fù)雜度為 O(n2).3411Bowlstack有 n 個碗,每個碗的平面圖為一個等腰梯形,告訴你每個梯形的上底,下底和高,要求你給n 個碗安排一個疊放順序使得疊放后總高度最小.【Accepted】由于 n9, 只需要搜索碗的疊放順序然后計(jì)算疊放高度取最小值即可, 計(jì)算疊放高度要根據(jù)兩個梯形上底,下底之間的大小關(guān)系分情況進(jìn)行討論,細(xì)心一點(diǎn)就好了.時間復(fù)雜度為 O(n2*n!).3412Pesky Heroes一棵n 個節(jié)點(diǎn)的樹,1 為根,且1 只有 1 個兒子,其他節(jié)點(diǎn)最多有 2 個兒子.其中有 m 個節(jié)點(diǎn)被設(shè)置成 trap,如果一個葉子節(jié)點(diǎn), 它到根的路徑上沒有tr

53、ap,那么它叫做 dead-end.需要安排最少的人,使得所有的dead-end 都被 到,且任何一個人都不能踩到 trap.每個人每次到達(dá)一個岔路口時總是向左走,且只能夠向右走一次.【Accepted】如果一棵子樹沒有 trap, 那么一個人一直向左走, 一定可以恰好從根出發(fā), 遍歷完整棵子樹而回到根結(jié)點(diǎn).由于被標(biāo)記為 trap 的點(diǎn)不能夠被 到, 所以“向右走一次”這個操作的作用是避免這個人走入通向trap 的路徑. 可以樹形 Dp, 設(shè) fi表示 完 i 這棵子樹最少需要安排多少個人, gi表示一個人從 i 走入以 i 為根的子樹并從 i 走出, 遍歷完整棵子樹另外還需要多少個人.方程轉(zhuǎn)

54、移如下：設(shè) trapi表示以 i 為根的子樹內(nèi)是否有 trap.fi = minflc + frc, gi + 1如果 traplc and traprc, 那么一個人走入 i 這棵子樹, 至少需要向右走兩次才能避免trap, 因此這個人一定無法再回到 i, 這種情況下 gi = + inf; 否則gi = minglc + grc, glc + frc, grc + flc.時間復(fù)雜度為 O(n).3413Reduced有 n 個 ID numbers Ai,【Accepted】IOI2008 年中國集訓(xùn)隊(duì)第二輪作業(yè)雅禮中學(xué) 陳丹琦IDNumbers0Ai<106,要求你找一個最小的 m 使得 Ci=Ai mod m 兩兩不同, n300.m 滿足條件當(dāng)且僅當(dāng)對于任何兩個數(shù) Ai, Aj 滿足|Ai- Aj| mod m > 0.預(yù)處理 0106 每個數(shù)的最大質(zhì)因子 fi, 枚舉所有的|Ai - Aj|找出它的所有的因子,利用 f分解質(zhì)因數(shù)后再枚舉.最后選一個不是任何一個數(shù)的因子的最小的 m.3414Tantrix這個題目