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