2019年4月至5月停课·OI学习安排(一)

说明

现在不是为了准备比赛,只是为了学习更多的知识,为以后做好准备。我认为应该复习与学习相结合,学习一些省选必备知识点,练习各类的题目,力求一次学会。

学过的内容会复习一下,没有学过的就要把它学会。

这里先定了3周的内容,剩余的时间待安排。“week”按照停课开始的时间算,5个工作日左右为一周。

其中序号前有“-”的表示复习内容,有“*​”的表示选学内容(有时间就学,没时间可以先跳过),有“^”的表示重点,一定要掌握熟悉(至少做5道非模板题,宁愿一次过把内容学精,也不要后面准备比赛的时候再来着急)。

Week 1:字符串

^1 后缀数组(SA)及其性质(学会利用SA与height的性质解决各类问题)

^2 后缀树与后缀自动机(SAM)(巧用树的性质来解决区间字符串问题)

3 回文算法(manacher)及回文自动机,回文树

-4 KMP及AC自动机

*5 Border的性质与周期

Week 2:数学

^1 莫比乌斯函数与莫比乌斯反演(学会推式子)

-2 线性筛

3 杜教筛(学会筛出μ和φ的前缀和)

*4 洲阁筛

*5 Min_25筛

-6 欧拉函数

-7 费马小定理与欧拉定理

8 容斥原理

9 Lucas定理与扩展Lucas定理

^10 和式与积式的推导与化简(用于优化顺序,降低常数等,可以应用于各类的题目)

Week 3:数据结构

^1 线段树(一定要学会线段树的各类高级操作,如合并分裂、二分、可持久化等,而且可以维护各种问题)

*2 替罪羊树(一定要掌握思想,可以不打代码)

-3 Treap(提升熟练度,最好做到15分钟内写完模板,而且习惯写指针版的平衡树)

-4 Splay(提升熟练度,特别是区间翻转的部分)

*5 树套树

6 Link-Cut-Tree

-7 树链剖分(学一类长链剖分的题)

*8 点分治

2019年4月10日星期三 上午9时整

显示 Gitment 评论