关于 OI 学习路线

发布时间 2023-12-31 22:33:05作者: Piggy424008

整理一下我学习 OI 的路线以及我还有什么没学。

2022.07~2022.08:简单语法,STL 的低阶应用,搜索/状压/树形/区间 dp 初探。后者掌握的极为不牢固,可以近似认为不会。

2022.09:最短路,稍微理解了一点点线段树,简单的线性 dp。

2022.10:并查集,快速幂,埃筛,CRT,稍微理解了一点点线筛,最小生成树。学习了链式前向星,所以开始学习网络流,刷了一些网络流 \(24\) 题。因为当时 CSP 在即而我码力很差,找了一周刷了很多红题。了解了很多算法但是都不太会,比如 ST 表,Trie,字符串哈希,单调栈。位运算基本应用。

我的做题记录显示我当时写了裴蜀定理和乘法逆元,但我当时后者应该是不太会的。

用线段树过掉了树状数组的板子。写了一些简单的背包 DP。

搜,搜,都可以搜。写的题大多数是奇怪的搜。

还理解了一些怪东西,比如 FFT,LCA,矩阵快速幂,exgcd。

2022.11:康托展开,Tarjan(强联通分量,边双联通分量,点双联通分量),差分约束,一些博弈论(Nim 游戏和威佐夫博弈)。

我当时写了 LIS,但现在完全忘了,只会树状数组求 LIS 了。

重写了一些网络流,不想学匈牙利因为复杂度比较高。

学习了模拟退火?现在完全忘了。

还在不断搜索。

学了一些小清新字符串 KMP 马拉车很什么的。学了 Lucas 定理,感觉很简单。学了拉格朗日插值,没意思。

尝试接触了 Prufer 序列,最小表示法,原根,高斯消元,线性基,平衡树。但现在只会后三个了,前三个完全不会了。

学了高消就顺便学了一下矩阵求逆,现在也忘了。

月底学了扫描线,左偏树,行列式求值,现在只会第一个了。这个月学了很多,但忘得更多,这为我后来的什么都写不出来埋下了祸根。

扩展欧拉定理比较简单,跟费小一起记了。

尝试着写一些离线题,但当时不甚理解离线思想,遂发帖询问,得到了一些答案。

2022.12:主席树,树链剖分,MCMF,子序列自动机,简单的 AC 自动机。

尝试学了分治 FFT 和多项式运算全家桶,然后就是忘 \(^3\)

学习了思想:Segment Beats。

学习了欧拉函数,数论分块,拓扑排序,群论,树上基本操作(直径,dp,哈希)。

2023.1:学习了莫比乌斯反演,积性函数,狄利克雷卷积,MR,PR,Fib 数列的一些性质,抽屉原理,容斥原理,二维/三维计算几何。

最后一个忘光了。

尝试理解了 DP 的常用优化(单调栈/单调队列/斜率优化/四边形不等式优化)。

2023.2:没学什么新东西。

2023.3:复习了上面所有有用的东西。当省选即将来临,我发现我还停留在口头上会的时候我终于慌了。学习了 SA,动态 dp,最小斯坦纳树,次小生成树,最小树形图,同余最短路。

2023.4:树同构,树分治,线段树分裂/合并,wqs 二分,多项式全家桶,类欧几里得算法(怎么现在才学),exCRT,线段树分治。

Lyndon 分解,自适应辛普森,最小斯坦纳树,Chirp-Z Transform,FWT,LCT,树套树,李超线段树。

学习了可持久化数据结构的原理,莫队(不带修),根号的基本用途。

学习了一些离线算法,比如 cdq 和整体二分。

听说了 Sqrt Tree,感觉很厉害。

2023.5~2023.6:高维偏序,点分治。尝试理解 SAM 和广义 SAM。

里面没有提到牛顿迭代是因为忘了什么时候学的。

写完发现原来也没学多少东西。不过作为某种程度上的零基础,高一一年学这么多我感觉还行吧。