NOIP 2021 备战计划

NOIP 2021 备战 计划

复习知识点：

加粗表示一定去复习，?表示很可能不需要

线段树、树状数组：无论最近写多少遍都要去好好复习

Dij、SPFA：理由同上

大DP：哪个不重要？

门类：线性DP、区间DP、状压DP、DAG DP、树型DP、期望DP……甚至FWT

套路：数据结构优化、单调性优化、结合贪心优化、记搜、bfs/dfs/topo辅助

KMP，Z 函数：去年考到过……重在理解

平衡树（fhq treap,splay）：血的教训记心间

概率期望：玄学，重在理解，也许会考

哈希：很有用，很灵活，很玄学

tarjan 求SCC、桥、割点、LCA、e-DCC、v-DCC （全家桶一把复习掉吧）

贝祖/费小/中国剩余/威尔逊/欧拉定理：都还记得，CRT要去复习一下式子

高斯消元，高斯约旦消元？：也许会考系列

匈牙利，KM？（似乎不在纲里）

Floyd：门道还是很多的，有三鬼子，还有传递闭包（前几天才考），都很有用

快速排序、归并排序……排序全家桶？：会有用的，快排好久没手写了……

A*，IDA*: 都没怎么写过……不过感觉有用

排列组合、容斥、卡特兰：前几天联考正好搞过了，应该没问题

exgcd：掌握即可

笛卡尔树（这个在考纲里！）：注重其在处理序列问题上的灵活运用，还是很有用的

次小生成树/次短路：在考纲里……估计只需要掌握思想

树链剖分？：或许可以写暴力

斜率优化？：大概率不考

网络流？：CSP 竟然考了？？（虽然是暴力）

最后两天题单：

加粗知识点模板（如果有）：

线段树1/树状数组线段树2 加强版树状数组

SPFA Dijkstra KMP Z Function

高斯消元 SCC缩点割点 CRT

普通平衡树文艺平衡树

其它题：

CF364E zhy的题
P6835 当期望板子题复习吧（一点也不板）
P6852 中午和hym,zyf大佬讨论的题，构造好题