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