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