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