说明
现在不是为了准备比赛,只是为了学习更多的知识,为以后做好准备。我认为应该复习与学习相结合,学习一些省选必备知识点,练习各类的题目,力求一次学会。
学过的内容会复习一下,没有学过的就要把它学会。
这里先定了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时整