书: https://pan.baidu.com/s/1LWWovU7IScpiddLrDhjl1w?pwd=pc5n
笔记如下：
- 算法复杂度分析：大O表示法（O(n), O(n log n), O(n²)）的实际意义与最坏/平均情况评估
- 基础数据结构应用：数组、链表、栈、队列的典型问题（如滑动窗口最大值用双端队列实现）
- 分治算法模板：
- 归并排序的逆序对计数应用
- 快速选择算法（Quickselect）找第k小元素
- 贪心算法证明技术：
- 区间调度问题（最早截止时间优先）
- 霍夫曼编码的构造与正确性
- 动态规划四要素：
- 状态定义（如dp[i][j]表示子问题解）
- 转移方程（递推关系）
- 初始化边界条件
- 空间优化（滚动数组）
- 经典DP问题：
- 背包问题（01/完全/多重背包）
- 最长公共子序列（LCS）
- 编辑距离（Levenshtein Distance）
- 图论基础算法：
- DFS/BFS的迭代与递归实现
- 拓扑排序（Kahn算法与DFS版本）
- 连通分量（Tarjan算法）
- 最短路径实战：
- Dijkstra算法（优先队列优化）
- Bellman-Ford检测负权环
- Floyd-Warshall全源最短路
- 最小生成树：
- Kruskal算法（并查集优化）
- Prim算法（堆实现）
- 并查集高级技巧：
- 路径压缩与按秩合并
- 带权并查集（维护附加信息）
- 字符串匹配算法：
- KMP的next数组预处理
- Rabin-Karp滚动哈希
- Trie树处理多模式匹配
- 数学相关算法：
- 欧几里得算法（GCD/LCM）
- 筛法求素数（埃氏筛/线性筛）
- 快速幂与矩阵快速幂
- 计算几何基础：
- 点积/叉积判断相对位置
- 凸包算法（Graham扫描）
- 最近点对问题（分治解法）
- 高级数据结构：
- 线段树（区间查询/更新）
- 树状数组（Fenwick Tree）
- 跳表（Skip List）实现
- 网络流模型：
- Ford-Fulkerson最大流
- Edmonds-Karp实现
- 二分图匹配转化
- NP难问题近似算法：
- 旅行商问题（TSP）的2-近似算法
- 集合覆盖的贪心解法
- 位运算优化：
- 状态压缩DP（如n皇后问题）
- 快速统计二进制1的个数
- 输入输出优化：
- C++的ios::sync_with_stdio(false)
- Java的BufferedReader提速
- 竞赛调试技巧：
- 对拍程序验证正确性
- 边界数据生成（极值/特殊case）
- 代码模板管理：
- 预编写常用算法模板
- 标准化输入输出处理