第 12 讲 · 实战

洛谷题单:例题与作业

看懂和写出来之间隔着一道道题。这一讲给第 02~08、10~13 讲每讲配 2~4 道最经典的洛谷题, 难度只保留「入门」和「普及−」,每讲内部由易到难排好。每题都给出「考点 → 思路 → 容易踩的坑」, 第 09 讲暂无符合这两个难度的题。

共 30 题(含入门 / 普及−) 平台:洛谷 luogu.com.cn 关键词:经典题 · 由易到难
关于题号与难度(请务必先读) 本讲所有题号、题名与难度标签都在 2026 年 9 月逐题到洛谷上核对过,点题号可直接打开题目页。 洛谷的难度标签会随评定调整,以后如果看到的颜色和这里不一样,以站内为准; 万一题号打不开,用表格里的中文题名在站内搜索即可。 做题时请以站内的实际题面、数据范围与时空限制为准。

12.1 怎么用这份题单

三步做题法

  1. 先读题、定算法:看数据范围反推复杂度。 例如 n ≤ 1000 允许 O(n²),n ≤ 10⁵ 只允许 O(n log n),n ≤ 20 可以考虑搜索。
  2. 手推小样例:自己造一组 3~5 个元素的数据,用纸笔跑一遍自己的算法,确认逻辑无误再写代码。
  3. 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 讲 · 图的存储与遍历

题号题目难度考点思路提示
P1596Lake 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)记录见过的数,第一次见到才输出。数值可能为负、范围很大,不能直接当数组下标。多组数据,每组开始前要清空。
P1102A−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 本章小结

做题时的三个自问

  1. 数据范围允许什么复杂度?我现在写的是这个量级吗?
  2. 这个算法在最优/最坏/特殊输入(全相同、已排序、完全图)下会退化吗?
  3. 如果 WA 了,我的程序状态和课件动画里的状态从第几步开始不一样?

推荐刷题节奏

  • 每天 1~2 题,比周末突击 10 题有效得多。
  • 一题最多卡 40 分钟。超时就去看题解,但看完必须合上题解重写一遍。
  • 每题 AC 后在代码里写一行注释:这题的关键结论是什么。一个月后回看,这就是你自己的速查表。
  • 定期做「重做旧题」:只重做那些当时看了题解的题。