10 2007 檔案

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