講稿集訓(xùn)隊作業(yè)solution

1、NEERC2006NEERC2006完成情況在PKUOnlineJudge上的測試情況A:PKU1827770hupo0013148Accepted104K306MSPascal5198B2006-12-12B:PKU1827267hupo0013149AcceptedNEERC2006NEERC2006完成情況在PKUOnlineJudge上的測試情況A:PKU1827770hupo0013148Accepted104K306MSPascal5198B2006-12-12B:PKU1827267hupo0013149Accepted5592K479MSPascal2597B2006-12-1

2、2C:PKU1828685hupo0013150Accepted24K1933MSPascal1622B2006-12-1301:38:37 D: -E:PKU1827277hupo0013152Accepted976K999MSPascal5192B2006-12-1218:45:21 F: -G:PKU1827284hupo0013154Accepted4K45MSPascal663B2006-12-12H:PKU1827300hupo0013155Accepted216K6227MSPascal5357B2006-12-12I:PKU1827296hupo0013156Accepted9

3、12K1544MSPascal4537B2006-12-12J:PKU1827303hupo0013157Accepted4K30MSPascal2037B2006-12-12K:PKU1827315hupo0013158Accepted0K60MSPascal1242B2006-12-12第 1 頁 共 15 S AASCII BBillingC-D E-FFoolsGHHardIJJavavsKNEERC2006ProblemA:ASCII在w*h網(wǎng)格平面內(nèi), 按順時針給出一個含n個頂點且都在格點上的簡單多邊形(不自交), 統(tǒng)計每個格子被覆蓋的面積的狀況. (w, h, n = 100)枚

4、舉指定的格子, 再與多邊形求交比較麻煩, 復(fù)雜度也高. 實際上, 可以對多邊形的面積進行梯形剖分即每條邊的端點向x軸做投影, 投影點與端點組成的梯形有向面積之和, 原面積. 針輸入的, 則從右向左的有向線段對應(yīng)的梯形面積為負, 從左向右則為正. NEERC2006ProblemA:ASCII在w*h網(wǎng)格平面內(nèi), 按順時針給出一個含n個頂點且都在格點上的簡單多邊形(不自交), 統(tǒng)計每個格子被覆蓋的面積的狀況. (w, h, n = 100)枚舉指定的格子, 再與多邊形求交比較麻煩, 復(fù)雜度也高. 實際上, 可以對多邊形的面積進行梯形剖分即每條邊的端點向x軸做投影, 投影點與端點組成的梯形有向面積

5、之和, 原面積. 針輸入的, 則從右向左的有向線段對應(yīng)的梯形面積為負, 從左向右則為正. 如左圖, ABC, AEDB(Green)BDFC(All)CBAEFD接下來處理每個梯形, 枚舉被梯形覆蓋的每列格子, 按列分別處理. 對于每列, 格子的連續(xù)段, 如右圖的Yellow部分; 的, 如右圖的Red部分. 可以直接處理掉部分. 對于每一個Yellow部分中的格子, 4的平面交, 若不考慮特殊性, 2種情況(對邊, 鄰邊一下即可. 實際上, 我不想那么麻煩, 寫了個凸包算面積第 2 頁 共 15 NEERC2006ProblemB:Billing11 位的數(shù)字串, 按優(yōu)先級給定一系列區(qū)間,

6、每個區(qū)間有一個標(biāo)志. 區(qū)間包含(多個, 則取優(yōu)先級高的), 號碼就具有該區(qū)間的標(biāo)志NEERC2006ProblemB:Billing11 位的數(shù)字串, 按優(yōu)先級給定一系列區(qū)間, 每個區(qū)間有一個標(biāo)志. 區(qū)間包含(多個, 則取優(yōu)先級高的), 號碼就具有該區(qū)間的標(biāo)志. 現(xiàn)在要求輸出用前綴表示的帶標(biāo)志序列號碼的前綴被匹配, 號碼就一定具有該前綴的標(biāo)志Trie 樹的葉子. 號碼前綴, 完全包含或被幾個標(biāo)志一樣的區(qū)間完全包含, 則作為一個葉子結(jié)點, 否則繼續(xù)擴展. 即可12每次檢查結(jié)點是否被包含, O(n)時間. 總復(fù)雜度為O(Ans*n)Ans為葉子總數(shù)第 3 頁 共 15 NEERC2006Probl

7、emC:Cellular給定一個長度為nA. 定義一種操作, A滿足Ai Aj )modmin(|i-j|, n-|i-Ai為所有和i的圓距離不超過dAj之和. 問經(jīng)過k次操作后的序列(n500,k10000000, m = 1000000, d = n / 2)每次操作, M A A 11NEERC2006ProblemC:Cellular給定一個長度為nA. 定義一種操作, A滿足Ai Aj )modmin(|i-j|, n-|i-Ai為所有和i的圓距離不超過dAj之和. 問經(jīng)過k次操作后的序列(n500,k10000000, m = 1000000, d = n / 2)每次操作, M

8、A A 111010111001100001101A1 A1 0 A A 2 2 A330 1 1 A A n n 其中n*nM為: (上面例子中的矩陣是d=1的情況min(|i-j|,n-|i-j|)Mi, 這就是Mk A, 其中矩陣的冪運算可以用倍增法在O(log k)次矩陣乘法下得出. 然而每次的矩陣乘法還是太慢, 需要改進. 觀察矩陣 M 的特殊性: 第二行是第一行右移一位, 第三行是第二行右移一位, ., 等等. 即上行右移一位為下行. 設(shè)第一行為x1, x2, ., xn, 則矩陣M 可以寫為:xnx2 x1 同樣的, 對于列也一樣, 左行下移一位為右行. 設(shè)第一列為y1y2yn,

9、 則矩陣M可以寫為 y2 21yn y 1 稱這樣的性質(zhì)為循環(huán)矩陣以上兩種表示法是同構(gòu)的兩種表示法相乘的結(jié)果第 4 頁 共 15 NEERC2006 x1y1x2y2 xn x1yn NEERC2006 x1y1x2y2 xn x1yn x2y1 xnx1y2x2y3xny1 xyxy xyxy xyxy xxyxyn 1 2 n 1 2 n 1 2 x y x y x y x xx y x y n 1 1n 1 2 2 n 1 2 結(jié)果依然是一個循環(huán)矩陣, 即一個循環(huán)矩陣乘循環(huán)矩陣還是循環(huán)矩陣. 一列就可以得到整個矩陣, 就是說每次乘法只要算出結(jié)果的第一行或第一列即可. 乘法的時間降為O(n

10、2). 第 5 頁 共 15 NEERC2006ProblemD:Driving在平面上有n(n=物, NEERC2006ProblemD:Driving在平面上有n(n=物, 現(xiàn)需要將一個半徑為r的圓從A點移動到B點. 求最短路將圓靠著矩形滑動(相切), 圓心的軌跡形成了一個導(dǎo)圓角矩形. 導(dǎo)圓角矩形是由原矩形的 4 條邊向外平移一個半徑的距離, 加上4 個1/4 圓作為導(dǎo)角. 導(dǎo)圓角矩形圓心無法進入. 問題轉(zhuǎn)化成, 在若干導(dǎo)圓下, 一個點移動到另一個點的最短路由于在曲線上點是連續(xù)的, 無法使用圖論算法, 所以需要根據(jù)最短路的性質(zhì)進行點的離散化, 圖(1) 邊上的點如下圖, 粗藍色代表導(dǎo)圓角矩

11、形上的完整的直線段. 的任意一點 由三角形的性質(zhì), ADCD一定比ABD,CBD短. A, C, 點作為離散點第 6 頁 共 15 NEERC2006DABC(2) 弧上的(2.1)如下圖, 對于在另一個導(dǎo)圓角矩形NEERC2006DABC(2) 弧上的(2.1)如下圖, 對于在另一個導(dǎo)圓角矩形上的弧l, 與弧AB的相切, 切線段為CD, C, D分別為兩段弧上的切點C,D都應(yīng)作為離散點A到l的最短路必經(jīng)過C,D, CD為該路徑上離開或進入導(dǎo)圓角矩形的ACBD(2.2)如下圖, 對于不在導(dǎo)圓角矩DDAB相切于C. C應(yīng)作為離散點. 因為從BD的路徑只有過C點的路徑最短, 且C為離開導(dǎo)圓角矩形的

12、事件點DACB由于(2.1)O(n2)個離散點, O(n2)條邊; 接著(2.2)會在(2.1)的基礎(chǔ)上產(chǎn)生(n3)的離散點, O(n3)條邊. 實際上, 在(2.1)中, 點和邊是共生的, 即在產(chǎn)生邊的過程中, 若該邊與 相交, 則需要取消離散點. 判斷邊與 相交需要 O(n), O(n4).最后運行Dijkstra算法即可, 復(fù)雜度為O(VE)logV)O(n3log第 7 頁 共 15 NEERC2006ProblemE:NEERC2006ProblemE:賣訂單SellOrder含: 供應(yīng)物品個數(shù), 價格.Buy Order 含: 需物品個數(shù), 出價.要求寫一個交易系統(tǒng). 對于當(dāng)前買訂

13、單, 若當(dāng)前價格最低的賣訂單低于當(dāng)前出價, 則發(fā)生交易. 對于當(dāng)前賣訂單, 若當(dāng)前出價最高的買訂單, 高于當(dāng)前價格, 則發(fā)生交易. 當(dāng)出價或價格相同時, 按訂單的先后循序發(fā)生交易. 發(fā)生交易時, 按供需物品個數(shù)的最小值交易. 交易后, 需要修改訂單的供需物品個數(shù). 訂單可以取3種命令: BUY, 賣訂單SELL, CANCEL. 共n個命令每個命令后, (n=格的物品總數(shù)和當(dāng)前處于最高出價的物品總數(shù)每次要取最小或最大, 所以訂單隊列是一個優(yōu)先隊列. 用最大堆模擬買訂單, 用最小堆模擬賣訂單. 接模擬. O(nlog第 8 頁 共 15 NEERC2006ProblemNEERC2006Prob

14、lemF:Fools第 9 頁 共 15 NEERC2006ProblemG:10000的圓上, 等距分布著NEERC2006ProblemG:10000的圓上, 等距分布著n個點. 現(xiàn)在再加入m個點. 要使得nm個點在圓在等距分布. 這就可能需要移動原來的n 個點到新位置上, 要求移動(沿著圓周移動)的總距離和最小. (n, m = 0, z(量Xv,Yez(中, 必會得到一個更大的z值, 所以z 單調(diào)遞減. 所以有z()0 z()0 這就意味著可以進行二分搜* . 注意初始范圍: *0,|E|. 關(guān)于01 分數(shù)規(guī)劃參見1或優(yōu)比率生成樹的解法zYe Xv 的最大值. 它需要滿足限制: 邊(u

15、, v)的選取, u, v 選取. 這樣的依賴關(guān)系與函數(shù)的形式使 想到了最小割來解決這類問題, 參見2. 建立二分圖XXv代表點vY部的點Ye代表邊e. 若邊e 2 個點u, v, 則分別從Xu, Xv Ye 連一條容量為正無限的邊. 再S, T. S Xv 連容量為的邊, Ye T 1 的邊. |E|Mincut割Mincut. STEdmonds Karp 算法. O(|V|+|E|), O(|E|). 第 11 頁 共 15 NEERC2006O(|E|). O(|E|2)次. 算法總復(fù)雜度為O(|E|3 log R). 而實際情況會比這個估計好很多NEERC2006O(|E|). O(

16、|E|2)次. 算法總復(fù)雜度為O(|E|3 log R). 而實際情況會比這個估計好很多. 稀疏二分圖的增O(|E|2). 這題使用Relabel to front Preflow Push O(|E|3), 反而會超時.另一解ST直接保留原圖即若原圖存在邊(u,vXuXv連一條容量為正無限的邊, XvXu也連一條容量為正無限的邊STSXvm的邊, XvT m-Dv+2的邊Dv表示點v的度O(|V|), O(|E|). PreflowPushO(|V|3), 效果 ProblemsysisofDinkelbachsAlgorithmfor0-1Fractional2roductiontoAlg

17、orithm,Problems26-3:huttle12 頁 共 15 NEERC2006Problem給出無向圖G(VE). 每次操作任意加一條非自環(huán)的邊(u,v), 每條邊的選擇是等概率的. G連通的期望操作次數(shù). (|V| = 30, |E| = 1000)圖的狀態(tài)的表示NEERC2006Problem給出無向圖G(VE). 每次操作任意加一條非自環(huán)的邊(u,v), 每條邊的選擇是等概率的. G連通的期望操作次數(shù). (|V| = 30, |E| = 1000)圖的狀態(tài)的表示: 由于每次加邊是等概率的, 且只需要考慮圖的連通性, 每次加邊要么不改變連通性,要么把兩個連通塊合并. 只要把圖的

18、連通狀況表示出來. 于是, 狀態(tài)就是每個連通塊的大小的集合. (|C1 |,|C2 |,|Ck |. Ci 為每個連通塊, k 個連通塊. 這樣的狀態(tài)有多少個呢? 實際上就是 應(yīng)n的整數(shù)拆分的個數(shù)f(n,k)表示把n拆分為k份的個數(shù), 有f (n,k) f (nk,k) f (n,k 由上式得到f(30,30)5604. 狀態(tài)數(shù)不多記當(dāng)前狀態(tài)為 S |C1 |,|C2 |,|Ck |由于點的標(biāo)號是沒有關(guān)系的, 為避免狀態(tài)重復(fù), 規(guī) 定|C1 |C2 |Ck |.g(SS 到完全連通的期望步數(shù). g(n) 0. 有如下方程 立j |g(S)g(S C(n, C(n, 1i 其中 S |C1 |,|C2 |,| Ci1 |,| Ci | | Cj |,| Ci1 |,| Cj1 |,| Cj1 |,| Ck | , 示連通塊Ci, Cj 合并后的狀態(tài). |Ci |Cj |表示使連通塊Ci, Cj 合并的可能加邊的個數(shù)C(n2)表示總可能加邊數(shù)p C(n2|Ci |Cj |, 表示使?fàn)顟B(tài)S不改變的可能加邊的個數(shù). 該方程等式右邊有兩個部分1i j每次加邊要么不改變連通性, 要么把兩個連通塊合并.S與S是滿足拓補序的, 即g(S)不會依賴g(S). 這樣就可以動態(tài)規(guī)劃. 最后關(guān)于g(