一次DS总结+一些闲话

  “只要你们搞懂这一轮……你们就可以……”

  在zcy(或是xgg)来之前,hfu如是说。

  但是……

  “这一轮……可能是有一点……毕竟弄完了可以进……恩,我们的路还长啊!”

  着实,也是。本人在xgg_naive讲完之后,按着残缺的记忆,把他的例题和对应的可能正确的解决方法写了一写。题表在这儿!

  其实,当我把这张题表列出来的时候,是很懵的。因为仔细一看(或是粗略一看),似乎并没有什么“神题”!

  ↑这句口胡煞有介事。因为人人都知道,DS题好猜不好想,好想不好做。因为真正的优秀的DS题,总是会有太多、太多的细节让你意外(就像真正优秀的DP一样)。

  splay和LCT今天晚上应该调的出来,如果时间特别多就写一个树套树的裸题(矩阵修改矩阵求和,又是好想不好调)。

  关于树套树,有一个衡水的人跟我说:你第一次写,不要嫌烦,写成class,然后调出来时,一切便很好说了。

  我还没有试过。不过,俗话说“他山之石,可以攻玉”,大概也是这个道理吧。

  如果要系统地去做,也只有指望那15天了。任务很重啊。

  今天一看表,居然7月份就快过完了,虽然也学了一些知识,但觉得中间有很多重复、很多套路。似乎我已经进入到了一个新阶段。

  最开始的开始,还只是#include "stdio.h",int main() {},return 0,scanf,printf,for,while,if,switch,case,array,现在看来甚至都不能算作竞赛的一部分。随后,有了函数,思维便有了一定的灵活性。于是,就有了搜索、递归和回溯。DFS很好理解,但BFS却要迟上许久。这之间,知道了分治、排序(虽然可以用sort水过去,但确实是很多算法的思想与实践基础)、贪心、struct、高精度。再之后是简单DP、栈、队列。

  于是进入了稍微高一点的阶段。进入寒假,一本通也就这样过去了。从图论开始,搜索、最短路、并查集、MST、DAG、拓扑、tarjan强连通缩点。之后是idy,线段树、倍增LCA、主席树、值域线段树、树链剖分。寒假part 1结束。之后,是DP,主要讲了状压、树形和数位。然后,进入string,Trie树、AC自动机、KMP、后缀数组(当时并不懂)。之后再是图论,差分约束、网络流。对了,中间是math(寒假最有意义的两天),idy为我们领路。

  再敲这些之前,我竟然都还以为,寒假学了特别多的东西,现在看来,似乎也确实没有什么。所以,其实没有那么可怕。信息学竞赛需要努力啊!

  中间hfu让我们做了很多练习题(只是中间有很多都没有最终调试颇令人可惜),在练习者阶段站稳了脚跟。5月份,才又讲了DP优化、平衡树(lmy)和网络流。

  6月份,去了一次沈阳。系统的拉了一些知识,既有分享又有经验教训(……)。五个一本爷可以%%上很久啊(liu_runda估计,恩)……实在是太强了。但再转念一想,信息学竞赛似乎全都是套路。当然,这几年信竞在充分普及之后出现了特别多的新花样。不过,万变不离其宗。

  信息学竞赛作为一门竞赛,中间有很多干货,但本身也是考试。既然是考试,那么应试技巧当然是很有必要的。无法改变环境,就只有自己努力向上了。

  今天阳光出奇的好。清晰度极高,心情也很好。晚饭过后散步,发现操场边上的下水道那夹缝里,竟然有一抹清奇的绿色。仔细看看,似乎是从很深的地方冒出来的,一节一节向上长。或许是坚定了信念,从那夹缝深处的黑暗之中露出了头,在阳光之中格外娇嫩。那样的娇嫩,是饱经沧桑过后的彻悟,是对曾经付出的肯定,是对美好明天的憧憬。带着喟叹,我一圈一圈的绕着操场走着,然后发现这样的绿色并不孤独。这样的绿色绝不同于下水道中那样的苔藓,是真正的光明正大。

  不过,我是否能活到那一天呢?唉。

原文地址:https://www.cnblogs.com/Doggu/p/opinion20170719.html