杂记 - Hello,CSP2019

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知识点”处找到)。一直以来就想要整理一下数年所学,现在得着机会,整理成图。

几个大的版块:

  1. 基础算法
  2. 图论
  3. 数据结构
  4. 数学
  5. 算法效率(?)
  6. 动态规划
  7. 字符串

之后细分了很多。复习做不得假,总有一种感觉就是“你不复习什么 考试就考什么”,于是我采用的是有轻重的逐个复习(尽管如此,仍有缺漏)。有一些同学觉得:

- 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!

想不到这一天这么快就来了,那想必以后的一年不会太长吧

0%