提高组(CSP-S)

提高组(CSP-S)

学习规划与参考资料
数据结构
- 并查集 - 处理不交集的合并和查询
- 区间问题相关数据结构
  - 线段树 - 维护区间信息
  - 树状数组(可选) - 单点/区域修改、单点/区域查询
  - ST表(可选) - 可重复贡献问题
- 单调队列 - 复用具有单调性的计算结果
- 单调栈 - 类似单调队列
图论
- 单源最短路
  - Dijkstra - 一点到所有点的最短路（非负权）
  - SPFA和Bellman-Ford - 一点到所有点的最短路（可能有负权）
  - 差分约束 Differential Constraints - 转化成SPFA看是否有负环
- 所有点间最短路
  - Floyd-Warshall - 所有点之间的最短路
- 生成树
  - 最小生成树
  - 最小瓶颈树
- 树上问题
  - LCA最低公共祖先 - 通过倍增快速求解
  - 树的遍历 - 树的DFS遍历及相关技巧
  - 树上差分
  - 树的重心
- 拓扑排序
- 最大流
- 强连通分量 Strongly Connected Components

DP
其它方法
数学
- 数论
- 模与相关运算
- 排列组合
- 解析几何
其它资源
- ★USACO Gold近年真题★
- 洛谷题单广场
- Studying Father的NOI题单 (2020)
- 洛谷上的USACO题目，其中training部分来自于USACO Training