Good Bye, NOIP. Hello! CSP 2019!
Have a nice day!(以下是我最后的复习,将所有我还记得的知识点罗列出来)
Part1. 前言
考前最后一晚,终得以喘息……愿畅谈关于 OI 的看法
在 CSP 2019 前一天晚(2019/11/14),决定要总结一下这几天停课、全力准备 CSP 的得失。顺便也给 CSP 后的总结留一个坑……
从初二开始打第一场 NOIP 普及组(大概是我发挥得最好的一次),然后初三打第一场提高组……不得不说初三的那段时间进步非常缓慢,差一点连一等奖都没拿到。
其实印象最深刻的是初三参加的第一场省选吧。教练选出了几个较为优秀的同学去参加,也就包括我。实际上,那段时间我的状态一直不好,停课、跟着高二学长学习,基本上没什么长进……就感觉很难gan出一道题的正解,甚至被选择去参加省选,心理感觉也是去当个炮灰,并不是冲击省队的选手(或许让我去感受省选的题目难度、氛围才是真正目的吧)……事实也是这样的,省选上每道题都只能尽可能骗分。
可能也是因为我努力骗分吧,我的成绩在和我水平相当的几位同学中还算不错。当时考试完、公布成绩时我也是这样想的。但同年级的也不乏佼佼者,且不言外校,本校的神犇 taotao 在 Day1 的分数就比我两场的总分要高……
说实话,那时候是抱着试一试的心态去参加的,所以感觉没什么……但真正到了 CSP2019 时,就是另一番模样了。
且听细说。
Part2. 文化课&竞赛
这也是大多数 OIer 纠结的一个问题。其实我觉得自己现在的处境还真的挺尴尬的(不过我本来就是个尴尬人),我的成绩还真不算差,但是也好不到能够稳拿省队名额,像本校神犇一样初中就去 NOI……
从高一开学(其实开学的时候离 CSP 也只有一个多月了),基本上就没有上晚自习;再后来就是停了一部分的文化课。
其实我觉得吧,我还真不是特别愿意停课…… 哪怕那门课是我不喜欢或是不擅长的,总不喜欢脱离整个体系,成为一个神秘的小团体(对于其他非信竞的同学,的确比较神秘……)一直有一个说起来很不切实际的梦想,就是成为所谓的全面的选手(以前甚至还想学遍信竟所有知识,但是现在知识点日新月异,几乎不可能学完了)。
既然无法成为梦想中的自己,就换一种活法,将“梦想”作为方向 —— 它在前方永远引领着我,但是也意味着我永远也无法追上它。
千百万种活法,生命的模样 -
- (我喜欢的歌曲)《旁观者S的独白》
也许这正是我与别人不同的活法,不仅和其他非 OI 选手、也和各位共同竞争的 OIer 不同的活法。
便去接受,哪怕是被逼无奈去选择的道路。千百条道路,不一定条条通罗马,也不一定条条都有人涉足;但只要前往了一条道路,就在这条路上留下鲜明、不可磨灭的印记,即使只是警告后来之人未来坎坷。
Part3. 正题
这是我复习 OI 最久、最认真、也最全面的一次;CSP 必将有果,或是证明我这段时间的努力,或是戳穿认真复习的表象下的疏漏
为了复习,我列出了一个知识点树形图(可以在“我的简介”中的最下方的“附:OI知识点”处找到)。一直以来就想要整理一下数年所学,现在得着机会,整理成图。
几个大的版块:
- 基础算法
- 图论
- 数据结构
- 数学
- 算法效率(?)
- 动态规划
- 字符串
之后细分了很多。复习做不得假,总有一种感觉就是“你不复习什么 考试就考什么”,于是我采用的是有轻重的逐个复习(尽管如此,仍有缺漏)。有一些同学觉得:
- XX算法这么难,CSP 怎么可能考嘛 / 算了,不复习XX算法了,要是这次考到了这个,我认命写暴力好吧……
然而,到了考场上,你发现这道题用到某一个你知道但是没有复习的知识点,你真的肯认命吗?无可奈何写个暴力你真的甘心吗?
其实虽然感觉初中的班主任过于激进、讲大道理,但是还是想要引用一句他的口头禅:
我只针对这个现象,不针对某个人
功利性,这个字眼听起来就像“追名逐利”这个词一样,虽本来没有任何感情色彩,但是总觉得说某个人特别“功利”,就有一点贬义、讽刺他“过于俗套”的意思。
说起来,又想到了文化课的事。对于我来说,高考选科显然不会选政治历史,然后这次选择停课,毫不犹豫地停掉了所有政治历史课,其实也是有违我的原则的。(原则一而再再而三地破,便不可叫原则了,或许我应该给它换个称谓)
既然上了生活这条船,你能调整的只有你在船上的位置:是在驾驶掌舵、在桅杆眺望、或是在船舱享受。没有一种做法应被嘲笑,然而掌舵的人、眺望的人便将矛头指向异类,以“成功论”的制高点鄙视异类……于是原本安稳享受的人,去往危险的桅杆顶,抢过船舵。
总有一天船会翻的。
(扯远了)总而言之,各类算法,只要存在,必有存在价值 —— SPFA虽被卡,它能够判断负权环,仍有意义;map 虽常数大,它相对于 hash 方便简洁、没有冲突,也能在 OI 中发挥作用。
只要它存在,凭什么说就不会出成题目?有什么理由否认它的意义?
(扯得更远了,回来总结自己的复习)不得不说这次复习是恶补了数论。之前许多数论知识虽然讲过,但是基本上都在自闭,好多知识点是靠自己听课后、花费数倍的精力去自行理解 —— 没有理解得透彻,印象也并不深刻。
这次复习数论,着重复习了:
- 中国剩余定理及其扩展
- 线性筛欧拉函数 / 分解质因数法求欧拉函数
- 扩展欧几里得
- BSGS
- Lucas 定理
- 高斯消元
以上这些是我认为尤其重要的,给予了最高重要度,其实也有没复习到的地方(也是因为我设置了”轻重程度“),比如生成树、莫比乌斯反演……
然后基本上是新学了 CDQ分治,只是初步了解而已,也没有去做难题(太耗费时间了)。
数据结构一直是我认为掌握的比较好的一个板块,所以只是将知识点罗列出来,基本上不复习就可以写出来了:
- 线段树 - 主席树
- 可并堆 - 左偏树
- 平衡树 - Splay / Treap(替罪羊没弄懂)
还有一个比较陌生的板块,也是之前讲过没听懂的,字符串:
- KMP
- AC自动机 / Trie图
- 字符串哈希
这几个学起来还是很累的,另外 Manacher 是我还记得怎么写的,但是后缀数组、后缀自动机、回文自动机还是gan不动……只有等考后补习了。
图论复习了很多:
- 最短路
- SPFA / 堆优化Dijkstra
- 差分约束
- 网络流(?你以为不可能考就不复习了)
- Dinic (ISAP忘了)
- 费用流
- 生成树
- Kruskal
- Prim
- Bruvaka(一个很少见但是似乎很强力的算法)
- Kruskal 重构树(这是最近新学的呢)
- Tarjan缩点
- 点双
- 边双
- 强连通分量
大概这样,就不细分了写不下
(啊-不想写了,咕算了)
剩下还有一些杂算法:
- 莫队算法(出乎意料)
- IDA*
- DLX
- 三分
(好多啊)这次复习,复习得最少的反而是很难且很常考的 DP……但是 DP 的种类实在是太多了,且具有很强的特殊性。除非练题,这在紧张的复习时间中是不允许的。就只复习了几个常用的 DP 优化以及一些 DP 类型。
Part4.
就这样了,若是说给自己的心理安慰也满足了……
希望明天的 CSP 能展示这几天的成果
你只管努力,剩下的就交给幸运了
- 来自忘了哪个博主的签名
所有一起努力的同学 ”Good Luck, and hello, CSP 2019“
最后分享一首 COP 的很久以前的作品《灼之花》~
The End
Thanks for reading!
想不到这一天这么快就来了,那想必以后的一年不会太长吧