为什么写这篇笔记
加入 ACM 集训队后，我逐渐意识到算法训练不是刷题数量的堆砌，而是对问题本质的理解与模式识别能力的积累。这篇笔记记录我的训练路径和踩过的坑。
训练路线
第一阶段：基础数据结构
- 数组、链表、栈、队列
- 哈希表、集合
- 二叉树、堆
第二阶段：经典算法
动态规划
动态规划的核心是状态定义与状态转移。常见类型：
// 01 背包
int dp[1005][1005];
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= W; j++) {
dp[i][j] = dp[i-1][j];
if (j >= w[i]) dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i]);
}
}
图论
| 算法 | 时间复杂度 | 适用场景 |
|---|---|---|
| Dijkstra | O((V+E)logV) | 单源最短路，非负权 |
| Bellman-Ford | O(VE) | 可检测负环 |
| Floyd | O(V³) | 全源最短路 |
| SPFA | 平均 O(E) | 稀疏图优化 |
第三阶段：高级算法
- 线段树与树状数组
- 网络流
- 字符串算法（KMP、后缀数组）
心得
- 不要只抄题解 — 先独立思考 30 分钟
- 建立错题本 — 记录 WA 的原因和思维盲区
- 定期复盘 — 每周回顾做过的题目，总结模式
下一步
继续深入字符串算法和计算几何，准备区域赛。