大概在暑假之前, 我从来没有想过能在暑假刷完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范围内, 没什么题目不能做.
和一年前相比, 我更多的知道了我应该做什么, 或者说, 更相信自己能做什么. 这应该是一年来最大的突破.