Posted on 2007-04-02 00:04
oyjpart 閱讀(1630)
評論(9) 編輯 收藏 引用 所屬分類:
ACM/ICPC或其他比賽
4月1日 校賽初賽開場，對我而言，這是人生中第一次ACM現(xiàn)場賽 總算沒有丟師傅，大哥的臉，呵呵~~
序幕：
3.31 TopCoder TCO大賽 預(yù)選賽第二場 說起來很不好意思的就是第一場預(yù)選賽竟讓沒有通過。。第二個500分的題目害怕枚舉算法超時，采用分類計算，結(jié)果代碼敲得很糟糕，導(dǎo)致最后分數(shù)只有第一題的分 盡管在challenge環(huán)節(jié)中拿到寶貴的50分 可是還是沒拿到復(fù)賽的入場券 昨天晚上第二次預(yù)選 終于正常一點發(fā)揮 無驚無險的進入復(fù)賽 看來要在TCO中加加油了 呵呵
4.1日早晨 昨天晚上3點多鐘TCO比賽才結(jié)束 于是打算第二天早上睡大覺 然后下午就有精神去比賽了 誰知道早上8點就醒了 于是就開始起來想想下午的比賽 當時想出一個很惡毒的計劃 哈哈 為自己做出了如此偉大的決定而興奮不已 （就是我準備比賽的時候從后面做起 等別人都把前面選作了 我就跟著做前面的題目 這樣就省去了選題目的時間） （后來才知道只是一大敗筆 因為題目難度居然是前面要簡單~~)
吃過飯突然接到郭老師一通電話 告訴我說四號院機房下午不開門。。我暈 趕緊抓上ASP趕到本部銀河機房去比賽 時間很充裕 于是我們之前又去實驗室拜訪了一下大哥，小川，雯姐等幾位大牛 然后奔赴機房~~
比賽正式開始：（比賽總時間4個小時 采用個人賽的形式）
比賽一開始我就看H題 一看 雖然是自己喜歡的圖論題 但初看去可能是樹形動態(tài)規(guī)劃 先放放 G題吧 數(shù)學題 看上去很眼熟 但是先不亂動數(shù)學題 看F題 Bessie 一看就是一個典型的Dijkstra() 于是開始狂敲代碼 大概10來分鐘的時候提交了第一個題目 結(jié)果返回 Wrong Answer 郁悶 一想咋Dijk都寫錯啊 翻翻standing 一看A題已經(jīng)10多20人過了 faint！A題啥子題？趕緊做了它！大概意思就是問x的哪一個倍數(shù)所有位為1？ 一個取余*10 的循環(huán)就可以輕松解決 2分鐘后代碼提交AC 接著開始看E題 看了看 是個廣搜的題目 準備寫 突然發(fā)現(xiàn)排名里面第一名居然已經(jīng)3題了！頓時大喊失策失策！放下E題 開始追逐第一名的步伐！
這時候我發(fā)現(xiàn)我的排名還是超級低 心想這下就丟臉啦~~ 于是開始認真做 今天題目似乎特別難理解 那個Land & Sea的題目讓我總是想起TopCoder里面一道變態(tài)的編程題 按照這種理解寫了個復(fù)雜程序提交錯誤之后 看了N久后來才明白原來就是FLOODFILL 一頓亂敲 順利通過 接著一看B題成了大家痛宰的題 我也來試試 稍微想了想 不久也得以順利通過 接著后來又把那道E題廣搜拿下 D題的動態(tài)規(guī)劃 很快的寫完之后很快的拿到WRONG ANSWER 郁悶了 由于在之前GHF幾道題目和一些題意理解上浪費了些時間 雖然在1個半小時的時候4題AC 但是排名在5，6左右 看來還要努力！這個時候 我沒有在那道動態(tài)規(guī)劃上面糾纏 而是打開了最先寫的F題 仔細讀題后發(fā)現(xiàn)原來同2點之間可能有2條邊，也就是通常我們說的重邊 加上一個小小的修改 順利AC 既然現(xiàn)在改成了從前往后做題的順序 那么就繼續(xù)做G題！一看題目的意思大概是求a^b的約數(shù)個數(shù) 其中a在1-2147483647之間 b在1-5之間 做法就是先求出1-65535之間的質(zhì)數(shù) 我求了一下大概23000多個 然后對a進行因式分解 在乘上b 根據(jù)二項式定理 約數(shù)的個數(shù)就是各個因數(shù)的質(zhì)數(shù)+1的成績 （即每個因數(shù)取0-k個這些可能）同時要注意一些細節(jié) 1.有些數(shù)的因數(shù)要超過65536 要分開處理 2.對于0的任意次方輸出0個約數(shù) 但是0的0次方要輸出1 因為0的0次方=1 這個時候終于6題 比賽還有1個小時20分鐘 排名升到了第二 后面幾個人都5題緊跟 我知道我在罰時上面沒有優(yōu)勢 于是趕緊開始看H題 題目大意是在一顆樹上分布有一些marbles 要把這些分布到每一個節(jié)點上面一個marble 求最小步數(shù) 想了想 開始敲 提交上去居然又是Wrong Answer 看來今天Wrong Anwer粘上我了 一頓亂改之后 大概比賽結(jié)束前30分鐘的時候發(fā)現(xiàn)題目中rooted tree的root并非確定 要預(yù)先判斷根節(jié)點 改過之后 順利AC 最后30分鐘仔細看D題題目 發(fā)現(xiàn)自己理解錯題意了 滿懷信心改過之后終于8題全部AC 因為罰時的緣故排在第二名 第三名和第四名都是6題 最后一個小時出題不多
比賽經(jīng)驗：
多題WA之后沒有慌張 多次自己的數(shù)據(jù)測試找到了程序的不足之處
不懈奮戰(zhàn) 堅持到最后
呵呵~~ 下個禮拜就決賽了 加油~！