目录

zifuneko · 2025-07-07 10:56:44 · 个人记录

本篇文章是 \text{Zifu} 所有所写的算法专栏的目录，按时间排序，更新于 11/14/2025.

对于 11/14/2025 后撰写的文章，会出现繁体字来表示对算法的自身见解。

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.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}
  • 暴力标记法
  • 暴力上跳法
  • 倍增法

哈希 Hash

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

*最短路

• 最短路
  • 性质
  • \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 算法
• 总结