照舊是由我分題目。這次只有一份題目, 和training的時侯一樣。分好後便設定好vim, gedit等環境, 這次用的是Linux, 加上keyboard十分順手, 令打字速度提升了10%。一開始看到J, 立即發現是很簡單的動態規劃, 便上機了。寫到一半呀暉告訴我A是赤裸裸的最大生成樹, 加上看到不少隊伍過了A, 便先寫A, 秒殺之。
24 min - Problem A - MST (1Y ; GagGuy)
過了後繼續寫J, 過了樣例便提交, 返回WA。此時whh的F可以做, 是很經典的二分圖匹配, 便換他上機。不久, 發現了J的錯處, 改之, 第2個Yes。
37 min - Problem J - DP (2Y ; GagGuy)
過題後呀暉問了我題D的一些東西, 和最近點對有關, 我便告訴他中大一直以來的做法, 便列印whh的F並由呀暉做D。我便隨手拿起G看看, 原來是prufer code, 211才剛學完, 不過不太肯定做法, 便先用樣例來試驗。過了不久, 便傳來呀暉射鵰的聲音。
50 min - Problem D - Closest pair (1Y ; Fai)
此時whh也找到F的錯處了。我便找呀暉討論一下G, 確定了做法。本來我打算寫的, 但是呀暉告訴我B是一條計算幾何的題目, 我想用些時間準備一下, 便很放心的把G交給呀暉。同時, whh的F也過了。
56 min - Problem F - Bipartite matching (1Y ; whh)
B是一條和判斷相似圖形有關的題目。由於數據很小, 應該可以用很直觀的方法做。於是便先計劃一下怎樣寫。不久, 便傳來第5個Yes。
64 min - Problem G - Prüfer code (1Y ; Fai + GagGuy)
由於頭5條都做得頗順利, 使我們一度在scoreboard上稱霸。此時的分工是由我做B, 呀暉做E - 一條頗麻煩的題目, whh看H - 一條很長的題目。準備了一會後, 我便開始寫B。寫的過程不算順利, 很多細節要處理。因此中途先給呀暉做E。然後就開始卡題了。我的B和呀暉的E都不斷返回WA, 眼見其它大學不斷超前我們, 而我們又沒有題可以過, 使我十分焦急。幸好, 呀暉的E在第3次提交時通過了。
172 min - Problem E - Ad Hoc? (3Y ; Fai)
我繼續做B, 而呀暉和whh聯手看H。H是一條graph題, 但看似不簡單。這時我才發現理解錯了B的題意, 但更改也不算太麻煩。可惜仍是返回WA。此時他們的H想到了做法, 便先給他們寫H, 可惜又返回WA。此時剩下一小時多一點, 已經有不少隊伍9題, 我們又卡了2題, 使我再一次十分著急, 便先出去吃東西冷靜, 並整理了一下思路, 決定換另一種方法寫B。而他們再看一次H後, 發現好像理解錯了, 把題目深化了很多。回來後重新寫B, 並處理了有重點的case, 但仍是WA。幸好, 在封board後18分鐘, 我們的H在更改後通過了。
258 min - Problem H - Shortest Path (2Y ; whh)
剩下40分鐘, 而我又覺得B差一點就能過了, 呀暉的C好像又很有想法, 使我一度想過上9題的希望。接下來的時間都是我和呀暉交替寫B和C, 可惜最後B仍是不能通過, C則不夠時間完成。最後以7題結束, 排名12。
No comments:
Post a Comment