08 2007 檔案

• 點名游戲-被小菜點名了      摘要: 感興趣的進去慢慢看吧。
  
    閱讀全文
  posted @ 2007-08-31 20:02 Felicia 閱讀(246) | 評論 (2)  編輯
• [動態規劃]pku1947      摘要: 推薦此題。基礎樹型DP。
  f[x][i](1 <= i <= p)表示以x為根的子樹，變成剩下i個點的子樹，且剩余子樹包含根結點，需要去掉的最少邊數。
  那么父結點的f值可以由它所有的兒子的f值做背包得到。
  最后的答案是min(min(f[i][p]) + 1 (2 <= i <= n), f[1][p])
  
    閱讀全文
  posted @ 2007-08-31 18:27 Felicia 閱讀(870) | 評論 (0)  編輯
• [動態規劃]pku1848      摘要: 強烈推薦此題。樹型DP。
  分析較長且帶有圖示，請閱讀全文。
  
    閱讀全文
  posted @ 2007-08-30 21:47 Felicia 閱讀(1048) | 評論 (4)  編輯
• 妹妹的鼓勵      摘要: 妹妹說，難題得留著哥哥慢慢解，總會AC的。
  聽著心里很是受用呢。
  
    閱讀全文
  posted @ 2007-08-29 22:27 Felicia 閱讀(155) | 評論 (1)  編輯
• [動態規劃]pku1112      摘要: 強烈推薦此題。圖論和DP結合。
  分析較長，請閱讀全文。
  
    閱讀全文
  posted @ 2007-08-29 17:15 Felicia 閱讀(925) | 評論 (4)  編輯
• [動態規劃]pku2411      摘要: 經典的狀態壓縮DP。f[i][j]表示第i行，方格排布為二進制數j（第k位上為1表示凸出一個格子，為0表示不凸出）的方案數。用DFS進行狀態轉移。
  如果行數比較多的話，可以用矩陣乘法優化。因為每行的狀態轉移都是相同的。設烈數為m，行數為n，可以做到O(2^(3m)logn)。
  
    閱讀全文
  posted @ 2007-08-28 21:03 Felicia 閱讀(1425) | 評論 (12)  編輯
• [動態規劃]pku2288      摘要: 經典的TSP問題變種。狀態為f[i][j][k]，表示經過二進制數i所指的哈密頓路（第bi位為1表示經過該點，為0表示不經過該點），倒數第二個點為j，最后一個點為k。.value表示最大權值，.num表示能走出最大權值的路徑數。若圖中k到p有邊，f[i][j][k]則轉移到f[i'][k][p]。i' == i | (1 << p)。
  
    閱讀全文
  posted @ 2007-08-28 20:47 Felicia 閱讀(836) | 評論 (2)  編輯
• 歸來還是離去？      摘要:
  
    閱讀全文
  posted @ 2007-08-27 22:20 Felicia 閱讀(122) | 評論 (0)  編輯
• [動態規劃]pku1141      摘要: int f[i][j]表示第i個字符到第j個字符需要添加的最少括號數。string ans[i][j] 表示第i個字符到第j個字符按照最優方案添加括號后的串。狀態轉移：1.f[i][j]由f[i + 1][j - 1]轉移來（通過兩端添括號() / [] ）。2.f[i][j]由f[i][k] + f[k + 1][j]轉移來（通過串合并）。答案是ans[0][len - 1]。
  
    閱讀全文
  posted @ 2007-08-27 15:55 Felicia 閱讀(1244) | 評論 (3)  編輯
• [動態規劃]pku1050      摘要: 枚舉矩形的上邊和下邊，花費O(n^2)，把問題轉化成一維的最大M子段和，做一個O(n)的DP。
    閱讀全文
  posted @ 2007-08-26 13:51 Felicia 閱讀(1026) | 評論 (6)  編輯
• [動態規劃]pku 部分動態規劃題目列表      摘要: pku 部分動態規劃題目列表
  
    閱讀全文
  posted @ 2007-08-26 11:52 Felicia 閱讀(6599) | 評論 (5)  編輯
• [計算幾何]pku1389      摘要: 題目給出 n 個矩形，要求它們的面積并。具體做法是離散化。先把 2n 個 x 坐標排序去重，然后再把所有水平線段（要記錄是矩形上邊還是下邊）按 y 坐標排序。最后對于每一小段區間 (x[i], x[i + 1]) 掃描所有的水平線段，求出這些水平線段在小區間內覆蓋的面積。總的時間復雜度是 O(n^2)。利用線段樹，可以優化到 O(nlogn)。
  
    閱讀全文
  posted @ 2007-08-25 17:53 Felicia 閱讀(443) | 評論 (0)  編輯
• [計算幾何]pku1279      摘要: 求多邊形的核。用半平面交算法。
  
    閱讀全文
  posted @ 2007-08-25 15:56 Felicia 閱讀(662) | 評論 (4)  編輯
• [計算幾何]pku1418      摘要: 強烈推薦此題！
  先考察一下這個問題的性質。
  性質1：任何一個圓都覆蓋了一個閉區域。
  性質2：對于任意一個點，覆蓋它的最上面的那個圓，一定是可見的。
  性質3：如果一個圓不可見（它被完全覆蓋），那么它的邊界是被完全覆蓋的。
  性質4：n個圓最多有2(n-1)^2個交點，這些交點把n個圓分成最多2(n-1)^2條小圓弧。
  性質5：對于每個小圓弧，要么它全被覆蓋，要么它全不被覆蓋。
  根據性質1和性質2，問題轉化為恰當地找出一些點，對于每個點，把覆蓋它的最上面的圓標記為可見。
  根據性質3，這些點一定在所有圓的邊界集合內。
  根據性質5，所有小圓弧構成邊界集合。每個小圓弧上只要任意取一個點就能代表整個小圓弧（邊界）。不妨取中點。
  至此得到算法：取所有小圓弧的中點，對每個點找到覆蓋它的最上面的圓。
  根據性質4，最多取2(n-1)^2個點。對每個點找到覆蓋它的最上面的圓，需要O(n)次運算。總復雜度是O(n^3)。
  
    閱讀全文
  posted @ 2007-08-24 22:43 Felicia 閱讀(569) | 評論 (2)  編輯
• 又是一年仲夏·留給即將短暫離開的土地      摘要: Bless GCC!
  
    閱讀全文
  posted @ 2007-08-22 12:07 Felicia 閱讀(205) | 評論 (3)  編輯
• [計算幾何]pku1269      摘要: 很好的基礎題，判斷直線相交的情況。要注意精度。判斷平行和重合時，用整數運算比較精確。剩下的事就是解出交點了。
  
    閱讀全文
  posted @ 2007-08-21 22:30 Felicia 閱讀(455) | 評論 (0)  編輯
• [計算幾何]pku1118      摘要: 樸素做法是 O(n^3) 的，超時。我的做法是枚舉每個點，然后求其它點和它連線的斜率，再排序。這樣就得到經過該點的直線最多能經過幾個點。求個最大值就行了。復雜度是 O(n^2logn) 的。把排序換成 hash，可以優化到 O(n^2)。
  
    閱讀全文
  posted @ 2007-08-21 20:37 Felicia 閱讀(469) | 評論 (1)  編輯
• [計算幾何]pku2284      摘要: 應用平面圖的歐拉定理：V + F - E = 2
  兩兩線段求交，得到交點數 V，然后判斷每個交點落在幾條邊上，如果一個點在一條邊上，這條邊就分裂成兩條邊，邊數加 1。這樣得到邊數 E。最后直接用歐拉定理解得 F。
  
    閱讀全文
  posted @ 2007-08-21 17:26 Felicia 閱讀(355) | 評論 (0)  編輯
• [計算幾何]pku1151      摘要: 題目給出 n 個矩形，要求它們的面積并。具體做法是離散化。先把 2n 個 x 坐標排序去重，然后再把所有水平線段（要記錄是矩形上邊還是下邊）按 y 坐標排序。最后對于每一小段區間 (x[i], x[i + 1]) 掃描所有的水平線段，求出這些水平線段在小區間內覆蓋的面積。總的時間復雜度是 O(n^2)。利用線段樹，可以優化到 O(nlogn)。
  
    閱讀全文
  posted @ 2007-08-21 16:39 Felicia 閱讀(588) | 評論 (1)  編輯
• [計算幾何]pku1113      摘要: 先求凸包，答案是凸包周長 + 2πl。因為簡單多邊形的轉角是360度，所以加上一個圓的周長。
  
    閱讀全文
  posted @ 2007-08-21 15:43 Felicia 閱讀(493) | 評論 (0)  編輯
• [計算幾何]pku1106      摘要: 簡單題，直接模擬即可
  
    閱讀全文
  posted @ 2007-08-21 14:35 Felicia 閱讀(329) | 評論 (0)  編輯
• [計算幾何] pku1265      摘要: 公式很容易猜出，見代碼
  
    閱讀全文
  posted @ 2007-08-19 16:24 Felicia 閱讀(333) | 評論 (0)  編輯
• [計算幾何]pku 部分計算幾何題目列表      摘要: pku 部分計算幾何題目列表
  
    閱讀全文
  posted @ 2007-08-19 16:14 Felicia 閱讀(3211) | 評論 (12)  編輯
• [計算幾何]pku3347      摘要: 先把矩形擴大 sqrt(2) 倍，轉化為整點問題。然后逐個求出每個矩形的坐標。
  對于每個矩形分別求出在它之上的矩形覆蓋的區間大小 t1，和包括它本身以及在它之上的矩形覆蓋的區間大小 t2
  若 t1 == t2，則該矩形被遮蓋。
  
    閱讀全文
  posted @ 2007-08-15 21:37 Felicia 閱讀(397) | 評論 (0)  編輯
• [動態規劃]pku3345      摘要: 建立一個虛點（權為無窮大），從它到每個入度為 0 的點都連一條邊，然后做樹型DP。
  先遞歸算出子結點的 f 值，然后用背包的方法計算父結點的 f 值。
  
    閱讀全文
  posted @ 2007-08-15 18:42 Felicia 閱讀(631) | 評論 (0)  編輯
• [計算幾何]pku3334      摘要: 二分水面高度，然后求總水量（就是求多邊形面積）
  
    閱讀全文
  posted @ 2007-08-15 08:59 Felicia 閱讀(460) | 評論 (1)  編輯
• [計算幾何]pku3335      摘要: 求多邊形的核
  
    閱讀全文
  posted @ 2007-08-14 19:29 Felicia 閱讀(501) | 評論 (0)  編輯
• 2007 校賽總結 by Felicia [2007.4.23]      摘要: 2007 校賽總結 by Felicia
  
    閱讀全文
  posted @ 2007-08-14 16:17 Felicia 閱讀(460) | 評論 (0)  編輯
• [轉載]淺談ACM/ICPC的題目風格和近幾年題目的發展      摘要: 淺談ACM/ICPC的題目風格和近幾年題目的發展
  
    閱讀全文
  posted @ 2007-08-14 16:13 Felicia 閱讀(629) | 評論 (0)  編輯
• [圖論]最大流(類實現)      摘要: 復雜度 O(n^2m)。支持一邊構建網絡，一邊求最大流。每次調用 flow()，得到當前新增的流量。
  
    閱讀全文
  posted @ 2007-08-13 21:12 Felicia 閱讀(1024) | 評論 (1)  編輯
• [計算幾何]pku1696      摘要: 先按題意找出最低點作為起始點，計算出起始向量。然后每次選擇左轉角度最小的點走。一定能走完 n 個點。
  
    閱讀全文
  posted @ 2007-08-13 20:46 Felicia 閱讀(496) | 評論 (0)  編輯
• [計算幾何]pku1687      摘要: 題目要求從幾個區域中，求出包含其它區域的那個區域。其實就是求最大區域。
  只要對每個區域依次計算面積即可，然后取最大的那個。
  
    閱讀全文
  posted @ 2007-08-13 19:07 Felicia 閱讀(445) | 評論 (0)  編輯
• 凸包(類實現)      摘要: 凸包(類實現)
  
    閱讀全文
  posted @ 2007-08-13 14:49 Felicia 閱讀(852) | 評論 (0)  編輯
• [計算幾何]pku1654      摘要: 記錄當前點和前一個點的坐標，算叉積，然后加入總面積之中
  注意最后得到的面積有可能是負的，要取絕對值，還有答案有可能超過 int 范圍，要用 long long
  
    閱讀全文
  posted @ 2007-08-13 13:42 Felicia 閱讀(681) | 評論 (0)  編輯
• [計算幾何]pku1556      摘要: 如果兩點的連線不和墻相交，那么在圖中為這兩點連一條邊，權值為這兩點的距離
  然后做 Dijkstra
  
    閱讀全文
  posted @ 2007-08-13 10:34 Felicia 閱讀(479) | 評論 (0)  編輯
• 西安賽區總結 by Felicia [2006.12.26]      摘要: 西安賽區總結 by Felicia
  
    閱讀全文
  posted @ 2007-08-13 10:27 Felicia 閱讀(562) | 評論 (2)  編輯
• 2006上海區域賽總結[2006.11.25]      摘要: 2006上海區域賽總結
  
    閱讀全文
  posted @ 2007-08-13 10:25 Felicia 閱讀(583) | 評論 (0)  編輯
• 我對11月12日 Moonmist & Deathdecay 北京之行的感想[2006.11.14]      摘要: 我對11月12日 Moonmist & Deathdecay 北京之行的感想
  
    閱讀全文
  posted @ 2007-08-13 10:19 Felicia 閱讀(440) | 評論 (1)  編輯
• Silence總結[2006.10.15]      摘要: Silence 總結
  
    閱讀全文
  posted @ 2007-08-13 10:15 Felicia 閱讀(442) | 評論 (0)  編輯
• 單源最短路 Dijkstra O(mlogn) (類實現)      摘要: 單源最短路 Dijkstra O(mlogn) (類實現)
  
    閱讀全文
  posted @ 2007-08-13 10:01 Felicia 閱讀(832) | 評論 (1)  編輯
• [計算幾何]pku1375      摘要: 對每個圓作切線，求出投影區間，最后全部求并
  
    閱讀全文
  posted @ 2007-08-12 18:35 Felicia 閱讀(367) | 評論 (0)  編輯
• [計算幾何]pku1031      摘要: 對多邊形的每個邊計算和原點的夾角范圍，求并得到總夾角范圍 alpha
  答案就是 min(alpha, 2 * pi) * k * h
  
    閱讀全文
  posted @ 2007-08-12 12:06 Felicia 閱讀(894) | 評論 (2)  編輯
• [計算幾何]pku1873      摘要: 暴力枚舉砍掉的樹，然后對剩余的樹求凸包
  
    閱讀全文
  posted @ 2007-08-12 11:52 Felicia 閱讀(472) | 評論 (0)  編輯
• 二分圖最大匹配(類實現)      摘要: 二分圖最大匹配(類實現)
  
    閱讀全文
  posted @ 2007-08-11 21:30 Felicia 閱讀(1231) | 評論 (0)  編輯