XMH 算法学习笔记与复习指南

学习周期：2026-05-10 ~ 2026-05-20 总题数：32 道 | 通过：31 道（96.9%）

---

📚 知识点分类总结

一、动态规划（DP）⭐⭐⭐⭐⭐

做题数量：15 道 | 通过率：93.3%

1.1 背包问题

完全掌握 ✅

已做题目：

• P497：完全背包（一次通过）
• P600：01背包变种（一次通过）
• P1523：多重背包（2次通过）
• P3917：完全背包计数（一次通过）
• P5955：完全背包（3次通过）
• P5956：多重背包二进制优化（5次通过）

核心知识点：

// 01背包（每个物品只能用一次）
for (int i = 1; i <= n; i++) {
    for (int j = m; j >= w[i]; j--) {  // 倒序枚举
        dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
    }
}

// 完全背包（每个物品可以用无限次）
for (int i = 1; i <= n; i++) {
    for (int j = w[i]; j <= m; j++) {  // 正序枚举
        dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
    }
}

// 多重背包二进制优化
// 将数量s拆分成 1, 2, 4, ..., 2^k, remainder
for (int k = 1; k <= s; k *= 2) {
    // 转化为01背包
    s -= k;
}

易错点：

• ❌ 01背包和完全背包的枚举顺序混淆
• ❌ 多重背包二进制优化后物品数量计算错误
• ❌ 数组开太小（特别是多重背包）

复习建议：

1. 熟记三种背包的模板代码
2. 重点掌握二进制优化的原理
3. 做题前先判断是哪种背包问题

---

1.2 线性DP

基本掌握 ⭐⭐⭐⭐

已做题目：

• P1229：资源分配问题（6次通过）
• P5354：线性DP（一次通过）
• P5356：线性DP（一次通过）
• P5358：线性DP（一次通过）
• P5365：最长上升子序列（一次通过）
• P5366：最长公共子序列（一次通过）
• P5375：DP问题（一次通过）
• P5376：回文串分割（一次通过）
• P5378：平均值最大（一次通过）

核心知识点：

// 最长上升子序列（LIS）
int ef(int x) {
    int l = 1, r = len, ans = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (f[mid] < x) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return ans;
}

// 资源分配问题（分组背包）
for (int i = n; i >= 1; i--) {  // 从后往前
    for (int j = 1; j <= m; j++) {
        for (int k = 0; k <= j; k++) {
            dp[i][j] = max(dp[i+1][j-k] + a[i][k], dp[i][j]);
        }
    }
}

易错点：

• ❌ 资源分配问题的转移顺序（从后往前）
• ❌ 初始化不完整（边界条件）
• ❌ 回溯路径时逻辑错误

复习建议：

1. 理解状态定义和转移方程
2. 画表格理解DP过程
3. 注意边界条件的初始化

---

二、图论算法 ⭐⭐⭐⭐

做题数量：8 道 | 通过率：100%

2.1 最短路径

完全掌握 ✅

已做题目：

• P5662：Dijkstra（一次通过）
• P5664：Dijkstra（一次通过）
• P5665：最短路（一次通过）
• P5972：最短路综合（3次通过）

核心知识点：

// Dijkstra算法
struct Edge {
    int to, w;
};
vector<Edge> e[MAXN];
int dis[MAXN], vis[MAXN];

void dijkstra(int s) {
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;

    priority_queue<pair<int,int>, vector<pair<int,int>>,
                   greater<pair<int,int>>> q;
    q.push({0, s});

    while (!q.empty()) {
        int u = q.top().second;
        q.pop();

        if (vis[u]) continue;
        vis[u] = 1;

        for (auto [to, w] : e[u]) {
            if (dis[to] > dis[u] + w) {
                dis[to] = dis[u] + w;
                q.push({dis[to], to});
            }
        }
    }
}

易错点：

• ❌ 判断无穷大：dis[i] == 0x3f3f3f3f → dis[i] > 0x3f3f3f3f/2
• ❌ 优先队列类型错误（大根堆 vs 小根堆）
• ❌ 无向边忘记存两次

复习建议：

1. 熟记Dijkstra模板
2. 理解为什么用优先队列
3. 注意无穷大的判断方式

---

2.2 最小生成树

完全掌握 ✅

已做题目：

• P3957：Kruskal（3次通过）
• P5989：Prim（一次通过）
• P5998：Kruskal（一次通过）

核心知识点：

// Kruskal算法（并查集）
struct Edge {
    int u, v, w;
} edges[MAXM];

bool cmp(Edge a, Edge b) {
    return a.w < b.w;
}

int fa[MAXN];
int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void kruskal() {
    sort(edges + 1, edges + m + 1, cmp);
    for (int i = 1; i <= n; i++) fa[i] = i;

    int cnt = 0, ans = 0;
    for (int i = 1; i <= m; i++) {
        int u = find(edges[i].u);
        int v = find(edges[i].v);
        if (u != v) {
            fa[u] = v;
            ans += edges[i].w;
            cnt++;
        }
        if (cnt == n - 1) break;
    }
}

// Prim算法
int dis[MAXN], vis[MAXN];
void prim(int s) {
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;

    for (int i = 1; i <= n; i++) {
        int u = 0;
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && dis[j] < dis[u]) {
                u = j;
            }
        }
        vis[u] = 1;
        for (auto [to, w] : e[u]) {
            if (!vis[to] && w < dis[to]) {
                dis[to] = w;
            }
        }
    }
}

易错点：

• ❌ 并查集路径压缩忘记写
• ❌ Kruskal忘记排序
• ❌ 判断图是否连通

复习建议：

1. 理解贪心思想
2. 熟记两种算法的区别
3. 注意判断图是否连通

---

2.3 拓扑排序

基本掌握 ⭐⭐⭐⭐

已做题目：

• P6784：拓扑排序（5次通过）

核心知识点：

int r[MAXN];  // 入度
vector<int> e[MAXN];

void toposort() {
    priority_queue<int, vector<int>, greater<int>> q;
    for (int i = 1; i <= n; i++) {
        if (r[i] == 0) q.push(i);
    }

    while (!q.empty()) {
        int u = q.top();
        q.pop();
        cout << u << " ";

        for (int v : e[u]) {
            r[v]--;
            if (r[v] == 0) q.push(v);
        }
    }
}

易错点：

• ❌ 用队列还是优先队列（看题目要求）
• ❌ 入度为0的点忘记加入队列
• ❌ q.top() 还是 q.front()（优先队列用top）

复习建议：

1. 理解拓扑排序的应用场景
2. 掌握入度的维护
3. 注意队列类型的选择

---

三、排序算法 ⭐⭐⭐

做题数量：3 道 | 通过率：66.7%

3.1 归并排序

需要加强 ⚠️

已做题目：

• P5322：归并排序求逆序对（7次通过）

核心知识点：

int a[MAXN], c[MAXN];
long long ans = 0;

void merge(int l, int r) {
    if (l == r) return;

    int mid = (l + r) / 2;
    merge(l, mid);
    merge(mid + 1, r);

    int p1 = l, p2 = mid + 1, cnt = 0;
    while (p1 <= mid && p2 <= r) {  // 注意：p1 <= mid
        if (a[p1] > a[p2]) {
            ans += r - p2 + 1;  // 逆序对数量
            c[++cnt] = a[p1++];
        } else {
            c[++cnt] = a[p2++];
        }
    }
    while (p1 <= mid) c[++cnt] = a[p1++];
    while (p2 <= r) c[++cnt] = a[p2++];

    for (int i = 1; i <= cnt; i++) {
        a[l + i - 1] = c[i];
    }
}

易错点：

• ❌ 边界条件：while (p1 <= mid) 不是 while (p1 <= l)
• ❌ 逆序对计算：ans += r - p2 + 1
• ❌ 归并后的数组赋值

复习建议：

1. 手动模拟归并过程
2. 熟记边界条件
3. 理解逆序对的计算方式

---

四、基础算法 ⭐⭐⭐⭐

做题数量：6 道 | 通过率：83.3%

4.1 二分查找

基本掌握 ⭐⭐⭐⭐

已做题目：

• P5362：二分查找（一次通过）
• P5363：二分查找（一次通过）
• P5364：二分答案（一次通过）

核心知识点：

// 二分查找
int ef(int x) {
    int l = 1, r = n, ans = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (a[mid] == x) {
            ans = mid;
            r = mid - 1;  // 找第一个出现的位置
        } else if (a[mid] < x) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return ans;
}

// 二分答案
bool check(int x) {
    // 判断x是否可行
}

int solve() {
    int l = 1, r = 1e9;
    while (l < r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

易错点：

• ❌ 边界条件：while (l <= r) 还是 while (l < r)
• ❌ 更新方式：l = mid + 1 还是 l = mid
• ❌ 返回值：l 还是 r

复习建议：

1. 理解二分的本质
2. 根据题目确定边界条件
3. 多练习二分答案类题目

---

📊 知识点掌握程度总览

知识点          做题数  通过率  掌握程度
────────────────────────────────────────
动态规划-背包    6道    100%    ⭐⭐⭐⭐⭐ 完全掌握
动态规划-线性    9道    100%    ⭐⭐⭐⭐☆ 熟练掌握
图论-最短路      4道    100%    ⭐⭐⭐⭐⭐ 完全掌握
图论-最小生成树  3道    100%    ⭐⭐⭐⭐⭐ 完全掌握
图论-拓扑排序    1道    100%    ⭐⭐⭐⭐☆ 基本掌握
排序-归并排序    1道    100%    ⭐⭐⭐☆☆ 需要加强
基础-二分查找    3道    100%    ⭐⭐⭐⭐☆ 基本掌握

---

💡 高效复习建议

第一周：巩固基础

重点复习：

1. 背包问题（每天1题）

   • P497, P600, P1523, P3917, P5955, P5956
   • 目标：能快速判断背包类型并写出代码

2. 归并排序（重点突破）

   • P5322
   • 目标：熟记边界条件，理解逆序对计算

学习方法：

• 先看模板代码，理解原理
• 关上书本，自己实现一遍
• 对比差异，找出问题

---

第二周：提升能力

重点复习：

1. 图论算法（每天1题）

   • P5662, P5664, P5972（最短路）
   • P3957, P5989, P5998（最小生成树）
   • P6784（拓扑排序）

2. 线性DP（每天1题）

   • P5365（LIS）
   • P5366（LCS）
   • P1229（资源分配）

学习方法：

• 先思考状态定义
• 再写转移方程
• 最后实现代码

---

第三周：查漏补缺

重点复习：

1. 错题重做

   • P5322（归并排序）
   • P1229（资源分配）
   • P5956（多重背包）
   • P6784（拓扑排序）

2. 未通过题目

   • P2600（背包问题）

学习方法：

• 看之前的错误代码
• 找出错误原因
• 重新实现正确代码

---

📝 算法模板速记卡

背包问题

01背包：倒序枚举 j--
完全背包：正序枚举 j++
多重背包：二进制优化（1,2,4,...,2^k,rem）

图论算法

Dijkstra：优先队列 + 松弛操作
Kruskal：排序 + 并查集
Prim：每次选最小边
拓扑排序：入度 + 队列

排序算法

归并排序：分治 + 合并
边界条件：p1 <= mid（不是 p1 <= l）
逆序对：ans += r - p2 + 1

二分查找

查找：while (l <= r)
答案：while (l < r)
更新：l = mid + 1 或 l = mid

---

🎯 学习目标

短期目标（2周内）

• [ ] 归并排序达到一次通过
• [ ] 完成P2600题目
• [ ] 所有模板能默写出来

中期目标（1个月）

• [ ] 背包问题10分钟内完成
• [ ] 图论题目15分钟内完成
• [ ] 一次通过率达到50%

长期目标（3个月）

• [ ] 学习区间DP、状压DP
• [ ] 学习网络流、强连通分量
• [ ] 学习线段树、树状数组

---

📌 重点提示

考试/比赛注意事项

提交前必查：

□ 代码能编译吗？
□ 测试样例通过了吗？
□ 数组开够大了吗？
□ 输出格式对吗？（换行、空格）
□ 有调试输出没删吗？
□ 边界条件处理了吗？

常见错误速查：

编译错误：检查分号、大括号、变量声明
答案错误：检查输出格式、边界条件、初始化
输出超限：检查数组大小、循环终止条件
运行错误：检查数组越界、空指针