09 2007 檔案

• [動態規劃]pku1185      摘要: 經典的狀態壓縮DP，狀態是f[i][j]，表示第i行，以3進制j為狀態。j的位代表一個格子，只能是：0表示第i行和第i - 1行都沒有炮兵，1表示第i行沒有炮兵而第i-1行有炮兵，2表示第i行有炮兵。然后用DFS進行狀態轉移。一開始我做了超時，后來預處理了一下合法狀態，快了不少，才AC。
  
    閱讀全文
  posted @ 2007-09-30 22:09 Felicia 閱讀(1057) | 評論 (0)  編輯
• [動態規劃]pku1163      摘要: 今天郁悶了，貼個小代碼
  
    閱讀全文
  posted @ 2007-09-29 22:43 Felicia 閱讀(552) | 評論 (0)  編輯
• [動態規劃]動態規劃總結 by Amber      摘要: 動態規劃總結 by Amber
  
    閱讀全文
  posted @ 2007-09-29 20:25 Felicia 閱讀(4002) | 評論 (0)  編輯
• [計算幾何]pku3391      摘要: 問題是求平面歐幾里德最小生成樹的第n - k小邊。
  平面歐幾里德最小生成樹是經典問題，可以做到O(nlogn)。具體做法是先對平面點進行三角剖分，時間復雜度是O(nlogn)，三角剖分的邊就是可能的在最小生成樹的邊。因為是平面圖，所以有O(n)條邊，在其上應用 Kruscal 算法即可。
  
    閱讀全文
  posted @ 2007-09-28 20:17 Felicia 閱讀(792) | 評論 (0)  編輯
• 漫談扭結      摘要: 漫談扭結
  
    閱讀全文
  posted @ 2007-09-27 17:26 Felicia 閱讀(1888) | 評論 (2)  編輯
• [計算幾何]pku1673      摘要: 此問題可轉化為求三角形垂心。我的做法是設垂心坐標為(x, y)，然后利用垂直關系解方程。
  
    閱讀全文
  posted @ 2007-09-27 17:18 Felicia 閱讀(668) | 評論 (1)  編輯
• Ubuntu 6.10 @ Dell XPS M1210 安裝手記      摘要: Ubuntu 6.10 @ Dell XPS M1210 安裝手記
  
    閱讀全文
  posted @ 2007-09-27 15:21 Felicia 閱讀(684) | 評論 (0)  編輯
• [轉載]好友的一首小詩      摘要: 一首小詩……
  
    閱讀全文
  posted @ 2007-09-27 15:06 Felicia 閱讀(206) | 評論 (0)  編輯
• [計算幾何]平面點的曼哈頓最小生成樹      摘要: 平面點的曼哈頓最小生成樹
  
    閱讀全文
  posted @ 2007-09-27 14:48 Felicia 閱讀(1282) | 評論 (0)  編輯
• [計算幾何]pku1624      摘要: 簡單計算幾何，我的做法是列出所有可能的切法（一共18種），求最優值。
  
    閱讀全文
  posted @ 2007-09-26 20:46 Felicia 閱讀(606) | 評論 (1)  編輯
• [計算幾何]pku1408      摘要: 構造所有的線段，然后枚舉每對水平－豎直線段，求交點，然后計算四邊形面積，求最大值。
  
    閱讀全文
  posted @ 2007-09-25 21:59 Felicia 閱讀(634) | 評論 (0)  編輯
• [動態規劃]pku3133      摘要: 強烈推薦此題！
  狀態壓縮DP的好題！
  分析見內
  
    閱讀全文
  posted @ 2007-09-24 21:12 Felicia 閱讀(1160) | 評論 (4)  編輯
• [計算幾何]pku3384      摘要: 強烈推薦此題。半平面交算法的一個應用。
  具體做法是，把多邊形的每條邊向內平移r單位長度，用這些線段所在直線和原多邊形作半平面交，得到的區域就是半徑為r的圓放入多邊形的可行域。可以證明這個區域一定是凸的，或者退化為一條線段，或一個點。那么，我們就可以在這個區域上求最遠點對啦。
  我的做法是O(n^2)的。應該存在O(nlogn)的做法，因為都是凸多邊形，每次半平面交只有最多兩個交點，可二分，而最后的求最遠點對可以旋轉卡殼。比賽的時候時間少，就寫了個暴力O(n^2)的。
  
    閱讀全文
  posted @ 2007-09-23 16:19 Felicia 閱讀(801) | 評論 (0)  編輯
• [計算幾何]pku1410      摘要: 基本幾何題，判斷線段是否與矩形相交。轉化為線段在矩形內或線段與四條邊相交。
  唯一要注意的是題目中關于左上角和右下角的定義。
  
    閱讀全文
  posted @ 2007-09-22 10:58 Felicia 閱讀(542) | 評論 (0)  編輯
• [計算幾何]pku1319      摘要: 這個題需要分情況討論。如果是grid，就能直接算，如果是skew，就一層層往上模擬著堆。最后取最大值。
  
    閱讀全文
  posted @ 2007-09-21 21:56 Felicia 閱讀(453) | 評論 (2)  編輯
• [計算幾何]兩圓求交點      摘要: mmd 和 cz 的智慧結晶。某次比賽的時候寫的。
  
    閱讀全文
  posted @ 2007-09-20 18:34 Felicia 閱讀(5876) | 評論 (7)  編輯
• 太難過了      摘要: 這是胡說八道
  
    閱讀全文
  posted @ 2007-09-19 18:06 Felicia 閱讀(239) | 評論 (0)  編輯
• [計算幾何]pku1586      摘要: 超級惡心的精度題。注意讀清題意，然后直接做就行了。
  
    閱讀全文
  posted @ 2007-09-19 17:47 Felicia 閱讀(462) | 評論 (0)  編輯
• [圖論][zz]給出一個沒有偶圈的簡單無向圖，求兩個頂點間路徑的數目      摘要: 給出一個沒有偶圈的簡單無向圖，求兩個頂點間路徑的數目
  
    閱讀全文
  posted @ 2007-09-19 10:08 Felicia 閱讀(995) | 評論 (2)  編輯
• [計算幾何]pku2954      摘要: Pick公式的應用。先介紹一下Pick公式：
  a = e / 2 + i - 1
  a為多邊形（頂點都在格點上）面積，e為多邊形邊上的格點數，i為多邊形內部的格點數。
  題目給出三點坐標，邊上的格點數可用gcd求得，剩下的事就是解方程了。
  
    閱讀全文
  posted @ 2007-09-18 21:59 Felicia 閱讀(446) | 評論 (0)  編輯
• 唔，我喜歡這首詩      摘要: 喜歡搞笑的詩的請進
  
    閱讀全文
  posted @ 2007-09-17 18:39 Felicia 閱讀(188) | 評論 (0)  編輯
• [計算幾何]pku1569      摘要: 枚舉三角形，然后判斷是否其余的點都不在形內，也不在邊上。時間復雜度是O(n^4)。
  
    閱讀全文
  posted @ 2007-09-16 21:19 Felicia 閱讀(373) | 評論 (0)  編輯
• [計算幾何]pku3129      摘要: 很簡單的幾何題。直接硬搞即可。
  
    閱讀全文
  posted @ 2007-09-15 20:25 Felicia 閱讀(395) | 評論 (0)  編輯
• [轉]WinSock學習筆記[2]      摘要: Winsock入門
  
    閱讀全文
  posted @ 2007-09-14 22:26 Felicia 閱讀(220) | 評論 (0)  編輯
• [轉]WinSock學習筆記[1]      摘要: Winsock入門
  
    閱讀全文
  posted @ 2007-09-14 22:23 Felicia 閱讀(195) | 評論 (0)  編輯
• [計算幾何]pku一些關于多邊形的題目      摘要: 見內
  
    閱讀全文
  posted @ 2007-09-14 22:21 Felicia 閱讀(550) | 評論 (0)  編輯
• [計算幾何]pku3130      摘要: 又是一個求多邊形的核的題。
  
    閱讀全文
  posted @ 2007-09-14 22:18 Felicia 閱讀(497) | 評論 (0)  編輯
• I Want A Wife      摘要: :)
  
    閱讀全文
  posted @ 2007-09-13 14:17 Felicia 閱讀(258) | 評論 (2)  編輯
• [計算幾何]pku2079      摘要: 先求凸包，然后再用旋轉卡殼方法求解。
  具體做法是枚舉三角形的第一個點i，設j = i + 1，k = j + 1。然后做以下操作：
  1.計算i，j，k構成的三角形面積a1和i，j，k + 1構成的三角形面積a2，如果a2 < a1，則進行下一步，否則k++，重復此步。
  2.記錄此時的三角形面積b，如果b < preb（就是上一個j對應的三角形面積）j++，轉第一步，否則退出。
  可以證明這個算法的復雜度為O(n2)。具體實現見代碼。
  
    閱讀全文
  posted @ 2007-09-13 13:40 Felicia 閱讀(870) | 評論 (0)  編輯
• [動態規劃]pku1038      摘要: 經典的狀態壓縮DP，《算法藝術與信息學競賽》的例題。f[i][j]表示前i行，最后兩行狀態為二進制數j，嵌入的最多芯片數。第i行到第i+1行用DFS進行狀態轉移。
  由于第i+1行只和第i行有關，故可以用滾動數組優化。
  
    閱讀全文
  posted @ 2007-09-12 20:44 Felicia 閱讀(1566) | 評論 (3)  編輯
• [動態規劃]pku3375      摘要: A O(NM) dynamic programming algorithm is quite apparent after sorting the computers and network interfaces by their coordinates. Furthermore, in any optimized case, for each computer the difference between the the indices of the network interfaces matching to and closest to the computer is never larger than N. So the complexity could be reduced to O(N2)
  
  有很多細節不好考慮，應該是我的水平原因。最后我向updog要了數據才過的。而且代碼寫的不好。將就看一下吧。
  
    閱讀全文
  posted @ 2007-09-11 22:28 Felicia 閱讀(822) | 評論 (1)  編輯
• [計算幾何]pku1494      摘要: 其實是初等幾何題。在紙上畫一下就出來了。
  
    閱讀全文
  posted @ 2007-09-10 20:48 Felicia 閱讀(461) | 評論 (0)  編輯
• [計算幾何]pku1473      摘要: 很簡單的題。直接按照題意模擬即可。
  
    閱讀全文
  posted @ 2007-09-10 16:58 Felicia 閱讀(382) | 評論 (0)  編輯
• 無敵詭異的姓名測試      摘要: 對搞笑的事情感興趣的請進
  
    閱讀全文
  posted @ 2007-09-10 13:13 Felicia 閱讀(189) | 評論 (0)  編輯
• [計算幾何]pku1039      摘要: 具體算法在《算法藝術與信息學競賽》里有講。
  
    閱讀全文
  posted @ 2007-09-09 22:01 Felicia 閱讀(778) | 評論 (0)  編輯
• [計算幾何]pku1133      摘要: 這個題目我用的是枚舉。具體做法是，對于每個星座，把它的第1個點放在星圖的第i個點上，第2個點放在星圖的第j個點上（i != j），保持形狀不變，移動這個星座中的其他點，看看這些點是否都和星圖中的點重合。若滿足條件，則找到一個匹配。如此得到星座c對星圖的匹配數a。再得到星座c對它本身的匹配數b。那么星座c的出現次數就是 a / b。對于只有一個星星的星座，要特殊考慮一下。至于找出最亮星座，方法很簡單：每次記錄亮度值，發現更亮的就更新解。
  
  p.s. 我一開始是用STL的complex做的，超時。后來改成向量做了。
  
    閱讀全文
  posted @ 2007-09-08 22:42 Felicia 閱讀(531) | 評論 (1)  編輯
• [計算幾何]pku1092      摘要: 題目要求統計一個平面圖中所有邊數為k的面的個數。應該是個經典問題。說說我的算法吧。
  枚舉每條邊，做以下的基本步驟。
  
  基本步驟：以這條邊作起始邊，不斷地找下一條“最左轉”的邊，并且標記每個點的訪問次數，直到某個點第3次被訪問為止。
  經過這個步驟之后，得到一個頂點序列。容易知道，當且僅當這個頂點序列是2-重復（就是形如12341234這樣），并且是逆時針旋轉的，那么就是一個面。
  接下去我們就把所有找到的邊數為k面進行hash去重，就得到答案啦。
  貌似我想的這個算法不夠好，如果有更好的算法，歡迎和我討論。
  
    閱讀全文
  posted @ 2007-09-07 19:37 Felicia 閱讀(661) | 評論 (0)  編輯
• 友情鏈接邀請
  posted @ 2007-09-07 16:15 Felicia 閱讀(1132) | 評論 (42)  編輯
• [計算幾何]pku1471      摘要: 這題勉強算幾何吧。我寫了個超級慢的枚舉。
  
    閱讀全文
  posted @ 2007-09-06 20:02 Felicia 閱讀(435) | 評論 (0)  編輯
• [計算幾何]pku1434      摘要: 簡單幾何題，但是容易WA。做法是二分水面高度，然后看看這個高度對應多少水。
  
    閱讀全文
  posted @ 2007-09-05 21:30 Felicia 閱讀(356) | 評論 (0)  編輯
• 到武漢啦！      摘要: 對我的悲慘人生感興趣的請進
  
    閱讀全文
  posted @ 2007-09-05 20:25 Felicia 閱讀(232) | 評論 (0)  編輯
• [動態規劃]pku1170      摘要: 呼~今天去學校啦！早上7點起床寫題，挑了個簡單題寫 ^_^
  這個是IOI95的DP題。用一個b位的6進制數i表示狀態。這個6進制數的每一位分別表示相應物品的數量。f[i]表示狀態i下的最小花費。同樣也可以用6進制數j表示優惠。那么，f[i]就能轉移到f[i - j]，如果優惠j可用的話。代價是使用優惠j時減少的花費。最后的答案就是min(f[i])，0 <= i <= start（start是初始狀態）。
  
    閱讀全文
  posted @ 2007-09-04 08:37 Felicia 閱讀(687) | 評論 (0)  編輯
• [動態規劃]pku1160      摘要: 先預處理，把第i個村子到第j個村子中，建一個郵局的最小代價算出來，存在min_cost[i][j]里。
  接下來就可以DP。設f[i][j]為前i個郵局，建在前j個村子的最小代價。那么f[i][j]可以轉移到f[i + 1][j + k]，(1 <= k 且 j + k <= n)，代價是min_cost[j + 1][j + k]。
  
    閱讀全文
  posted @ 2007-09-03 22:44 Felicia 閱讀(1515) | 評論 (3)  編輯
• [圖論]pku1125      摘要: 簡單題。很早以前做的。貼一下凌亂的代碼。
  
    閱讀全文
  posted @ 2007-09-02 20:09 Felicia 閱讀(509) | 評論 (2)  編輯
• [動態規劃]pku1088      摘要: 簡單的記憶化搜索。很早以前做的，代碼風格很亂。將就一下啦。
  
    閱讀全文
  posted @ 2007-09-02 20:02 Felicia 閱讀(929) | 評論 (5)  編輯
• [動態規劃]pku1737      摘要: 樓爺的題。遞推。f[n]表示n個結點的連通圖個數，則有遞推公式：
  
  void calc(int n)
  {
  f[n] = 0;
  for (int i = 1; i < n; i++)
  f[n] += f[i] * f[n - i] * (pow(i) - 1) * C(n - 2, i - 1);
  //pow(x) == 2^x
  }
  
  因為數據較多，所以預先算出f[1] -- f[50]，再輸出。要用高精度。我用了標程。
  
    閱讀全文
  posted @ 2007-09-02 13:53 Felicia 閱讀(778) | 評論 (6)  編輯
• [動態規劃]pku1946      摘要: 首先明確一點：最優解必為奶牛1..n-1輪流領跑，奶牛n撞線。且跑了x圈后，未領跑過的奶牛都耗費了x的體力。
  設f[i][j][k]表示前i-1頭奶牛已領跑，現在由第i頭奶牛領跑，一共跑了j圈，奶牛i耗費了k的體力。
  則f[i][j][k]可以轉移到f[i][j + p][k + p^2]（耗費1分鐘，奶牛i以p圈/分鐘的速度繼續領跑），也可轉移到f[i + 1][j][j]（換成奶牛i + 1領跑，不耗費時間）。
  時間復雜度為O(nde^2.5)。
  
    閱讀全文
  posted @ 2007-09-01 11:42 Felicia 閱讀(495) | 評論 (1)  編輯