同步自 CSP Wiki 提高组体系:系统覆盖容斥、同余、逆元、矩阵快速幂、A*/IDA* 搜索、树形/状压/数位/单调队列优化 DP、并查集、线段树、平衡树、莫队、最短路、Tarjan 强连通分量、LCA、KMP、Trie、Manacher 等核心提高组算法。
- 创建人
同步自 CSP Wiki 提高组体系:系统覆盖容斥、同余、逆元、矩阵快速幂、A*/IDA* 搜索、树形/状压/数位/单调队列优化 DP、并查集、线段树、平衡树、莫队、最短路、Tarjan 强连通分量、LCA、KMP、Trie、Manacher 等核心提高组算法。
开篇导读。本章只有一讲,讲清楚提高组的考试层级与 NOIP 的衔接、按目标分数(含省一、省队、AK)该怎么安排学习内容、以及模拟实战与赛后复盘的方法。建议在进入第 1 章之前先读完这一讲。
本章 10 讲:集合基础、容斥原理、欧拉函数、筛法进阶、欧拉定理与费马小定理、同余方程、乘法逆元、裴蜀定理、中国剩余定理、矩阵与矩阵快速幂。
学习建议:这一章概念密度最高。先吃透同余体系(欧拉定理 → 逆元 → 同余方程 → CRT),再进矩阵;每个结论自己推一遍比背公式牢。
本章 5 讲:双向搜索、A* 搜索、迭代加深、IDA*、剪枝。
学习建议:剪枝是提高组搜索的分数核心,先学会估界再谈 A*;IDA* 建议和迭代加深一起理解,本质是同一套"限定深度反复搜"。
本章 9 讲:背包进阶、树形 DP、状压 DP、数位 DP、计数 DP、单调队列/栈优化、四边形不等式优化、状态设计技巧,最后一讲是核心代码模板汇总。
学习建议:状态设计比方程更重要,先写清"这一维代表什么";优化部分一律先写朴素版、跑对样例,再改。
本章 12 讲:二叉堆、并查集、单调栈、单调队列、ST 表、树状数组、线段树、二叉搜索树与平衡树、Splay、Treap、分块、莫队。
学习建议:并查集、树状数组、线段树这三件必须手写到不出错;平衡树和莫队属于拔高,前面的写熟了再上。
本章 15 讲,是全课最长的一章:最小生成树、Floyd/Bellman-Ford/SPFA/Dijkstra 四套最短路、拓扑排序、欧拉路、Tarjan 强连通分量、割点割边、双连通分量、树的直径与重心、LCA、树上前缀和与差分、最长路、次短路、Prufer 序列。
学习建议:按"最短路 → 连通性 → 树上问题"三段推进;Tarjan 和 LCA 是省选常客,模板要能默写。
本章 5 讲:字符串基础术语、前缀函数与字符串匹配、字符串哈希、Trie 树、Manacher 算法。
学习建议:KMP 的 next 数组建议手推几遍再写代码;哈希随手准备双模数,防止被卡。
本章 4 讲:离散化、双指针、悬线法、扫描线。都是看着小、考场上救命的技巧。
学习建议:悬线法配一道最大子矩形题练;扫描线建议和线段树一起做一遍矩形面积并。