10 2007 檔案

• 2007南京賽區(qū)總結(jié) by mmd      摘要: 這是我們隊(duì)的mmd寫的總結(jié)，發(fā)布在珞珈山水bbs上，轉(zhuǎn)載過來。
  
    閱讀全文
  posted @ 2007-10-28 23:36 Felicia 閱讀(2446) | 評(píng)論 (19)  編輯
• The 2007 ACM Asia Programming Contest - Nanjing Final Score Board      摘要: 我們隊(duì)第6,得到WHU歷史上第一枚金牌,這里是Final Score Board
  
    閱讀全文
  posted @ 2007-10-28 23:33 Felicia 閱讀(952) | 評(píng)論 (2)  編輯
• Wish myself      摘要: 臨行祝福
  
    閱讀全文
  posted @ 2007-10-25 10:03 Felicia 閱讀(322) | 評(píng)論 (2)  編輯
• [TopCoder]SRM373 Div1      摘要: [TopCoder]SRM373 Div1
  
    閱讀全文
  posted @ 2007-10-24 14:02 Felicia 閱讀(590) | 評(píng)論 (2)  編輯
• [計(jì)算幾何]pku3293      摘要: 先按規(guī)則連。規(guī)則是隔一段連一個(gè)。比如一條直線上有6個(gè)點(diǎn)，就1-2，3-4，5-6，這么連。如果只有奇數(shù)個(gè)點(diǎn)，就不行。然后再判有沒有洞。
  方法是任選一個(gè)點(diǎn)，走一圈，看看是否遍歷所有的點(diǎn)。
  
    閱讀全文
  posted @ 2007-10-22 14:06 Felicia 閱讀(623) | 評(píng)論 (1)  編輯
• [計(jì)算幾何]pku3429      摘要: 直接按照題目意思模擬即可。關(guān)鍵是需要實(shí)現(xiàn)有理數(shù)運(yùn)算。我的方法是重載運(yùn)算符。
  
    閱讀全文
  posted @ 2007-10-22 13:50 Felicia 閱讀(616) | 評(píng)論 (3)  編輯
• [計(jì)算幾何]pku3424      摘要: 先確定窗口左上角可能出現(xiàn)的區(qū)域，方法是對(duì)每個(gè)點(diǎn)確定這樣一個(gè)區(qū)域，然后求交。接下來枚舉窗口左上角，計(jì)算密碼序列，插入一個(gè)set中。最后按字典序輸出這個(gè)set。
  
    閱讀全文
  posted @ 2007-10-22 13:48 Felicia 閱讀(469) | 評(píng)論 (0)  編輯
• [TopCoder]SRM372 Div1      摘要: [TopCoder]SRM372 Div1
  
    閱讀全文
  posted @ 2007-10-21 18:34 Felicia 閱讀(511) | 評(píng)論 (0)  編輯
• ACM/ICPC 2007北京賽區(qū)預(yù)選賽結(jié)果      摘要: ACM/ICPC 2007北京賽區(qū)預(yù)選賽結(jié)果
  
    閱讀全文
  posted @ 2007-10-19 20:28 Felicia 閱讀(1771) | 評(píng)論 (1)  編輯
• [動(dòng)態(tài)規(guī)劃]O(n^2 / logn)的LCS      摘要: 上次說，LCS有O(n^2 / logn)的解法。這個(gè)解法是在字符集不大的情況下，先預(yù)處理，再用位運(yùn)算做狀態(tài)轉(zhuǎn)移。
  唐文斌曾經(jīng)翻譯過一篇論文，專門討論這個(gè)問題。
  
  下面是練習(xí)題（n = 10000 的LCS）
  http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1210
  
  和我的解答
  
    閱讀全文
  posted @ 2007-10-19 16:56 Felicia 閱讀(1383) | 評(píng)論 (5)  編輯
• [動(dòng)態(tài)規(guī)劃] pku1458 最長(zhǎng)公共子序列      摘要: 最長(zhǎng)公共子序列……想必很多人都知道吧……
  這里給出一個(gè)O(n^2)的算法，人人都會(huì)的。
  但是，我想說，我所知道的最好算法，是O(n^2 / logn)的。
  
    閱讀全文
  posted @ 2007-10-16 22:46 Felicia 閱讀(1435) | 評(píng)論 (4)  編輯
• 今天好忙啊      摘要: 忙了一天獎(jiǎng)學(xué)金的事
  
    閱讀全文
  posted @ 2007-10-15 23:46 Felicia 閱讀(340) | 評(píng)論 (1)  編輯
• [TopCoder]SRM371 Div1      摘要: [TopCoder]SRM371 Div1
  
    閱讀全文
  posted @ 2007-10-14 20:41 Felicia 閱讀(425) | 評(píng)論 (0)  編輯
• 今天很不爽      摘要: 三維凸包郁悶我
  
    閱讀全文
  posted @ 2007-10-13 17:44 Felicia 閱讀(417) | 評(píng)論 (4)  編輯
• [動(dòng)態(tài)規(guī)劃]pku1080      摘要: 很簡(jiǎn)單的DP，也是很基礎(chǔ)的DP。做法就不說啦：）
  
    閱讀全文
  posted @ 2007-10-12 22:25 Felicia 閱讀(1127) | 評(píng)論 (1)  編輯
• 百度之星2007紀(jì)念      摘要: For my A*Star 2007
  
    閱讀全文
  posted @ 2007-10-11 19:47 Felicia 閱讀(454) | 評(píng)論 (4)  編輯
• 第32屆ACM-ICPC亞洲區(qū)長(zhǎng)春賽區(qū)預(yù)選賽 網(wǎng)絡(luò)賽選拔結(jié)果      摘要: 第32屆ACM-ICPC亞洲區(qū)長(zhǎng)春賽區(qū)預(yù)選賽 網(wǎng)絡(luò)賽選拔結(jié)果
  
    閱讀全文
  posted @ 2007-10-10 09:38 Felicia 閱讀(1369) | 評(píng)論 (1)  編輯
• [計(jì)算幾何]pku1379      摘要: 平面點(diǎn)的三角剖分應(yīng)用。對(duì)輸入點(diǎn)集進(jìn)行三角剖分，求得對(duì)偶圖Voronoi圖，Voronoi圖的結(jié)點(diǎn)以及邊與矩形的邊的交點(diǎn)就是可疑點(diǎn)。枚舉可疑點(diǎn)，計(jì)算最優(yōu)值就是答案。
  
    閱讀全文
  posted @ 2007-10-10 09:31 Felicia 閱讀(1359) | 評(píng)論 (4)  編輯
• [TopCoder]SRM370 Div2      摘要: SRM370 Div2
  
    閱讀全文
  posted @ 2007-10-10 09:07 Felicia 閱讀(552) | 評(píng)論 (2)  編輯
• [動(dòng)態(tài)規(guī)劃]pku1338      摘要: 非常經(jīng)典的遞推計(jì)算。基本思想是設(shè)3個(gè)指針，分別表示3個(gè)素?cái)?shù)乘到哪了，然后通過比較3個(gè)指針位置的遞推結(jié)果來確定下一個(gè)數(shù)是什么。
  具體實(shí)現(xiàn)見代碼。
  
    閱讀全文
  posted @ 2007-10-09 21:53 Felicia 閱讀(828) | 評(píng)論 (1)  編輯
• [動(dòng)態(tài)規(guī)劃]pku3420      摘要: 經(jīng)典題型。如果列數(shù)較少，就能用我們熟知的狀態(tài)壓縮DP解決。但現(xiàn)在列數(shù)有2^31。考慮到相鄰兩列之間狀態(tài)轉(zhuǎn)移規(guī)則是相同的，我們可以用矩陣表示這種轉(zhuǎn)移規(guī)則，而最后的結(jié)果就是求這個(gè)轉(zhuǎn)移矩陣的n次冪的左上角元素。
  
    閱讀全文
  posted @ 2007-10-08 09:19 Felicia 閱讀(1126) | 評(píng)論 (0)  編輯
• [動(dòng)態(tài)規(guī)劃]pku1191      摘要: 不錯(cuò)的DP題。狀態(tài)f[i][x1][y1][x2][y2]表示要把(x1,y1) -- (x2, y2) 分割成i塊所得到的最小平方和（平方和指的是每塊矩形的和的平方和）。然后根據(jù)水平和豎直切割進(jìn)行狀態(tài)轉(zhuǎn)移。這樣計(jì)算出f[n][1][1][8][8]得到整個(gè)棋盤分割成n塊得到的最小平方和，然后代入均方差公式算得結(jié)果。
  
    閱讀全文
  posted @ 2007-10-08 09:12 Felicia 閱讀(819) | 評(píng)論 (1)  編輯
• [計(jì)算幾何]兩個(gè)凸多邊形的交      摘要: 兩個(gè)凸多邊形的交
  
    閱讀全文
  posted @ 2007-10-07 10:27 Felicia 閱讀(1761) | 評(píng)論 (2)  編輯
• [圖論]pku3417      摘要: 我的做法是，對(duì)于每條新邊，記錄樹中與之對(duì)應(yīng)的路徑。然后對(duì)于每條樹邊，統(tǒng)計(jì)被對(duì)應(yīng)的次數(shù)。最后記錄每個(gè)點(diǎn)到樹根的路徑上，有多少個(gè)1（設(shè)為q[i]）。對(duì)于新邊(x,y)，它對(duì)答案的貢獻(xiàn)就是q[x] + q[y] - 2q[lca(x,y)]。除了這些，答案還應(yīng)加上樹中0邊的數(shù)量 * m。
  
    閱讀全文
  posted @ 2007-10-06 20:53 Felicia 閱讀(521) | 評(píng)論 (0)  編輯
• [動(dòng)態(tài)規(guī)劃]pku1179      摘要: 經(jīng)典的DP，把環(huán)斷開，f[i][j][0]記錄i到j(luò)的最小值，f[i][j][1]記錄最大值，然后遞推計(jì)算。記錄最小值是因?yàn)閮蓚€(gè)負(fù)數(shù)乘起來可能得到一個(gè)大的正數(shù)。
  
    閱讀全文
  posted @ 2007-10-05 16:47 Felicia 閱讀(630) | 評(píng)論 (0)  編輯
• [動(dòng)態(tài)規(guī)劃]pku1189      摘要: 概率+DP，比較經(jīng)典的題。按照遞推的方式計(jì)算概率。
  
    閱讀全文
  posted @ 2007-10-04 20:47 Felicia 閱讀(815) | 評(píng)論 (4)  編輯
• 第32屆ACM/ICPC國際大學(xué)生程序設(shè)計(jì)競(jìng)賽 亞洲區(qū)南京預(yù)選賽 選拔結(jié)果      摘要: 詳情見內(nèi)
  
    閱讀全文
  posted @ 2007-10-03 18:45 Felicia 閱讀(496) | 評(píng)論 (0)  編輯
• [計(jì)算幾何]pku3407      摘要: 簡(jiǎn)單的幾何題，先把經(jīng)緯度換算成球面坐標(biāo)，再把球面坐標(biāo)換算成直角坐標(biāo)，然后求夾角，乘半徑得到球面距離
  
    閱讀全文
  posted @ 2007-10-02 17:55 Felicia 閱讀(639) | 評(píng)論 (1)  編輯
• [計(jì)算幾何]pku3410      摘要: 我的做法是，枚舉第一個(gè)多邊形的第i條邊和第二個(gè)多邊形的第j條邊重合，然后從這條重合的邊開始，盡可能的向后擴(kuò)展重合邊，然后判斷剩下的多邊形是否是凸多邊形。
  比賽的時(shí)候，我在某個(gè)地方忘記對(duì)多邊形點(diǎn)數(shù)求模，導(dǎo)致wa了很久，一直到比賽結(jié)束后才AC。以此為鑒！
  
    閱讀全文
  posted @ 2007-10-02 17:52 Felicia 閱讀(632) | 評(píng)論 (0)  編輯
• 奇跡 boa      摘要: 聽著很有感覺：）于是找了歌詞翻譯
  
    閱讀全文
  posted @ 2007-10-01 12:27 Felicia 閱讀(250) | 評(píng)論 (0)  編輯