09 2007 檔案

• [動(dòng)態(tài)規(guī)劃]pku1185      摘要: 經(jīng)典的狀態(tài)壓縮DP，狀態(tài)是f[i][j]，表示第i行，以3進(jìn)制j為狀態(tài)。j的位代表一個(gè)格子，只能是：0表示第i行和第i - 1行都沒有炮兵，1表示第i行沒有炮兵而第i-1行有炮兵，2表示第i行有炮兵。然后用DFS進(jìn)行狀態(tài)轉(zhuǎn)移。一開始我做了超時(shí)，后來預(yù)處理了一下合法狀態(tài)，快了不少，才AC。
  
    閱讀全文
  posted @ 2007-09-30 22:09 Felicia 閱讀(1049) | 評(píng)論 (0)  編輯
• [動(dòng)態(tài)規(guī)劃]pku1163      摘要: 今天郁悶了，貼個(gè)小代碼
  
    閱讀全文
  posted @ 2007-09-29 22:43 Felicia 閱讀(545) | 評(píng)論 (0)  編輯
• [動(dòng)態(tài)規(guī)劃]動(dòng)態(tài)規(guī)劃總結(jié) by Amber      摘要: 動(dòng)態(tài)規(guī)劃總結(jié) by Amber
  
    閱讀全文
  posted @ 2007-09-29 20:25 Felicia 閱讀(3991) | 評(píng)論 (0)  編輯
• [計(jì)算幾何]pku3391      摘要: 問題是求平面歐幾里德最小生成樹的第n - k小邊。
  平面歐幾里德最小生成樹是經(jīng)典問題，可以做到O(nlogn)。具體做法是先對(duì)平面點(diǎn)進(jìn)行三角剖分，時(shí)間復(fù)雜度是O(nlogn)，三角剖分的邊就是可能的在最小生成樹的邊。因?yàn)槭瞧矫鎴D，所以有O(n)條邊，在其上應(yīng)用 Kruscal 算法即可。
  
    閱讀全文
  posted @ 2007-09-28 20:17 Felicia 閱讀(785) | 評(píng)論 (0)  編輯
• 漫談扭結(jié)      摘要: 漫談扭結(jié)
  
    閱讀全文
  posted @ 2007-09-27 17:26 Felicia 閱讀(1853) | 評(píng)論 (2)  編輯
• [計(jì)算幾何]pku1673      摘要: 此問題可轉(zhuǎn)化為求三角形垂心。我的做法是設(shè)垂心坐標(biāo)為(x, y)，然后利用垂直關(guān)系解方程。
  
    閱讀全文
  posted @ 2007-09-27 17:18 Felicia 閱讀(660) | 評(píng)論 (1)  編輯
• Ubuntu 6.10 @ Dell XPS M1210 安裝手記      摘要: Ubuntu 6.10 @ Dell XPS M1210 安裝手記
  
    閱讀全文
  posted @ 2007-09-27 15:21 Felicia 閱讀(673) | 評(píng)論 (0)  編輯
• [轉(zhuǎn)載]好友的一首小詩(shī)      摘要: 一首小詩(shī)……
  
    閱讀全文
  posted @ 2007-09-27 15:06 Felicia 閱讀(199) | 評(píng)論 (0)  編輯
• [計(jì)算幾何]平面點(diǎn)的曼哈頓最小生成樹      摘要: 平面點(diǎn)的曼哈頓最小生成樹
  
    閱讀全文
  posted @ 2007-09-27 14:48 Felicia 閱讀(1273) | 評(píng)論 (0)  編輯
• [計(jì)算幾何]pku1624      摘要: 簡(jiǎn)單計(jì)算幾何，我的做法是列出所有可能的切法（一共18種），求最優(yōu)值。
  
    閱讀全文
  posted @ 2007-09-26 20:46 Felicia 閱讀(597) | 評(píng)論 (1)  編輯
• [計(jì)算幾何]pku1408      摘要: 構(gòu)造所有的線段，然后枚舉每對(duì)水平－豎直線段，求交點(diǎn)，然后計(jì)算四邊形面積，求最大值。
  
    閱讀全文
  posted @ 2007-09-25 21:59 Felicia 閱讀(626) | 評(píng)論 (0)  編輯
• [動(dòng)態(tài)規(guī)劃]pku3133      摘要: 強(qiáng)烈推薦此題！
  狀態(tài)壓縮DP的好題！
  分析見內(nèi)
  
    閱讀全文
  posted @ 2007-09-24 21:12 Felicia 閱讀(1151) | 評(píng)論 (4)  編輯
• [計(jì)算幾何]pku3384      摘要: 強(qiáng)烈推薦此題。半平面交算法的一個(gè)應(yīng)用。
  具體做法是，把多邊形的每條邊向內(nèi)平移r單位長(zhǎng)度，用這些線段所在直線和原多邊形作半平面交，得到的區(qū)域就是半徑為r的圓放入多邊形的可行域。可以證明這個(gè)區(qū)域一定是凸的，或者退化為一條線段，或一個(gè)點(diǎn)。那么，我們就可以在這個(gè)區(qū)域上求最遠(yuǎn)點(diǎn)對(duì)啦。
  我的做法是O(n^2)的。應(yīng)該存在O(nlogn)的做法，因?yàn)槎际峭苟噙呅危看伟肫矫娼恢挥凶疃鄡蓚€(gè)交點(diǎn)，可二分，而最后的求最遠(yuǎn)點(diǎn)對(duì)可以旋轉(zhuǎn)卡殼。比賽的時(shí)候時(shí)間少，就寫了個(gè)暴力O(n^2)的。
  
    閱讀全文
  posted @ 2007-09-23 16:19 Felicia 閱讀(794) | 評(píng)論 (0)  編輯
• [計(jì)算幾何]pku1410      摘要: 基本幾何題，判斷線段是否與矩形相交。轉(zhuǎn)化為線段在矩形內(nèi)或線段與四條邊相交。
  唯一要注意的是題目中關(guān)于左上角和右下角的定義。
  
    閱讀全文
  posted @ 2007-09-22 10:58 Felicia 閱讀(534) | 評(píng)論 (0)  編輯
• [計(jì)算幾何]pku1319      摘要: 這個(gè)題需要分情況討論。如果是grid，就能直接算，如果是skew，就一層層往上模擬著堆。最后取最大值。
  
    閱讀全文
  posted @ 2007-09-21 21:56 Felicia 閱讀(443) | 評(píng)論 (2)  編輯
• [計(jì)算幾何]兩圓求交點(diǎn)      摘要: mmd 和 cz 的智慧結(jié)晶。某次比賽的時(shí)候?qū)懙摹?
  
    閱讀全文
  posted @ 2007-09-20 18:34 Felicia 閱讀(5856) | 評(píng)論 (7)  編輯
• 太難過了      摘要: 這是胡說八道
  
    閱讀全文
  posted @ 2007-09-19 18:06 Felicia 閱讀(231) | 評(píng)論 (0)  編輯
• [計(jì)算幾何]pku1586      摘要: 超級(jí)惡心的精度題。注意讀清題意，然后直接做就行了。
  
    閱讀全文
  posted @ 2007-09-19 17:47 Felicia 閱讀(454) | 評(píng)論 (0)  編輯
• [圖論][zz]給出一個(gè)沒有偶圈的簡(jiǎn)單無向圖，求兩個(gè)頂點(diǎn)間路徑的數(shù)目      摘要: 給出一個(gè)沒有偶圈的簡(jiǎn)單無向圖，求兩個(gè)頂點(diǎn)間路徑的數(shù)目
  
    閱讀全文
  posted @ 2007-09-19 10:08 Felicia 閱讀(984) | 評(píng)論 (2)  編輯
• [計(jì)算幾何]pku2954      摘要: Pick公式的應(yīng)用。先介紹一下Pick公式：
  a = e / 2 + i - 1
  a為多邊形（頂點(diǎn)都在格點(diǎn)上）面積，e為多邊形邊上的格點(diǎn)數(shù)，i為多邊形內(nèi)部的格點(diǎn)數(shù)。
  題目給出三點(diǎn)坐標(biāo)，邊上的格點(diǎn)數(shù)可用gcd求得，剩下的事就是解方程了。
  
    閱讀全文
  posted @ 2007-09-18 21:59 Felicia 閱讀(439) | 評(píng)論 (0)  編輯
• 唔，我喜歡這首詩(shī)      摘要: 喜歡搞笑的詩(shī)的請(qǐng)進(jìn)
  
    閱讀全文
  posted @ 2007-09-17 18:39 Felicia 閱讀(179) | 評(píng)論 (0)  編輯
• [計(jì)算幾何]pku1569      摘要: 枚舉三角形，然后判斷是否其余的點(diǎn)都不在形內(nèi)，也不在邊上。時(shí)間復(fù)雜度是O(n^4)。
  
    閱讀全文
  posted @ 2007-09-16 21:19 Felicia 閱讀(365) | 評(píng)論 (0)  編輯
• [計(jì)算幾何]pku3129      摘要: 很簡(jiǎn)單的幾何題。直接硬搞即可。
  
    閱讀全文
  posted @ 2007-09-15 20:25 Felicia 閱讀(388) | 評(píng)論 (0)  編輯
• [轉(zhuǎn)]WinSock學(xué)習(xí)筆記[2]      摘要: Winsock入門
  
    閱讀全文
  posted @ 2007-09-14 22:26 Felicia 閱讀(212) | 評(píng)論 (0)  編輯
• [轉(zhuǎn)]WinSock學(xué)習(xí)筆記[1]      摘要: Winsock入門
  
    閱讀全文
  posted @ 2007-09-14 22:23 Felicia 閱讀(186) | 評(píng)論 (0)  編輯
• [計(jì)算幾何]pku一些關(guān)于多邊形的題目      摘要: 見內(nèi)
  
    閱讀全文
  posted @ 2007-09-14 22:21 Felicia 閱讀(542) | 評(píng)論 (0)  編輯
• [計(jì)算幾何]pku3130      摘要: 又是一個(gè)求多邊形的核的題。
  
    閱讀全文
  posted @ 2007-09-14 22:18 Felicia 閱讀(489) | 評(píng)論 (0)  編輯
• I Want A Wife      摘要: :)
  
    閱讀全文
  posted @ 2007-09-13 14:17 Felicia 閱讀(248) | 評(píng)論 (2)  編輯
• [計(jì)算幾何]pku2079      摘要: 先求凸包，然后再用旋轉(zhuǎn)卡殼方法求解。
  具體做法是枚舉三角形的第一個(gè)點(diǎn)i，設(shè)j = i + 1，k = j + 1。然后做以下操作：
  1.計(jì)算i，j，k構(gòu)成的三角形面積a1和i，j，k + 1構(gòu)成的三角形面積a2，如果a2 < a1，則進(jìn)行下一步，否則k++，重復(fù)此步。
  2.記錄此時(shí)的三角形面積b，如果b < preb（就是上一個(gè)j對(duì)應(yīng)的三角形面積）j++，轉(zhuǎn)第一步，否則退出。
  可以證明這個(gè)算法的復(fù)雜度為O(n2)。具體實(shí)現(xiàn)見代碼。
  
    閱讀全文
  posted @ 2007-09-13 13:40 Felicia 閱讀(862) | 評(píng)論 (0)  編輯
• [動(dòng)態(tài)規(guī)劃]pku1038      摘要: 經(jīng)典的狀態(tài)壓縮DP，《算法藝術(shù)與信息學(xué)競(jìng)賽》的例題。f[i][j]表示前i行，最后兩行狀態(tài)為二進(jìn)制數(shù)j，嵌入的最多芯片數(shù)。第i行到第i+1行用DFS進(jìn)行狀態(tài)轉(zhuǎn)移。
  由于第i+1行只和第i行有關(guān)，故可以用滾動(dòng)數(shù)組優(yōu)化。
  
    閱讀全文
  posted @ 2007-09-12 20:44 Felicia 閱讀(1556) | 評(píng)論 (3)  編輯
• [動(dòng)態(tài)規(guī)劃]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)
  
  有很多細(xì)節(jié)不好考慮，應(yīng)該是我的水平原因。最后我向updog要了數(shù)據(jù)才過的。而且代碼寫的不好。將就看一下吧。
  
    閱讀全文
  posted @ 2007-09-11 22:28 Felicia 閱讀(812) | 評(píng)論 (1)  編輯
• [計(jì)算幾何]pku1494      摘要: 其實(shí)是初等幾何題。在紙上畫一下就出來了。
  
    閱讀全文
  posted @ 2007-09-10 20:48 Felicia 閱讀(450) | 評(píng)論 (0)  編輯
• [計(jì)算幾何]pku1473      摘要: 很簡(jiǎn)單的題。直接按照題意模擬即可。
  
    閱讀全文
  posted @ 2007-09-10 16:58 Felicia 閱讀(374) | 評(píng)論 (0)  編輯
• 無敵詭異的姓名測(cè)試      摘要: 對(duì)搞笑的事情感興趣的請(qǐng)進(jìn)
  
    閱讀全文
  posted @ 2007-09-10 13:13 Felicia 閱讀(180) | 評(píng)論 (0)  編輯
• [計(jì)算幾何]pku1039      摘要: 具體算法在《算法藝術(shù)與信息學(xué)競(jìng)賽》里有講。
  
    閱讀全文
  posted @ 2007-09-09 22:01 Felicia 閱讀(771) | 評(píng)論 (0)  編輯
• [計(jì)算幾何]pku1133      摘要: 這個(gè)題目我用的是枚舉。具體做法是，對(duì)于每個(gè)星座，把它的第1個(gè)點(diǎn)放在星圖的第i個(gè)點(diǎn)上，第2個(gè)點(diǎn)放在星圖的第j個(gè)點(diǎn)上（i != j），保持形狀不變，移動(dòng)這個(gè)星座中的其他點(diǎn)，看看這些點(diǎn)是否都和星圖中的點(diǎn)重合。若滿足條件，則找到一個(gè)匹配。如此得到星座c對(duì)星圖的匹配數(shù)a。再得到星座c對(duì)它本身的匹配數(shù)b。那么星座c的出現(xiàn)次數(shù)就是 a / b。對(duì)于只有一個(gè)星星的星座，要特殊考慮一下。至于找出最亮星座，方法很簡(jiǎn)單：每次記錄亮度值，發(fā)現(xiàn)更亮的就更新解。
  
  p.s. 我一開始是用STL的complex做的，超時(shí)。后來改成向量做了。
  
    閱讀全文
  posted @ 2007-09-08 22:42 Felicia 閱讀(521) | 評(píng)論 (1)  編輯
• [計(jì)算幾何]pku1092      摘要: 題目要求統(tǒng)計(jì)一個(gè)平面圖中所有邊數(shù)為k的面的個(gè)數(shù)。應(yīng)該是個(gè)經(jīng)典問題。說說我的算法吧。
  枚舉每條邊，做以下的基本步驟。
  
  基本步驟：以這條邊作起始邊，不斷地找下一條“最左轉(zhuǎn)”的邊，并且標(biāo)記每個(gè)點(diǎn)的訪問次數(shù)，直到某個(gè)點(diǎn)第3次被訪問為止。
  經(jīng)過這個(gè)步驟之后，得到一個(gè)頂點(diǎn)序列。容易知道，當(dāng)且僅當(dāng)這個(gè)頂點(diǎn)序列是2-重復(fù)（就是形如12341234這樣），并且是逆時(shí)針旋轉(zhuǎn)的，那么就是一個(gè)面。
  接下去我們就把所有找到的邊數(shù)為k面進(jìn)行hash去重，就得到答案啦。
  貌似我想的這個(gè)算法不夠好，如果有更好的算法，歡迎和我討論。
  
    閱讀全文
  posted @ 2007-09-07 19:37 Felicia 閱讀(654) | 評(píng)論 (0)  編輯
• 友情鏈接邀請(qǐng)
  posted @ 2007-09-07 16:15 Felicia 閱讀(1119) | 評(píng)論 (42)  編輯
• [計(jì)算幾何]pku1471      摘要: 這題勉強(qiáng)算幾何吧。我寫了個(gè)超級(jí)慢的枚舉。
  
    閱讀全文
  posted @ 2007-09-06 20:02 Felicia 閱讀(427) | 評(píng)論 (0)  編輯
• [計(jì)算幾何]pku1434      摘要: 簡(jiǎn)單幾何題，但是容易WA。做法是二分水面高度，然后看看這個(gè)高度對(duì)應(yīng)多少水。
  
    閱讀全文
  posted @ 2007-09-05 21:30 Felicia 閱讀(350) | 評(píng)論 (0)  編輯
• 到武漢啦！      摘要: 對(duì)我的悲慘人生感興趣的請(qǐng)進(jìn)
  
    閱讀全文
  posted @ 2007-09-05 20:25 Felicia 閱讀(224) | 評(píng)論 (0)  編輯
• [動(dòng)態(tài)規(guī)劃]pku1170      摘要: 呼~今天去學(xué)校啦！早上7點(diǎn)起床寫題，挑了個(gè)簡(jiǎn)單題寫 ^_^
  這個(gè)是IOI95的DP題。用一個(gè)b位的6進(jìn)制數(shù)i表示狀態(tài)。這個(gè)6進(jìn)制數(shù)的每一位分別表示相應(yīng)物品的數(shù)量。f[i]表示狀態(tài)i下的最小花費(fèi)。同樣也可以用6進(jìn)制數(shù)j表示優(yōu)惠。那么，f[i]就能轉(zhuǎn)移到f[i - j]，如果優(yōu)惠j可用的話。代價(jià)是使用優(yōu)惠j時(shí)減少的花費(fèi)。最后的答案就是min(f[i])，0 <= i <= start（start是初始狀態(tài)）。
  
    閱讀全文
  posted @ 2007-09-04 08:37 Felicia 閱讀(678) | 評(píng)論 (0)  編輯
• [動(dòng)態(tài)規(guī)劃]pku1160      摘要: 先預(yù)處理，把第i個(gè)村子到第j個(gè)村子中，建一個(gè)郵局的最小代價(jià)算出來，存在min_cost[i][j]里。
  接下來就可以DP。設(shè)f[i][j]為前i個(gè)郵局，建在前j個(gè)村子的最小代價(jià)。那么f[i][j]可以轉(zhuǎn)移到f[i + 1][j + k]，(1 <= k 且 j + k <= n)，代價(jià)是min_cost[j + 1][j + k]。
  
    閱讀全文
  posted @ 2007-09-03 22:44 Felicia 閱讀(1504) | 評(píng)論 (3)  編輯
• [圖論]pku1125      摘要: 簡(jiǎn)單題。很早以前做的。貼一下凌亂的代碼。
  
    閱讀全文
  posted @ 2007-09-02 20:09 Felicia 閱讀(500) | 評(píng)論 (2)  編輯
• [動(dòng)態(tài)規(guī)劃]pku1088      摘要: 簡(jiǎn)單的記憶化搜索。很早以前做的，代碼風(fēng)格很亂。將就一下啦。
  
    閱讀全文
  posted @ 2007-09-02 20:02 Felicia 閱讀(918) | 評(píng)論 (5)  編輯
• [動(dòng)態(tài)規(guī)劃]pku1737      摘要: 樓爺?shù)念}。遞推。f[n]表示n個(gè)結(jié)點(diǎn)的連通圖個(gè)數(shù)，則有遞推公式：
  
  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
  }
  
  因?yàn)閿?shù)據(jù)較多，所以預(yù)先算出f[1] -- f[50]，再輸出。要用高精度。我用了標(biāo)程。
  
    閱讀全文
  posted @ 2007-09-02 13:53 Felicia 閱讀(769) | 評(píng)論 (6)  編輯
• [動(dòng)態(tài)規(guī)劃]pku1946      摘要: 首先明確一點(diǎn)：最優(yōu)解必為奶牛1..n-1輪流領(lǐng)跑，奶牛n撞線。且跑了x圈后，未領(lǐng)跑過的奶牛都耗費(fèi)了x的體力。
  設(shè)f[i][j][k]表示前i-1頭奶牛已領(lǐng)跑，現(xiàn)在由第i頭奶牛領(lǐng)跑，一共跑了j圈，奶牛i耗費(fèi)了k的體力。
  則f[i][j][k]可以轉(zhuǎn)移到f[i][j + p][k + p^2]（耗費(fèi)1分鐘，奶牛i以p圈/分鐘的速度繼續(xù)領(lǐng)跑），也可轉(zhuǎn)移到f[i + 1][j][j]（換成奶牛i + 1領(lǐng)跑，不耗費(fèi)時(shí)間）。
  時(shí)間復(fù)雜度為O(nde^2.5)。
  
    閱讀全文
  posted @ 2007-09-01 11:42 Felicia 閱讀(485) | 評(píng)論 (1)  編輯