//大概在5周前就寫完忘記發(fā)了, (2)和(3)大概胎死腹中了.
Climber.pI按: 時隔兩年, 故地重游, 大概是高中OI生涯的第二次GDKOI, 也是最后一次GDKOI, 倒數(shù)第三場正式比賽了. 結果差強人意, 卻也是意料之中. 也就形式化一把, 隨記二三.
(1) 關于賽場
大概是前一天晚上一個人逛中大, 結果還沒找錯了講評的地方 = =|||
Day0
大概就是各種聊天, 各種扯淡…沒敲一行代碼, 所以第二天就NC了
Day1
感覺組織工作比NOIp差很多, 比如進去都半個小時了才有水喝.
P1是個DP, 一開始根據(jù)數(shù)據(jù)范圍準備的判斷了復雜度, 但是后來鑒于題目的背景, 沒有進一步的分析題意. 相反, 聯(lián)想到了USACO Training的job, 二分+貪心經(jīng)典題, 于是YY了一個貪心. 大概是把所有任務排序, 然后先選大的, 不能再裝的時候就選小的, 居然還過了樣例.
但當時對貪心的正確性毫無把握, 于是又寫了O(a^N)的暴搜, 然后對拍. 大概是手生的緣故, 一個半小時才全部折騰完, 最終的結果是貪心錯誤. 于是有改寫了一個小范圍暴搜, 大范圍貪心的程序. 當天中午重新看題的時候, 瞬間發(fā)現(xiàn)題目實際上是個變形的背包. 一旦在現(xiàn)場思維走偏, 總是難以挽回, 比如去年初賽, 比如去年Day1P2.
這時候有種奇怪的感覺, 時時刻刻想著放棄卻又不敢放棄, 完全不能控制比賽進程, 只能順著身體的慣性寫題. 很像初中的時候跑1500的感覺, 帶著種無法預知的恐懼.
P2是最短路, 由于邊的權值為{1, 2, 3}其中一個數(shù), 所以可以拆成若干邊權為1的邊, 從而用O(3n)的BFS AC.
當時讀題之后認為dij+heap可以A, 但是幾乎不記得怎么寫了. 大致估計了一下, 認為SPFA可以過80%, 又擔心SPFA敲掛, 又多敲了一個Floyd. 敲完折騰完對拍基本上過了3h了, 結果一直不同, 最后手工算了一組數(shù)據(jù)發(fā)現(xiàn)是Floyd掛了, 原因不知. 當然, 由于只開了80%的范圍, 也無緣享受4s時限優(yōu)惠了.
P3是個數(shù)學題, 當時只有40+min, 果斷放棄. 但事實上30%的做法可以直接手算打表, 50%的做法可以利用DP, 甚至可以通過記憶化搜索打表AC.
P4是字符串, 由于不記得C++的I/O, 只能用字符數(shù)組敲. 雖然原理絕對正確, 但是最后還是沒調(diào)出來.
于是Day1就結束了, 41算是意料之中, 值得慶幸的是SPFA沒有寫掛. 和NOIp一樣, 依舊是全市第二, 盡管wx神牛這次102是我的若干倍.
Day2
大概是被Day1嚇到了, Day2晚上回來還是敲了一會兒代碼. 第二天的組織工作好了很多.
P1是數(shù)學題. 仔細讀題之后很快發(fā)現(xiàn)了O(N)的做法, 聯(lián)想到若干次被周期數(shù)列坑了, 果斷找循環(huán)節(jié), 發(fā)現(xiàn)前面一部分并不循環(huán), 而循環(huán)節(jié)一定是N的倍數(shù), 于是果斷從后面找N. 考慮了50%的范圍, 于是找了400N, 于是只過了60%的數(shù)據(jù). 可以證明的是循環(huán)節(jié)長度不超過O(N^2), 但是我并不知道如何證明, 于是12分沒了. 經(jīng)過一番對拍, 時間已經(jīng)過了近2h了.
P2的標準做法需要用到線段樹/樹狀數(shù)組/平衡樹等高級數(shù)據(jù)結構. 讀題之后發(fā)現(xiàn)模擬十分好寫, 但是由于當時考慮不周, 邊寫邊調(diào)浪費了很多時間. 大概是利用一個數(shù)組記錄某值是否存在, 然后利用數(shù)組模擬鏈表來實現(xiàn). 終于調(diào)對了之后, 發(fā)現(xiàn)樣例掛了, 特意問了評委30%的范圍是否符合50%的要求, 得到肯定答復后. 遂放棄此題的進一步調(diào)試, 最終過了4個點.
當時還有70min左右, 在P3和P4猶豫了很久, 發(fā)現(xiàn)P4如果用Floyd的話還需要記錄路徑, 實在不好寫, 遂放棄.
第三題是搜索, 可以利用DP預處理狀態(tài), 或者充分利用問題性質(zhì), 只枚舉每個格子需要填否即可. 當時的做法是記錄未填格子的位置, 逐個枚舉, 如果某行全部枚舉后進行可行性剪枝, 最后判斷沒列是否符合題意. 雖然思路絕對正確, 但是一直調(diào)不出來, 在最后幾分鐘突然發(fā)現(xiàn)是初始狀態(tài)打成1了, 應該為0, 改了之后, 屏幕一閃, 樣例過了. 最終過了6個點, 僅超時了兩個點, 有兩個WA的點多輸出了一組解, 不知道哪里寫掛了.
于是總分就是18 + 16 + 24 = 58, 又是全市第二, xh64第一, wx牛居然直接3分了…
至此, GDKOI的賽程結束, 在中大西苑一樓大堂看到一等和二等證書發(fā)完卻不見深圳蹤影, 悵然若失之感涌上心頭, 差不多退役了.
(2) 一些人一些事
(3) 亂七八糟的想法