📚 编程复习笔记

2026年6月12日 — 6月16日

---

💡 阅读指南：每个知识点按 题型归类 → 核心思路 → 易错提醒 排列，重点标注 ⚠️ 和口诀 🎯 帮助快速回忆。

---

🔵 专题一：最短路算法（本周核心）

这是最重要的专题，务必彻底掌握！

📌 1.1 Dijkstra 算法 — 单源最短路（正权边）

涉及题目：P233 最短路径 I、P619 【模板】最短路-Dij堆优化、P1496 最短路计数

🎯 核心口诀：「贪心取最小，松弛更新邻」

算法步骤：
1. 初始化 dist[起点] = 0，其余 = ∞
2. 每次取出未访问中 dist 最小的点 u
3. 用 u 去松弛所有邻居 v：if dist[u] + w < dist[v] → 更新
4. 标记 u 已访问，重复直到所有点处理完

⚠️ 易错点：

错误	正确做法
用普通数组找最小值 → O(n²) 超时	用优先队列（小根堆） → O((n+m)logn)
处理重边时只存一条	存所有边，算法自动选最短
自环边直接忽略	正权自环不影响结果，可以不管
忘记 long long	边权可达 10⁹，路径可达 10¹⁴，必须 long long
堆中过期数据不跳过	if (d > dist[u]) continue; 跳过旧记录

📝 Dij 堆优化模板：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> pli;
const ll INF = 1e18;

int main() {
    int N, M; cin >> N >> M;
    vector<vector<pair<int,int>>> g(N+1);
    for (int i = 0; i < M; i++) {
        int a, b, c; cin >> a >> b >> c;
        g[a].push_back({b, c});
        g[b].push_back({a, c}); // 无向图
    }
    vector<ll> dist(N+1, INF);
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    dist[1] = 0; pq.push({0, 1});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue; // 过期数据跳过
        for (auto [v, w] : g[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    cout << dist[N] << endl;
}

---

📌 1.2 最短路计数

涉及题目：P1496 最短路计数

🎯 核心思路：在 BFS/Dij 过程中，顺便统计路径数

关键逻辑：
- if dist[u] + w < dist[v]:  cnt[v] = cnt[u]    // 发现更短路，重置计数
- if dist[u] + w == dist[v]: cnt[v] += cnt[u]   // 等长路径，累加计数

⚠️ 易错点：

• 无权图用 BFS，有权图用 Dij
• 结果对 100003 取模，但比较距离时不要取模
• 重边会产生多条等长路径，不要去重

---

📌 1.3 最短距离和路径问题

涉及题目：P2530 最短距离和路径问题

🎯 核心思路：Dij + 记录前驱，路径字典序最小

记录路径方法：
1. 用 pre[] 数组记录每个点的前驱
2. 字典序最小：松弛时，如果 dist 相同，比较路径字典序
3. 技巧：按编号从小到大遍历邻居即可

⚠️ 本题卡点：

• TLE 可能是输出路径时用了递归，大数据栈溢出 → 用迭代回溯
• WA 可能是字典序处理不对 → 同距离时选编号更小的前驱
• 多条边要全部存储，不能只保留最短的

---

🟢 专题二：贪心算法

📌 2.1 合并果子（哈夫曼编码思想）

涉及题目：P2236 【基础】合并果子

🎯 核心口诀：「每次合并最小的两堆」

算法：用小根堆（优先队列）
1. 所有果子重量放入小根堆
2. 每次取出最小的两个 a, b
3. 合并耗费 a+b，把 a+b 放回堆中
4. 累加耗费，重复直到堆中只剩一堆

priority_queue<int, vector<int>, greater<int>> pq;
// 读入所有重量 push 进 pq
int total = 0;
while (pq.size() > 1) {
    int a = pq.top(); pq.pop();
    int b = pq.top(); pq.pop();
    total += a + b;
    pq.push(a + b);
}
cout << total << endl;

💡 为什么这样最优？ 贪心证明：每次让最小的先合并，避免大的数被重复计算。

---

🟡 专题三：思维/构造题

📌 3.1 你的名字 — 字符串重排判定

涉及题目：P7220 你的名字

🎯 核心思路：判断两个字符串是否为字母异位词

只需统计两个字符串中每个字母的出现次数是否完全相同。
排序后比较 / 计数数组比较 都可以。

sort(s.begin(), s.end());
sort(t.begin(), t.end());
cout << (s == t ? "YES" : "NO") << endl;

---

📌 3.2 平移 MEX

涉及题目：P7252 平移 MEX

🎯 核心思路：选择偏移量 x，使得 MEX 最大

MEX 定义：数组中没出现的最小非负整数
关键观察：平移 x 后，数组变成 {a₁+x, a₂+x, ..., aₙ+x}
我们要选 x，使得 0,1,2,...,k-1 都出现，而 k 不出现

⚠️ 易错点：

• x 可以为负数！不要只考虑 x ≥ 0
• 枚举可能的 MEX 值 k，检查是否存在 x 使 0~k-1 都出现
• 时间复杂度 O(n²)，n ≤ 3000 可以接受

---

📌 3.3 内存溢出错误

涉及题目：P7253 内存溢出错误

🎯 核心思路：模拟操作，遇到溢出则重置

1. 逐个执行操作
2. 每次操作后检查是否越界（a[bᵢ] > h）
3. 如果越界 → 重置数组为初始值
4. 继续执行后续操作（不会回退到之前已执行的操作）

⚠️ 易错点：

• 重置后继续执行后面的操作，不是从头开始！
• 注意是 a[bᵢ] 越界，不是 cᵢ 越界

---

📌 3.4 兑换硬币

涉及题目：P1651 【入门】兑换硬币

🎯 核心思路：枚举 + 数学

1元 = 100分，每种至少1枚
a + 2b + 5c = 100, a,b,c ≥ 1
→ (a-1) + 2(b-1) + 5(c-1) = 100 - 1 - 2 - 5 = 92
设 a'=a-1, b'=b-1, c'=c-1，则 a' + 2b' + 5c' = 92, a',b',c' ≥ 0
枚举 c' 从 0 到 18，对每个 c' 枚举 b' 即可

---

🔴 高频错误模式总结

错误类型	典型表现	解决方法
算法选择错误	最短路用 Floyd 超时	10⁵ 级别用 Dij 堆优化
数据类型溢出	用 int 存路径长度	边权 10⁹ × 10⁵ → 必须 long long
重复提交不改思路	同一题连续 TLE/WA	换思路，不要只改细节
边界条件遗漏	重边、自环、空图	写代码前先想边界

---

📋 复习检查清单

• [ ] 能手写 Dijkstra 堆优化版本
• [ ] 理解最短路计数的转移方程
• [ ] 知道路径记录和字典序最小怎么处理
• [ ] 掌握哈夫曼/合并果子的贪心策略
• [ ] 理解 MEX 的定义和构造方法
• [ ] 模拟题注意"重置后继续"的逻辑
• [ ] 所有最短路题目检查是否需要 long long