STL总结

• $\text{1 vector}$
• $\text{2 stack}$
• $\text{3 queue}$
• $\text{4 priority\_queue}$
• $\text{5 set}$
• $\text{6 map}$
• $\text{7 string}$
• $\text{8 pair}$
• $\text{9 algorithm}$
  • $\text{9.1 swap()}$
  • $\text{9.2 sort()}$
  • $\text{9.3 lower\_bound() / upper\_bound()}$
  • $\text{9.4 reverse()}$
  • $\text{9.5 max() / min()}$
  • $\text{9.6 unique()}$
  • $\text{9.7}$ 数学函数
  • $\text{9.8 gcd() / lcm()}$
  • $\text{9.9 iota()}$
  • $\text{9.10 next\_permutation()}$
  • $\text{9.11 max\_element()}$
• 代码

前缀和、差分、离散化与堆

• 前缀和
  • 前缀和的定义
  • 使用前缀和的方法
  • 二维前缀和
• 差分
  • 差分的定义
  • 使用差分的方法
• 离散化
• 堆

倍增

• 归并排序
• 快速幂
• 慢速乘
• 逆元
• RMQ
  • 表示区间最大（最小）值的问题。
  • ST表

C++基础及技巧

• $\text{inline}$
• $\text{main()}$
• 注释
• $\text{printf \& scanf}$
  • 转义字符
  • 取址运算符
• $\text{define}$
• $\text{typedef}$
• $\text{fixed}\ \&\ \text{setprecision}$
  • $\text{fixed}$
  • $\text{setprecision}$
  • 组合使用 $\text{fixed}$ 和 $\text{setprecision}$
• 加快 $\text{cin}$、$\text{cout}$ 运行效率
  • $\text{ios::sync\_with\_stdio(false)}$
  • $\text{tie}$

*动态规划 DP

• 基础
  • 引入
  • 原理
  • 记忆化搜索
• 背包 DP
  • 01 背包
    • 状态转移方程
    • 滚动数组优化
  • 完全背包
  • 多重背包
    • 朴素实现
    • 二进制分组优化
  • 混合背包
  • 二维费用背包
  • 分组背包
  • 有依赖背包
• 状压 DP
• 树形 DP
  • 引入题目
  • P1122 最大子树和
  • P2016 战略游戏
• 树上 DP

最近公共祖先 LCA

• $\text{LCA}$
  • 暴力标记法
  • 暴力上跳法
  • 倍增法
• $\text{Tarjan}$ 算法
• $\text{LCA}$ 的性质
• $\text{DFS}$ 序与欧拉序

哈希 Hash

• 哈希
• 哈希的特性
• 求字符哈希

*最短路

• 最短路
  • 性质
  • $\text{Dijkstra}$
    • 松弛操作
    • 过程
    • $\text{Dijkstra}$ 朴素实现
    • $\text{Dijkstra}$ 优先队列维护
  • $\text{Bellman Ford}$
    • $\text{SPFA}$
  • $\text{Floyd}$
    • 实现

逆元

• 乘法逆元的定义
• 费马小定理
• 扩展欧几里得
  • 基本原理
  • 步骤
• 乘法逆元的作用
  • 求解模线性同余方程
  • 计算分数的模运算
• 代码
  • 费马小定理 + 快速幂
  • 扩展欧几里得
  • 线性求 ${1-n}$ 逆元
  • 线性求 $1-n$ 逆元（妙招）
  • 线性求 $\text{val}_1,\text{val}_2,...,\text{val}_n$ 逆元
• 总结

*并查集

• 并查集三件套
  • $\text{find()}$
  • $\text{merge()}$
  • $\text{init()}$
• 优化
  • 按高度合并
  • 按大小合并
• 并查集扩展
  • 扩展域并查集
  • 带权并查集

*树状数组与线段树

• 树状数组
  • 前言
  • 正文
    • 使用 $\text{lowbit}$
    • 树状数组的子节点与父节点
    • 单点修改
    • 区间查询
    • 区间修改，单点查询
    • 区间修改，区间查询
    • 权值树状数组
• 线段树
  • 前言
  • 性质
    • 线段树的性质
    • 线段树的灵魂：$\text{Lazy tag}$
  • 区间修改，区间查询
    • $\text{MakeTag}$
    • $\text{PushDown}$
    • 完整代码
  • 区间加法，区间乘法，区间查询
    • 具体方法
    • 变量含义
    • 注意事项
    • 完整代码
  • 线段树维护最大子段和
    • 变量含义
    • $\text{PushUp}$
    • 完整代码（注释多）
• 总结

莫队

• 莫队
  • 普通莫队
  • 带修莫队
  • 回滚莫队

单调队列与单调栈

• 单调队列
  • deque
    • 元素访问
    • 元素增删及修改
  • 单调队列模版
  • 单调队列与DP结合
• 单调栈

强连通分量 SCC

• 定义
• kosaraju 算法
  • 正向图中搜索得到包含所有店的后序遍历
  • 将序列反转，依次在反图中进行强连通分量标记
  • kosaraju 主体
  • 缩点
  • 正确性证明
• Tarjan 算法

+树 Tree

• 定义
• 树的序列化

最小生成树 MST

• Kruskal
• Prim
• 後記

拓扑排序 Topo

• 定义
• Kahn 算法
• DFS 算法
• 总结