有些东西,写下来或许才能放下
或才能重新拾起吧.
一年匆匆入此坑
几经辉煌几近红
时去未能入校队
落得孤生水题多
暑假看紫书白书算导来专题训练一下,弥补4+2的些许遗憾.
啊算导啊.那应该是我们算法界的圣经了.
许多人口中的渲染.似乎引起了对它的肃穆.
上了大学之后,才知道水题是那么的重要.比如有些学科好好刷掉一些题库之后,就很容易博得绩点满堂.以致于降低了大学绩点的吸引力.昨天和学妹吹水的时候.还在吹牛需要竞赛来维持一点智商.”吆喝”了一年的算法竞赛之路,似乎也在今天有了一个新的转角.4+2莫大的打击让我玩了几天html游戏设计(<<网页游戏开发秘笈>>,这是一本一章一个引擎教学的神书…..)然后今天水了一盘计蒜之道的复赛.看起来赚了一件衣服.于是又有点像记录一些东西,勉励之后的方向.
啊水题真的很重要.
水题上百,手速不慢.
上学期最开始的时候是郭老师上台宣讲”ACM算法竞赛”,抑或是晓铭老师说了一句”打的好可以去东校参加比赛”.当初就特别真诚的抱着去东校可以报销车费的美好欲望报名了ACM中珠集训队,当时还特别好奇这玩意为啥要宣传,福利挺棒的啊.
厚着老脸在上面一堆省赛一等奖的同学下面写上了自己的名字,每周二晚上与东校那边一起刷vjudge的SYSU系列.刘老师还一人送了一本书,我的是那本黑书.<<算法艺术与信息学竞赛>>书是好书.但是对于刚刚接触这方面的我而言,无异于葵花宝典.其实那一段时间的vjudge提高并不是很明显,因为跟着大腿的方向,并没有补题的习惯.而在算法讨论群里面的那些同学讨论着动归或数据结构,又想到一个TA对我说的话
你最近还是先看一些容易的算法吧,动归以后再搞
于是就没有补题的欲望,而对于那些计算几何之类”看起来听得懂”的题,就更没有补题的欲望了.这个不好的习惯囊括了之后的一次次短码之美月赛,考试等等.莫名自大的可怕,还是难以想象.
于是在短码之美的打击下,(同时也是在知乎)的安利下,翻开了紫书.<<算法竞赛入门经典(第二版)>>,水了两三章之后这本书特别够意思的直接来region题,向TA问了几道题后,王芮浩师兄建议我先去看它的第一版.于是我转战第一版.其实更多的是看书,书看完了,UVA也才刷掉几道搜索的水题.
那个时候真的很拼啊.刷UVA的题动不动就四五个小时过去了.因为那儿的英文挺坑的,看过去少说一个小时过去了.而后理解题意之后宛如智障的瞎打一顿码,而后再去努力理解题解.最后看到一篇博客的一句话深有感触看题解是一个相对的事,如果实在很长时间做不出来,那么无妨一看(把这句或许得辩证的理解,但是我往往被坑去太多时间,以致于”事倍功半”).
当时特别励志的用这句话鼓舞自己
“刷题不过百,不是人傻就是懒”
第一个学期看着题解在UVA上敲了百题后就差不多到期末了.自大情绪又体现出来,于是水题很快很快(真的很快…)的刷完后,就被两道算法题卡住木讷到最后结束.不过也验证了这个小标题水题过百,手速不慢,然而由于vjudge里面过题太少.便没有赢得公费旅游的资格.但是这个阶段得到的最大教训却是另外一个.
因为装逼的需求.于是想要多学一些”算法知识”,于是从网上找了很多很多资料,买了良莠不齐的各种算法书,比如清华大学出版社的<<算法设计与分析>>教材.发现自己是多么稚嫩之外似乎大量的时间一无所获反而盲目满足.甚至有些书都未翻开过.不过最为可惜的莫过于在英语课和思修课上”学”算法,其实也不过看几道水题而已,反而糟蹋了老师的精心准备,愧对老师.
高中起点,扬起新帆
寒假尝试了另外几条路之后就觉得USACO(美国高中的训练OJ)是一个不错的选择.有趣的一件事是上面总是CHI(中国)ip比美国多,于是其实这个学期刷题基本都在那上面,见证了一次次把自己以前刷的题归为水题的过程.略为可惜的是之后对于整理笔记的思考不足以体现其价值.而且到写这篇文章的时候也卡在了一道很难写的长程序上面.
开始写博客了之后记录也增多.相比上个学期,由于3月份开始比赛纷至沓来,这个学期其实更多的是去做题了.然而似乎算上比赛过的题也就是百来道,不过这些题的质量相对就高了一些,并不是盲目的模拟(虽然也很多题想了很久没想到算法..模拟过了的)刚开学的时候看(水)了数据结构与算法分析.它更大的用处在于解除我对很多”高级名词”的畏惧. <<数据结构与算法分析(C语言描述)>> 然而在4+2第一场赛后讨论中,被梓华提及的红黑树,以及他写的二叉+桶排给惊艳.于是明白了另一个道理
“没敲过代码的看书过程,意义实在有限”
三月份开始就是各种各样的比赛了,说实话就是一次又一次被惊艳.先是校赛预选赛,脑洞一开用hash优化了一个map的查询,(然而那时候还宣称map是hash结果天真的我..)给队伍贡献了一题.而后百度之星在初赛由于只过了水(相对而言)题于是无缘(拿)复(衣)赛(服),再然后省赛/校赛见识了脑洞对于算法的讲究.当时打浙江省赛木洪对于题目的直觉之间经验了我,特别是后来省赛两位队友脑洞强推公式简直可怕.于是那时候开始努力提高自己的脑洞水平.于是在编程之美里面很快的刷掉了两道脑洞题,当然不能掩饰被hack掉的事实.期末考试后便是4+2校队选拔赛.借了两本4+2的题解..简直打开了一个新的世界…….于是最开始的预期是很悲观的四场打铁,但是最后平均一场一题,也算不上过多遗憾,只能怪自己思维和视野的局限.再然后就是今天的计蒜之道复赛,认真刷好水题的我以倒数第三的位置进了复赛.顺便以倒数第三的拿衣服位置拿了衣服..
所以话说回来..水题还是很重要的.不过想要更上一层楼,得有更大的思考了.
安利
“别人口中”的水题,
建议搜索关键词有: 模拟, 模板题, ACM数学题
<<啊哈!算法>>
这本书应该才是真正的算法入门读物,网络上他的博客里面也有他对于基本算法的解释.当时搜排序搜到后就喜欢上了这种”幼儿园式”的教学方法.而且很期待第二版的出版.
建议搜索关键词有: 贪心, 树状数组, 并查集 ,高精度
<<挑战程序设计>>/<<算法竞赛入门经典(第一版)>>/USACO题库
这三个其实才算稍微入门了之后的一些选择,芮浩师兄借了我一本<<挑战程序设计>>,我翻了几页后自己买了一本,然而因为心分三用没有往后再扎实的看下去.<<入门经典>>第一版大概是我唯一看完的一本算法书吧.当时草草看完,因为看不懂的直接跳.现在看来其实也并没有那么难,只是一种莫名的畏惧或陌生吧..USACO题库我刷到最后一章暂停了下来,刷题的一些记录放在了CSDN博客上面.前面三章几乎都是些水题吧.因为重排了之后,后面几章便才开始讲基础的算法模板题.nocow上题解的帮助挺大的.因为简单题可以看到更漂亮的算法,难题可以明白大神的思维方式.
建议搜索关键词有: 网络流, 动态规划, 剪枝
< < ACM国际大学生程序设计竞赛 > > 知识与入门 / 算法与实现
第二本是常用的模板,在第一学期期中机考快速幂的时候知道的.但是这本模板给我最大的体验就是如果没练过,相对坑度比<<算法竞赛入门经典(训练指南)>>要大.另外缺少hash的函数处理模板.其实实际使用中若不是模板题这本书参考价值更多的是看个人,毕竟ACM允许纸质材料后,更多的考察抽象思维能力.<<知识与入门>>便是常见算法的讲解,讲的特别简明精要,优点是可以开拓眼界,缺点是没有证明部分,若没有基础看的会比较虚..相对难一些的比赛想要现学现用也是不大现实.另外其实安利自己从网上收集的模板,在这篇文章里面能找到
建议搜索关键词有: 数据结构, 图论 , 数论
大一结束,我大概也就停留在这个水平吧,之后也不好安利.或许小伙伴你愿意和我一起刷白书呢.
几近一年过去,160的车费补贴也算是实现了最初的梦想,当然离现在的理想还是有些许差距.
希望暑假加油完成专题训练.下学期算法比赛好好表现.不能再靠水题来混日子了.
4+2感想(原4+2题解感想摘录)
伙食很好
讲题详细
难度迷人
补贴超多
公费旅游
五星好评
第一场打铁
五个小时一题没有过的感觉还是很不好受的.
晚上思考了很久人生.觉得大一还是努力去见见世面吧.
但是大二的两个队友却都没空参赛了.sigh..真的有一些莫名的绝望.
总结
- 一段代码写烂一个小时后就得有重写的打算,不要老是”调”评测系统
- 一个代码超时如果尚有可回忆的方法,那么久一定要坚持复杂度.超时可能是写烂了而不是复杂度太高
对于一个区间的动态维护首先应该想到线段树.
- 线段树和优先队列的区别.
- 线段树是每次查询的时候更新,优先队列对于版本信息会较为混淆(不能及时剔除旧版本)
第二场迷之两题
一上手看最后一题..写了半小时发现看错题了……..
但是还算是捡回了昨天的运气XD
- NIM博弈赢的方式是所有异或为0
- 统计四堆不如统计两堆.然后枚举后面两堆和前面两堆异或一样就可以了..
BTW.今天晚霞挺美的.
生活还是要继续的:)
第三场步入正轨
今天来东校比赛..周围都是大腿光环:)
把两个实训队友落在珠海还是内心有一些愧疚的..不过下午看到做出来超级漂亮的板子.简直女神.
过了两题后学了两个小时算法..发现模板这种东西关键时刻还是比较鸡肋的.(顿时为期末模板写烂找好了借口).不过很有趣的是翻到了AC自动机的部分.然后认认真真看了一个小时(并没有看懂)恭喜少豪最后一秒钟提交通过233.
很开心的是郭老师过来说报销车费住宿费.公费旅游名不虚传233
话题步入正轨.这次比赛很难进校队了,但是从一定程度上已经扩宽了我的知识面.比如第三题AC自动机,第二题状态压缩以及第一场里面对于线段树的理解加深.也相对来说超过了最开始看4+2真题时候”可能打铁”的预期.与其说让我暑假放弃对于算法的训练,不如说方向更加明确了一些
最后一场继续打铁
心还是很累..
今天完成第一次把电脑弄崩的成就…
毕竟我还是太嫩了..不过最为可惜的是,看到两个省赛队友都拒绝参赛,那大二的我也不知道会做出什么选择,或许移动大三的课比较水吧..
不过一题没过的最后一天,看到队友能把小车电焊部分做好,真是超级欣慰和感动
英语题..出题师兄越做越忍不住..不停加注释什么的终于破译了英语之谜
论爆到英语大神重要性 来考考那么weed out是什么意思(微笑)