關(guān)鍵字: ACM ICPC 珠海賽 金山杯 2009 BNUEP int_ijk

注：這是高手的心得，高手就是高手。。。 學(xué)弟怎么能不MB+YM，收藏之

===================================================================================================

這是有史以來最神奇的一次比賽.

這種神奇的跡象從一大早就開始持續(xù)...去科干院要坐車一個(gè)半小時(shí), 和去一趟廣州差不多的時(shí)間. 10點(diǎn)鐘開始比賽, 我們學(xué)校8支隊(duì)伍7點(diǎn)半悠閑地坐著大巴過去了. 按照北理工的教練的說法就是, 你們學(xué)校也太不重視比賽了, 怎么都不住那邊. 不過也的確, 要是這次來得及的話, 那么省賽的時(shí)候一大早出發(fā)應(yīng)該也來得及>_<

然后一個(gè)神奇的地方是, 比賽一共分了6個(gè)機(jī)房. 而且機(jī)器良莠不齊, 差距及其巨大. (據(jù)說把機(jī)房分成了三個(gè)等級(jí),上等房,中等房和下等房, 每個(gè)學(xué)校按比例分配...)然后我們隊(duì)自從用了int_ijk隊(duì)名之后, 每次比賽都是在角落里. 這次也不例外, 被分配到了最后排的左下角, 縱觀全場(chǎng).

--------按照慣例 下面是流水賬----------------

先列舉一下題目

Apple Tree: 線性DP. Banana Game: 博弈. Cross Words: 字符串查找.

Download Again: 簡(jiǎn)單題. Encrypted SMS: 中序遍歷. Football Match: 概率.

General Problem: 三次方程求根. Horse in Chinese Chess: 廣搜.

Insect World: 模擬. Jack's Lost Lists: 枚舉.

開始分頭看題, 尚鵬ABC, 我DEF,許翰中GHIJ. 大約20分鐘的時(shí)候交流了一下, 尚鵬說B是博弈, 之前做過的原題. 我看了DE, 覺得都是簡(jiǎn)單題, 不過還感覺應(yīng)該不是最簡(jiǎn)單的題目,所以沒有馬上上去寫(后來發(fā)現(xiàn)整套題目都是這種難度,沒有很大的區(qū)分度). 過了一會(huì)兒我先去寫D, 許翰中說不用模擬, 直接用文件總大小除以帶寬就好了. 于是很快寫完, 一次AC了.

尚鵬說B做過, 然后很神奇的拿出一篇論文, 上面有一個(gè)終極公式. 敲上去瞬間過掉了. 我倒比較擔(dān)心的是怕我們學(xué)校的其他幾個(gè)隊(duì)伍跟風(fēng)的話肯能被卡住.

然后是許翰中上去寫了A題, 尚鵬幫忙看了一下DP公式. 好像怎么錯(cuò)了一次, 然后就AC掉了.

這個(gè)時(shí)候大概是1小時(shí)多一點(diǎn). 我換上去寫C題. 這個(gè)題題意挺奇怪, 我們交流了好幾次才確認(rèn)了題意. 看了一下數(shù)據(jù)量不大, 也有好幾個(gè)隊(duì)過了, 應(yīng)該不用字典樹, 二分查找就行. 敲完代碼也一次AC了.

E題其實(shí)按照題目所說的方式遞歸進(jìn)去, 前序輸出就好了. 許翰中上去敲, 我?guī)兔创a, 貌似也是一次AC的.

這個(gè)時(shí)候尚鵬弄完F題, 用最直接求概率的方法就好了, 打了個(gè)表, 也一次AC的.

看了一下排名, 發(fā)現(xiàn)I題挺多人過, 于是我看了一下, 發(fā)現(xiàn)直接模擬就可以. 找最近點(diǎn)線性掃描也不會(huì)超時(shí). 于是也很快AC了.

現(xiàn)在還剩三個(gè)題, G,H,J. 大約還有兩個(gè)半小時(shí)吧. 時(shí)間很充裕. 但是華農(nóng)那個(gè)隊(duì)已經(jīng)9題了...我們排在第二, 已經(jīng)覺得趕不上了, 于是心理上已經(jīng)做好了最后排在第二的準(zhǔn)備...

許翰中看完J題就驚呼--原題!于是拿出黑書,我一看果然..>_< 這個(gè)時(shí)侯尚鵬上去敲G題, 我在旁邊幫忙看J題, 也準(zhǔn)備著些H題. 敲完發(fā)現(xiàn)有點(diǎn)問題, 于是打印下來. 換許翰中上去寫J, 用黑書上的n^3的算法. 提交了, 發(fā)現(xiàn)不對(duì)... 于是換我上去些H. 但是我又有點(diǎn)擔(dān)心說這個(gè)時(shí)候開三個(gè)題是不是有點(diǎn)冒險(xiǎn), 然后他倆說沒事, 大不了回去寫檢討. 我說好, 于是就去敲H. 敲完發(fā)現(xiàn)也不對(duì)..于是又換尚鵬繼續(xù)改G. 好像是代碼里面某個(gè)地方敲錯(cuò)了, 改好了提交AC了.

現(xiàn)在剩兩個(gè)題, 代碼都差不多寫好了, 還有一個(gè)半小時(shí)不到吧. 我和許翰中輪流糾結(jié)H和J. 許翰中錯(cuò)了好幾次, 后來覺得是不是可能枚舉出來的解會(huì)不合法, 于是加強(qiáng)了對(duì)解得限制, 然后AC了.

還有一小時(shí), 還剩我這個(gè)題, 應(yīng)該很快就能AC. 第一次提交犯了低級(jí)錯(cuò)誤, 調(diào)試的時(shí)候把枚舉的步數(shù)改小了, 提交忘了該回來. 結(jié)果得到一個(gè)TLE. 這個(gè)TLE嚇了我一跳, 反復(fù)算了復(fù)雜度不可能超時(shí)啊. 估計(jì)是裁判判錯(cuò)了, 害我好幾分鐘都沒敢提交. 改了兩個(gè)地方之后提交還是WA. 檢查了好久才發(fā)現(xiàn), 判斷重復(fù)的時(shí)候,我是判斷記錄步數(shù)的數(shù)組值是否為0, 這里導(dǎo)致了BUG, 因?yàn)橛?jì)算的時(shí)候有模2008, 求了模之后原來不為0的也可能為0了... 汗.改了這里提交AC了.

這個(gè)時(shí)候, 還有大約半小時(shí)比賽結(jié)束, 教練在遙遠(yuǎn)的某個(gè)地方收到一條裁判發(fā)來的短信"你們圓滿了"...汗.

-----------------------------------------------

第一次比賽的時(shí)候做完所有的題目, 感覺題目沒有拉出梯度來. 簡(jiǎn)單的不夠簡(jiǎn)單, 難題也不夠難. 而且我們驚呼了好幾次--原題...(不過也情有可原, 出題者的時(shí)間實(shí)在太倉促).到最后的時(shí)候時(shí)候看排名發(fā)現(xiàn)華農(nóng)那隊(duì)依然9題..我們等比賽結(jié)束的那段時(shí)間就一直在算罰時(shí)...

最后結(jié)果是, 我們學(xué)校1個(gè)一等獎(jiǎng), 2個(gè)二等獎(jiǎng), 3個(gè)三等獎(jiǎng). 還有兩個(gè)08級(jí)的隊(duì)伍缺乏經(jīng)驗(yàn)可惜沒能拿獎(jiǎng).

總的來說這次比賽運(yùn)氣的成分占了很大因數(shù), 遇到好幾個(gè)原題, 而且這么多次比賽第一次用上了帶來的資料. 這次我們隊(duì)正確率還算可以, 不用寫檢討, 不過我最后一個(gè)題還是犯了一個(gè)低級(jí)錯(cuò)誤和一個(gè)高級(jí)錯(cuò)誤, 有點(diǎn)過意不去...