08 2007 檔案

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