第 12 讲 · 实战
洛谷题单:例题与作业
看懂和写出来之间隔着一道道题。这一讲给第 02~08、10~13 讲每讲配 2~4 道最经典的洛谷题,
难度只保留「入门」和「普及−」,每讲内部由易到难排好。每题都给出「考点 → 思路 → 容易踩的坑」,
第 09 讲暂无符合这两个难度的题。
共 30 题(含入门 / 普及−)
平台:洛谷 luogu.com.cn
关键词:经典题 · 由易到难
关于题号与难度(请务必先读)
本讲所有题号、题名与难度标签都在 2026 年 9 月逐题到洛谷上核对过,点题号可直接打开题目页。
洛谷的难度标签会随评定调整,以后如果看到的颜色和这里不一样,以站内为准;
万一题号打不开,用表格里的中文题名在站内搜索即可。
做题时请以站内的实际题面、数据范围与时空限制为准。
12.1 怎么用这份题单
三步做题法
- 先读题、定算法:看数据范围反推复杂度。
例如
n ≤ 1000 允许 O(n²),n ≤ 10⁵ 只允许 O(n log n),n ≤ 20 可以考虑搜索。
- 手推小样例:自己造一组 3~5 个元素的数据,用纸笔跑一遍自己的算法,确认逻辑无误再写代码。
- WA 了先自己调试:把中间变量打印出来,用课件里的动画对照「程序的状态变化」和「算法的正确状态变化」差在哪一步。
必备的自查习惯
- 数组开够了吗? 无向图的边数组要开
2 * m;下标从 1 开始时数组要多开 1 位。
- 初始值对吗? 求最小值时
INF 够大吗?求最大值时负无穷设了吗?
- 会不会爆 int? 看到乘法、求和、计数,先想
long long。
- 边界处理了吗? n = 1、空串、只有一条边的图。
- 多组数据清空了吗? 全局数组、
vector、栈和队列都要重置。
难度标签与排列顺序
本题单只保留洛谷的两档:
入门
普及−。
每讲的题都已经由易到难排好:先按难度标签从低到高;同一档里,按洛谷上的通过率从高到低
(通过率越高,通常越好上手)。建议按顺序做,一道题卡住超过 40 分钟再看思路提示。
12.2 第 02 讲 · 线性表
| 题号 | 题目 | 难度 | 考点 | 思路提示 |
| P3156 | 询问学号 | 入门 | 顺序表的随机存取 |
把学号按进教室的顺序存进数组,第 i 个同学就是 a[i]——这正是顺序表 O(1) 按位访问。n 到 2×10⁶,读入要快(关闭同步流或用 scanf)。 |
| P1996 | 约瑟夫问题 | 普及− | 循环链表 |
用数组模拟循环链表:nxt[i] 指向下一个人,最后一个人指回 1。数到第 m 个人就把他从环里摘掉(改他前一个人的 nxt)。也可以用第 04 讲的队列:出队,没数到 m 就重新入队。 |
| B3631 | 单向链表 | 普及− | 静态链表:插入与删除 |
元素值 ≤ 10⁶ 且互不相同,可以直接用值当下标:nxt[x] 存 x 后面的元素。把 y 插到 x 后面:nxt[y] = nxt[x]; nxt[x] = y;(先连后断);删除 x 的后继:nxt[x] = nxt[nxt[x]];。 |
12.3 第 03 讲 · 栈
| 题号 | 题目 | 难度 | 考点 | 思路提示 |
| P1739 | 表达式括号匹配 | 入门 | 括号匹配 |
第 03 讲的括号匹配。因为只有一种括号,其实用一个计数器就够了:遇到 ( 加一、遇到 ) 减一,中途一旦变成负数就已经不匹配;如果扩展到三种括号就必须用栈。 |
| P1449 | 后缀表达式 | 普及− | 栈求后缀表达式 |
题目用 . 分隔操作数、@ 结束。遇到数字就入栈,遇到运算符就弹出两个数计算后再入栈。注意「先弹出的是右操作数」——减法和除法顺序别反。 |
12.4 第 04 讲 · 队列
| 题号 | 题目 | 难度 | 考点 | 思路提示 |
| B3616 | 【模板】队列 | 普及− | 队列的基本操作 |
先用数组 + front / rear 两个下标手写一遍,再用 std::queue 写一遍对比。队列为空时出队、取队首要按题目输出错误信息,不能越界访问。 |
| P1540 | 机器翻译 | 普及− | 队列 + 标记数组 |
典型 FIFO 场景:内存满时淘汰最早进入的单词。用 queue 配一个布尔数组记录「是否在内存中」。 |
12.5 第 05 讲 · 串
| 题号 | 题目 | 难度 | 考点 | 思路提示 |
| P5015 | 标题统计 | 入门 | 串的读入与遍历 |
标题里可能有空格,要整行读入(getline),再遍历字符串,跳过空格和换行计数。热身题,练习串的读入。 |
| P1308 | 统计单词数 | 普及− | 朴素模式匹配 |
不区分大小写:先把单词和文章都转成小写。要求「完整单词」匹配:在单词和文章的两边各补一个空格再查找,就不会匹配到别的单词的一部分(位置要换算回原文)。位置从 0 开始,找不到输出 -1。 |
12.6 第 06 讲 · 数组与矩阵
| 题号 | 题目 | 难度 | 考点 | 思路提示 |
| P5732 | 杨辉三角 | 入门 | 二维数组 / 下三角 |
a[i][j] = a[i−1][j−1] + a[i−1][j],只用到下三角部分。进阶:用第 06 讲下三角矩阵的压缩公式,把它存进一维数组再输出。 |
| P5731 | 蛇形方阵 | 入门 | 二维数组的下标控制 |
按「右、下、左、上」四个方向循环填数,走到边界或已经填过的格子就转向。每个数占 3 个字符宽,用 printf("%3d", …) 对齐。 |
| B2105 | 矩阵乘法 | 普及− | 二维数组 / 三重循环 |
按定义 C[i][j] = Σ A[i][t] · B[t][j],三重循环 O(nmk)。元素绝对值 ≤ 1000、m ≤ 100,结果不超过 10⁸,int 够用;C 要先清零。 |
12.7 第 07 讲 · 树与二叉树
| 题号 | 题目 | 难度 | 考点 | 思路提示 |
| P1030 | 求先序排列 | 普及− | 中序 + 后序 → 先序 |
后序的最后一个字符是根;在中序里找到它来划分左右子树,递归处理。先输出根,再递归左、右子树,就是先序。注意子串边界。 |
| P4913 | 二叉树深度 | 普及− | 二叉树的存储与遍历 |
用两个数组 l[i]、r[i] 存左右孩子,从根 1 递归:depth(u) = max(depth(l[u]), depth(r[u])) + 1,空结点深度为 0。树退化成链时递归会很深,本机调试可能爆栈;也可以改用层序遍历数层数。 |
12.8 第 08 讲 · 图的存储与遍历
| 题号 | 题目 | 难度 | 考点 | 思路提示 |
| P1596 | Lake Counting | 普及− | 连通分量(DFS) |
把每个 W 看成顶点,八个方向相邻的 W 之间有边。逐格扫描,遇到没访问过的 W 就从它出发 DFS / BFS 把整片水塘标记掉,答案加一——这就是「数连通分量」。 |
| B3643 | 图的存储 | 普及− | 邻接矩阵 + 邻接表 |
同一张无向图分别存成邻接矩阵(g[u][v] = g[v][u] = 1)和邻接表(vector<int> adj[N],两个方向都要加)。邻接表输出前,要把每个点的邻居排好序。 |
| P5318 | 查找文献 | 普及− | DFS / BFS 遍历 |
要求按编号从小到大访问邻接点——所以邻接表里每个点的邻居要先排序。这是最容易 WA 的点。注意这是有向图。 |
12.9 第 09 讲 · 图论算法
本讲暂无符合难度的题
原题单里的拓扑排序 / 关键路径、Floyd、最小生成树、Dijkstra 模板题都是「普及/提高−」,
已按要求删除。建议先用第 09 讲的动画和手推练习;等难度上调后,再回来做洛谷模板题。
12.10 第 10 讲 · 查找与哈希
| 题号 | 题目 | 难度 | 考点 | 思路提示 |
| P3370 | 【模板】字符串哈希 | 普及− | 字符串哈希 |
用多项式哈希 h = h · base + c 把每个字符串映射成整数(base 取 131 之类的数,用 unsigned long long 自然溢出,或者用双模数更稳),排序后数一数有几个不同的值。 |
| P2249 | 查找 | 普及− | 折半查找(找第一个) |
序列单调不减,要找第一次出现的位置:二分时 a[mid] ≥ q 就往左收缩,最后检查找到的位置是否等于 q。等价于 lower_bound。n 到 10⁶,读入要快。 |
| P4305 | 不重复数字 | 普及− | 哈希表去重 |
按顺序扫描,用哈希表(unordered_set)记录见过的数,第一次见到才输出。数值可能为负、范围很大,不能直接当数组下标。多组数据,每组开始前要清空。 |
| P1102 | A−B 数对 | 普及− | 哈希计数 / 二分 |
A = B + C:先用 map(或 unordered_map)统计每个数出现的次数,再对每个 B 累加 cnt[B + C]。也可以排序后用 upper_bound − lower_bound 数个数。答案可能超过 int,用 long long。 |
12.11 第 11 讲 · 排序
| 题号 | 题目 | 难度 | 考点 | 思路提示 |
| P1059 | 明明的随机数 | 普及− | 排序 + 去重 |
sort + unique + erase 三连,或直接用 set。数值只在 1~1000 之间,也可以开一个标记数组,从小到大扫一遍就得到有序且去重的结果。 |
| P1093 | 奖学金 | 普及− | 多关键字排序 |
自定义比较函数:总分降序 → 语文降序 → 学号升序。三个关键字都写进比较函数,排序结果就是唯一的。只输出前 5 名。 |
| P1177 | 【模板】排序 | 普及− | O(n log n) 排序 |
n 到 10⁵,冒泡、选择这类 O(n²) 排序会超时。用它来亲手实现第 11 讲的快速排序、归并排序或堆排序。手写快排要随机选基准,并处理好大量相同元素的情况,否则会退化成 O(n²)。 |
12.12 本章小结
做题时的三个自问
- 数据范围允许什么复杂度?我现在写的是这个量级吗?
- 这个算法在最优/最坏/特殊输入(全相同、已排序、完全图)下会退化吗?
- 如果 WA 了,我的程序状态和课件动画里的状态从第几步开始不一样?
推荐刷题节奏
- 每天 1~2 题,比周末突击 10 题有效得多。
- 一题最多卡 40 分钟。超时就去看题解,但看完必须合上题解重写一遍。
- 每题 AC 后在代码里写一行注释:这题的关键结论是什么。一个月后回看,这就是你自己的速查表。
- 定期做「重做旧题」:只重做那些当时看了题解的题。