關鍵字: ACM ICPC 珠海賽 金山杯 2009 BNUEP int_ijk
注：這是高手的心得，高手就是高手。。。 學弟怎么能不MB+YM，收藏之
===================================================================================================
這是有史以來最神奇的一次比賽.
這種神奇的跡象從一大早就開始持續...去科干院要坐車一個半小時, 和去一趟廣州差不多的時間. 10點鐘開始比賽, 我們學校8支隊伍7點半悠閑地坐著大巴過去了. 按照北理工的教練的說法就是, 你們學校也太不重視比賽了, 怎么都不住那邊. 不過也的確, 要是這次來得及的話, 那么省賽的時候一大早出發應該也來得及>_<
然后一個神奇的地方是, 比賽一共分了6個機房. 而且機器良莠不齊, 差距及其巨大. (據說把機房分成了三個等級,上等房,中等房和下等房, 每個學校按比例分配...)然后我們隊自從用了int_ijk隊名之后, 每次比賽都是在角落里. 這次也不例外, 被分配到了最后排的左下角, 縱觀全場.
--------按照慣例 下面是流水賬----------------
先列舉一下題目
Apple Tree: 線性DP. Banana Game: 博弈. Cross Words: 字符串查找.
Download Again: 簡單題. Encrypted SMS: 中序遍歷. Football Match: 概率.
General Problem: 三次方程求根. Horse in Chinese Chess: 廣搜.
Insect World: 模擬. Jack's Lost Lists: 枚舉.
開始分頭看題, 尚鵬ABC, 我DEF,許翰中GHIJ. 大約20分鐘的時候交流了一下, 尚鵬說B是博弈, 之前做過的原題. 我看了DE, 覺得都是簡單題, 不過還感覺應該不是最簡單的題目,所以沒有馬上上去寫(后來發現整套題目都是這種難度,沒有很大的區分度). 過了一會兒我先去寫D, 許翰中說不用模擬, 直接用文件總大小除以帶寬就好了. 于是很快寫完, 一次AC了.
尚鵬說B做過, 然后很神奇的拿出一篇論文, 上面有一個終極公式. 敲上去瞬間過掉了. 我倒比較擔心的是怕我們學校的其他幾個隊伍跟風的話肯能被卡住.
然后是許翰中上去寫了A題, 尚鵬幫忙看了一下DP公式. 好像怎么錯了一次, 然后就AC掉了.
這個時候大概是1小時多一點. 我換上去寫C題. 這個題題意挺奇怪, 我們交流了好幾次才確認了題意. 看了一下數據量不大, 也有好幾個隊過了, 應該不用字典樹, 二分查找就行. 敲完代碼也一次AC了.
E題其實按照題目所說的方式遞歸進去, 前序輸出就好了. 許翰中上去敲, 我幫忙看代碼, 貌似也是一次AC的.
這個時候尚鵬弄完F題, 用最直接求概率的方法就好了, 打了個表, 也一次AC的.
看了一下排名, 發現I題挺多人過, 于是我看了一下, 發現直接模擬就可以. 找最近點線性掃描也不會超時. 于是也很快AC了.
現在還剩三個題, G,H,J. 大約還有兩個半小時吧. 時間很充裕. 但是華農那個隊已經9題了...我們排在第二, 已經覺得趕不上了, 于是心理上已經做好了最后排在第二的準備...
許翰中看完J題就驚呼--原題!于是拿出黑書,我一看果然..>_< 這個時侯尚鵬上去敲G題, 我在旁邊幫忙看J題, 也準備著些H題. 敲完發現有點問題, 于是打印下來. 換許翰中上去寫J, 用黑書上的n^3的算法. 提交了, 發現不對... 于是換我上去些H. 但是我又有點擔心說這個時候開三個題是不是有點冒險, 然后他倆說沒事, 大不了回去寫檢討. 我說好, 于是就去敲H. 敲完發現也不對..于是又換尚鵬繼續改G. 好像是代碼里面某個地方敲錯了, 改好了提交AC了.
現在剩兩個題, 代碼都差不多寫好了, 還有一個半小時不到吧. 我和許翰中輪流糾結H和J. 許翰中錯了好幾次, 后來覺得是不是可能枚舉出來的解會不合法, 于是加強了對解得限制, 然后AC了.
還有一小時, 還剩我這個題, 應該很快就能AC. 第一次提交犯了低級錯誤, 調試的時候把枚舉的步數改小了, 提交忘了該回來. 結果得到一個TLE. 這個TLE嚇了我一跳, 反復算了復雜度不可能超時啊. 估計是裁判判錯了, 害我好幾分鐘都沒敢提交. 改了兩個地方之后提交還是WA. 檢查了好久才發現, 判斷重復的時候,我是判斷記錄步數的數組值是否為0, 這里導致了BUG, 因為計算的時候有模2008, 求了模之后原來不為0的也可能為0了... 汗.改了這里提交AC了.
這個時候, 還有大約半小時比賽結束, 教練在遙遠的某個地方收到一條裁判發來的短信"你們圓滿了"...汗.
-----------------------------------------------
第一次比賽的時候做完所有的題目, 感覺題目沒有拉出梯度來. 簡單的不夠簡單, 難題也不夠難. 而且我們驚呼了好幾次--原題...(不過也情有可原, 出題者的時間實在太倉促).到最后的時候時候看排名發現華農那隊依然9題..我們等比賽結束的那段時間就一直在算罰時...
最后結果是, 我們學校1個一等獎, 2個二等獎, 3個三等獎. 還有兩個08級的隊伍缺乏經驗可惜沒能拿獎.
總的來說這次比賽運氣的成分占了很大因數, 遇到好幾個原題, 而且這么多次比賽第一次用上了帶來的資料. 這次我們隊正確率還算可以, 不用寫檢討, 不過我最后一個題還是犯了一個低級錯誤和一個高級錯誤, 有點過意不去...