CSP-S 提高 知识点

两端同时搜索、相遇判定、效率对比分析

启发式函数设计、与 Dijkstra 的关系、A* 正确性条件

均摊分析、主定理（Master Theorem）、常见算法复杂度汇总

迭代加深 + 启发式剪枝、经典应用

限制深度的 DFS、适用场景分析

归并排序求逆序对、CDQ 分治、平面最近点对

ST 表中的倍增、LCA 的倍增法、倍增在序列/树上的通用技巧

坐标压缩、排序+去重实现、配合数据结构使用

将最优化问题转化为判定问题、实数二分、整数二分模板

求解 ax+by=gcd(a,b)，裴蜀定理，二元一次不定方程

扩展 GCD 求逆元、费马小定理求逆元、线性递推求 1~n 逆元

CRT 基本形式、扩展 CRT（EXCRT）

矩阵乘法、矩阵快速幂加速递推、构造转移矩阵

集合计数、二进制枚举子集实现容斥、Mobius 函数入门

φ(n) 定义与计算、欧拉定理、与积性函数的关系

期望 DP、马尔可夫链入门、概率生成函数入门

Nim 游戏、SG 函数、Sprague-Grundy 定理、公平组合博弈

Lucas 定理、卡特兰数、Burnside/Polya 计数入门

Miller-Rabin 素性测试、Pollard-Rho 因数分解

next 数组构建、KMP 匹配过程、循环节判定

多项式哈希、双哈希防冲突、哈希在子串匹配中的应用

Trie + 失配指针构建、多模式串匹配、AC 自动机上 DP

SA 构造（倍增法/O(nlogn)）、LCP 数组、后缀数组应用

O(n) 求最长回文子串、臂长概念、边界处理

PAM（Eertree）构建、本质不同回文串计数

最长上升子序列（LIS）、最长公共子序列（LCS）、数字三角形

0-1 背包、完全背包、多重背包、分组背包、混合背包

石子合并、矩阵链乘、戳气球，区间 DP 的枚举顺序

树上背包、树的直径、树的重心、换根 DP

基于位掩码的 DP、旅行商问题（TSP）、棋盘覆盖

含特定数字的数的统计、数位拆分技巧、记忆化搜索实现

单调队列优化、斜率优化（凸包 trick）、矩阵快速幂优化递推

破环为链、环形石子合并等经典问题

Dijkstra（堆优化）、SPFA、Floyd 算法原理、适用条件与复杂度对比

Kruskal 算法（并查集）、Prim 算法，最小生成树性质与应用

BFS/Kahn 算法、DFS 实现、DAG 判定、拓扑排序上的 DP

Tarjan 算法、Kosaraju 算法、缩点建新图

倍增法求 LCA、Tarjan 离线算法、树剖求 LCA

二分图判定（染色法）、匈牙利算法、Konig 定理

最大流（EK/Dinic 算法）、最小割、费用流、二分图匹配

将不等式组转化为图论最短/最长路问题

判定条件、Hierholzer 算法求欧拉回路

vector / deque / set / map / unordered_map / 优先队列等容器的底层结构直觉、时间复杂度、常用 API 与选择方法，附 bitset 入门

sort / lower_bound / unique / next_permutation / nth_element 等常用算法

用二进制视角看变量、bitset 打印与操作二进制位、枚举子集、lowbit、位运算 DP 前置技巧

函数模板、类模板基本概念，手写比较函数

基础并查集（路径压缩+按秩合并）、带权并查集、可撤销并查集

单点修改/区间查询、区间修改/区间查询（双树状数组），BIT 的本质

建树、单点/区间修改、区间查询、lazy 标记 pushdown、动态开点

RMQ 问题 O(1) 查询，倍增思想在 ST 表中的体现，局限性分析

字符 Trie 的构建与查询、01-Trie（最大异或）、Trie 上 DP

块状数组/块状链表思想，区间修改/查询的 sqrt 分解

Treap / Splay 的基本操作（插入/删除/查询排名），FHQ Treap

根据上下文推断缺失代码，理解算法意图，复杂程序补全

复杂递归/DFS/BFS 程序的手动模拟，STL 容器相关程序阅读