大概在暑假之前, 我從來沒有想過能在暑假刷完Training.
去年初賽后, 刷了幾道Contest Bronze的水題, 想要重啟Training, 但是在寫了一道完全背包之后, 水平所限, 無可奈何的放棄了.
從高一開學(xué), 到NOIp后, 只寫了38k的程序. 今年5月, 寫了24k. 當(dāng)時的狀態(tài), 找不著北, 還要面對文化課的挑戰(zhàn). 而當(dāng)時的計劃又比較凌亂, 不管是訓(xùn)練還是比賽. 按照我當(dāng)時的能力, 應(yīng)該在9月初開始, 一直到11月一直寫DP. 期間可以穿插一些圖論和搜索的復(fù)習(xí), 11月可以學(xué)會寫一些簡單的暴搜(這個當(dāng)時做到了), 背一下裸的圖論代碼(當(dāng)時也做到了, 但是沒有上機, 應(yīng)該找裸的算法題不斷提交默寫代碼). 不過確定校內(nèi)上機環(huán)境已然是開學(xué)第三周了, 還有軍訓(xùn)一周. 時間本不多, 加上中考的失落, 以及高一的迷茫.
NOIp后曾一度拿到lrj老師推薦的題目, 大概是兩次吧. 不過UVa太猥了, 只有AC與否, 而且輸出格式紛繁, 實在是初學(xué)者的噩夢. 當(dāng)時水平有限, 或者說更確切的是自信有限. 不相信自己寫得出這樣的題目. 首先要相信自己能寫某一題, 然后就會寫了. 后面無可奈何的不了了之. 有點印象的僅僅是一道樹(模擬), 和spfa記錄方案.
寒假面對實現(xiàn)能力痛定思痛, 重寫Chapter3. 大概一直到3月份才完成, 除了msquare和comelot. 同時一直寫在線的Contest, March終于進了Silver, 而且寫的也不錯. 三個月寫了120k的代碼, 效果不錯, 之后就是歷時一個余月的”迎大運”斷網(wǎng)活動. 應(yīng)該說這三個月實現(xiàn)能力有了初步提升.
4月份幾乎一個月耗在了Chapter4上, 可是僅僅A了兩道最大流和一道最小環(huán). 嘗試了幾道題, 但是無果而終. 寫了幾種msquare, 這應(yīng)該是第二次研究Contor展開. 這個月網(wǎng)絡(luò)完全癱瘓, 第一周還腹痛如絞. 進度極慢.
5月初面對段考的結(jié)束, 以及4月份的奇慢進度, 和dy學(xué)長談了幾乎一晚上. 之后就按照學(xué)長建議開始寫DP, 從tyvj開始. 一開始面對LIS和背包很輕松的解決了, 但是其他類型壓力很大, 經(jīng)常卡幾天然后某一天突然A兩三題. 之后學(xué)了一些東西, 看了jec推薦的動歸八講 和 一套網(wǎng)上的題解. 而后得到了Ylen的建議, 開始考慮看題解和思考的平衡點. 期間還準備了LGOI的初賽, 結(jié)果較挫, 題目比較莫名其妙(完善最后一題), 大概前五吧. 重做去年初賽, 復(fù)習(xí)了空間向量, 突然發(fā)現(xiàn)去年第四題理解錯題意, 其實就是一個查表找最小字典序. 去年卻認為必須模擬, 還畫了二三十幅圖.
5月份的收獲主要是方向性的, DP和題解, 去年的思維誤區(qū). 盡管5月份訂的目標是50道, 但是期末考試前大概只寫了20道, 應(yīng)該還是盲目思考太多. 思考和學(xué)習(xí)之間需要一個平衡點, 隨著時間的推移, 會越來越偏向思考. 但是過早的傾向于思考會加大時間成本.
6月份又開始準備段考, 盡管結(jié)果很挫. LGOI的復(fù)賽正好和上課時間沖突了, 也沒心情去, 不了了之. 當(dāng)時的能力大概會300的算法, 不知道實現(xiàn)如何. 現(xiàn)在會400的算法, 不妨一試. 6月份的記憶似乎就剩下糾結(jié)前面某安保負責(zé)人的網(wǎng)線 和 生物王后雄了. 很難得的AK了王后雄前四章.
暑假頹了半個月, 看小說, 看電視劇, 看電影, 準備訂精華的課, 稍微動了動作業(yè).
半個月開始正式訓(xùn)練, A題速度快了很多. 也學(xué)了很多東西, 比如樹形DP(目前只會兒子兄弟表示法), 同時鑒于tyvj的難度, 開始注意一題多解. 大概10天之后開始寫朱全民的<動態(tài)規(guī)劃典型例題>, 寫了22題, 除了兩道SC. 大概總共用了3周時間完成上述工作, 52k代碼. 進一步鞏固了樹形DP, 開始接觸SC. 信心大增.
于是在個人膨脹的大背景下, Training被重新提上日程. 用了兩天的時間學(xué)習(xí)和復(fù)習(xí)暴搜, 重寫了n皇后問題(位運算無能). 用了一周左右的時間寫完了Chapter4, 參考了一些題解, 除了fence8沒怎么參考別人的AC程序. 因為入手新laptop的緣故, 停兩天, 然后開始Chapter5, 學(xué)習(xí)凸包, 在window卡了半天. 第二天發(fā)現(xiàn)實現(xiàn)非常之簡單, 完全是去年寫矩形切割留下的心理陰影, 主程序才10line, Tarjan都要20line. 之后最惡心的題目應(yīng)該是twofive, 完全的實現(xiàn)無能, 照著標程打了一遍才部分理解. Chapter6的題目幾乎都會寫暴力, 但是AC算法確實想不到, 而且居然涉及到多篇WC論文. 不管怎么樣, 總算過了. 實現(xiàn)能力越來越強, 只要明白了算法, 可以在3h內(nèi)調(diào)出95%的程序. 但是由于題目難度, 很多題目做不到一題多解. 這半個月可能是搞OI以來最充實的半個月, 寫了87k的代碼.
如果日后準備KOI甚至更進一步的話, 不妨重寫一遍Training后面的題目. 不同的是注重高級數(shù)據(jù)結(jié)構(gòu). 這次比較注重實現(xiàn)能力\調(diào)試能力和暴搜的訓(xùn)練, 較為輕視高級數(shù)據(jù)結(jié)構(gòu)和高級算法(比如兩道最小割都被無視了).
這一年以來, 最重要的轉(zhuǎn)折點應(yīng)該是5月, 其次是1月, 然后是7月. 從5月開始, 量變逐漸產(chǎn)生質(zhì)變.
接下來的任務(wù)是NOIp 2011, 目標應(yīng)該是300左右, 雖然大部分年份的題目估計在3h內(nèi)單題AC. 但是考慮到整體時間, 應(yīng)該做到45min內(nèi)出第一題(水題情況), 并且讀完全卷, 制定計劃. 后三題按照難度大致完成兩題, 必須完成每題的暴力部分, 然后寫對拍.
知識盲點還是有一些, 比如Contor展開, Hash, KMP, 最短路算法普遍很陌生, 并查集的應(yīng)用, 雙向廣搜, Tarjan等. 如果時間更多的話, 還有各種數(shù)論和遞推, 線段樹, 樹狀數(shù)組, 最大流. 實現(xiàn)盲點主要是對拍和暴力, 也許應(yīng)該先寫暴力, 然后寫AC算法(或者更強的部分算法), 寫makedata, 對拍. 寫暴力和makedata的時間應(yīng)該可以控制在10min內(nèi), 要多訓(xùn)練.
題目的話, 歷年題目還有很多沒寫, POJ的DP分類, 各種模擬賽, Ural. 9月份以前兩者為主, 主要是練習(xí)算法, 增強熟練程度, 寫一些有難度的算法題. 明天先寫完Training最后兩題的題解, 然后復(fù)習(xí)一下Tarjan. 剩下幾天以整理暑假題目為主, 每天大概A1~2道題, 從LGOI和歷年開始. 至少在NOIp范圍內(nèi), 沒什么題目不能做.
和一年前相比, 我更多的知道了我應(yīng)該做什么, 或者說, 更相信自己能做什么. 這應(yīng)該是一年來最大的突破.