洛谷罗勇军《算法竞赛》题单

洛谷罗勇军《算法竞赛》题单（洛谷）

本题单共收录 10 个子题单、696 个题目条目、682 道不同题目。

其中有 14 道题出现在多个学习阶段，形成 14 个重复条目。这些条目按洛谷原分组保留，并共享完成进度。

题目按洛谷书籍题单的子题单顺序排列。

怎么看小节里的图
基础数据结构 - 罗勇军《算法竞赛》
基本算法 - 罗勇军《算法竞赛》
搜索 - 罗勇军《算法竞赛》
高级数据结构 - 罗勇军《算法竞赛》
动态规划 - 罗勇军《算法竞赛》
数论和线性代数 - 罗勇军《算法竞赛》
组合数学 - 罗勇军《算法竞赛》
计算几何 - 罗勇军《算法竞赛》
字符串 - 罗勇军《算法竞赛》
图论 - 罗勇军《算法竞赛》

怎么看小节里的图

每个小节开头有若干张 flowchart TD 有向图，画的是本节题目之间的做题先后关系。

节点写「题号 + 简短标题」，就是本节题单里列的那几道题。
箭头 A → B 表示硬前置：B 会用到 A 建立起来的套路，先把 A 做完再碰 B，能省掉大量原地打转。
图里只画有前置关系的题。 没有出现在任何图里的题，在每节末尾单独列出，它们不依赖本节任何题，可以随时插进来做。
四个大题（高级数据结构、动态规划、数论和线性代数、图论）题量上百，改用知识点级路线图：节点是子专题加它的起始题，箭头是子专题之间的先后；每张图下面一句话列出该子专题的其余题目。
图只画节内关系，跨小节的依赖写在每节正文里。
同一道题出现在多个小节时，每节的图都把它完整画一次，因为它在不同小节的入边并不相同。

基础数据结构 - 罗勇军《算法竞赛》

洛谷子题单 · 31 题

栈与表达式

flowchart TD
  nP1449["P1449 后缀表达式"]
  nP1739["P1739 表达式括号匹配"]
  nP1981["P1981 表达式求值"]
  nP1175["P1175 表达式的转换"]

  nP1449 --> nP1739
  nP1449 --> nP1981
  nP1981 --> nP1175

P1449 后缀表达式是栈的入口，P1739 括号匹配是它的最简版，P1981 → P1175 是中缀求值再到表达式转换。

单调栈

flowchart TD
  nP2947["P2947 Look Up S"]
  nP5788["P5788 单调栈"]

  nP2947 --> nP5788

P2947 Look Up 是「找右边第一个更大值」的单调栈，P5788 是同一模板的裸题。

队列基础

flowchart TD
  nP1996["P1996 约瑟夫问题"]
  nP1160["P1160 队列安排"]
  nP1540["P1540 机器翻译"]
  nP2776["P2776 小组队列"]

  nP1996 --> nP1160
  nP1996 --> nP1540
  nP1540 --> nP2776

P1996 约瑟夫问题用队列模拟，P1160 队列安排改成链表，P1540 机器翻译是先进先出缓存，P2776 小组队列要同时维护两层队列。

单调队列

flowchart TD
  nP1886["P1886 单调队列"]
  nP1440["P1440 求m区间内的最小值"]
  nP2032["P2032 扫描"]
  nP1714["P1714 切蛋糕"]
  nP2422["P2422 良好的感觉"]

  nP1886 --> nP1440
  nP1886 --> nP2032
  nP1886 --> nP1714
  nP1886 --> nP2422

P1886 滑动窗口是模板，P1440 与 P2032 是同一模板换题面，P1714 切蛋糕把前缀和塞进队列，P2422 良好的感觉找「最小值乘区间和」。

单调队列优化 DP

flowchart TD
  nP1886["P1886 单调队列"]
  nP1725["P1725 琪露诺"]
  nP3957["P3957 跳房子"]
  nP2629["P2629 好消息，坏消息"]

  nP1886 --> nP1725
  nP1886 --> nP3957
  nP1886 --> nP2629

同样从 P1886 出发：P1725 琪露诺把窗口套在 DP 转移上，P3957 跳房子再叠一次二分答案，P2629 是好消息坏消息的环形前缀和处理。

二叉树

flowchart TD
  nP1087["P1087 FBI 树"]
  nP1030["P1030 求先序排列"]
  nP1229["P1229 遍历问题"]
  nP1305["P1305 新二叉树"]
  nP5018["P5018 对称二叉树"]

  nP1087 --> nP1030
  nP1030 --> nP1229
  nP1305 --> nP5018

P1087 FBI 树练建树与遍历，P1030 求先序是已知两种遍历推第三种，P1229 数方案；P1305 新二叉树按描述建树，P5018 对称二叉树在它之上做匹配。

堆与贪心

flowchart TD
  nP3378["P3378 堆"]
  nP1090["P1090 合并果子"]
  nP2168["P2168 荷马史诗"]
  nP3045["P3045 Cow Coupons G"]

  nP3378 --> nP1090
  nP1090 --> nP2168
  nP1090 --> nP3045

P3378 是堆模板，P1090 合并果子是堆 + 贪心，P2168 荷马史诗是它的 k 叉版，P3045 Cow Coupons 要两个堆互相反悔。

对顶堆

flowchart TD
  nP3378["P3378 堆"]
  nP1168["P1168 中位数"]
  nP2085["P2085 最小函数值"]
  nP2827["P2827 蚯蚓"]

  nP3378 --> nP1168
  nP3378 --> nP2085
  nP2085 --> nP2827

P1168 中位数是对顶堆模板，P2085 最小函数值是多路取最小，P2827 蚯蚓用单调队列把堆替换掉。

P5597 复读是树上 DP + 字符串，与本节其他题没有前置关系。

基本算法 - 罗勇军《算法竞赛》

洛谷子题单 · 47 题

二分答案

flowchart TD
  nP1824["P1824 进击的奶牛"]
  nP2678["P2678 跳石头"]
  nP1419["P1419 寻找段落"]
  nP1083["P1083 借教室"]
  nP1314["P1314 聪明的质监员"]
  nP3745["P3745 期末考试"]

  nP1824 --> nP2678
  nP1824 --> nP1419
  nP1824 --> nP1083
  nP1083 --> nP1314
  nP2678 --> nP3745

P1824 进击的奶牛是二分答案模板，之后 P2678 跳石头、P1419 寻找段落、P1083 借教室都是「二分答案加 check」；P1083 → P1314 是差分套二分，P2678 → P3745 是同一模型的更复杂版本。

三分

flowchart TD
  nP3382["P3382 三分"]
  nP1883["P1883 三分"]

  nP3382 --> nP1883

P3382 三分求单峰函数极值是模板，P1883 把多组函数取 max 之后仍然是单峰的。

ST 表与区间最值

flowchart TD
  nP3865["P3865 ST 表 & RMQ 问…"]
  nP2880["P2880 Balanced Lineup G"]
  nP2251["P2251 质量检测"]
  nP1816["P1816 忠诚"]
  nP1198["P1198 最大数"]
  nP5012["P5012 水の数列"]

  nP3865 --> nP2880
  nP3865 --> nP2251
  nP3865 --> nP1816
  nP3865 --> nP1198
  nP3865 --> nP5012

P3865 ST 表是模板，P2880 / P2251 / P1816 都是区间最值的直接套用，P1198 最大数要在线增量建表，P5012 是水の数列。

倍增进阶

flowchart TD
  nP3865["P3865 ST 表 & RMQ 问…"]
  nP4155["P4155 国旗计划"]
  nP5465["P5465 星际穿越"]
  nP3295["P3295 萌萌哒"]
  nP5344["P5344 逛森林"]

  nP3865 --> nP4155
  nP3865 --> nP5465
  nP3865 --> nP3295
  nP3865 --> nP5344

同样从 P3865 出发：P4155 国旗计划是区间覆盖上的倍增，P5465 星际穿越是树上倍增，P3295 萌萌哒用倍增合并区间，P5344 逛森林是倍增建虚点。

前缀和与差分

flowchart TD
  nP3397["P3397 地毯"]
  nP3406["P3406 海底高铁"]
  nP4552["P4552 IncDec Sequence"]
  nP3948["P3948 数据结构"]
  nP3131["P3131 Subsequences Summi…"]
  nP2280["P2280 激光炸弹"]

  nP3397 --> nP3406
  nP3397 --> nP4552
  nP4552 --> nP3948
  nP3131 --> nP2280

P3397 地毯是二维差分，P3406 海底高铁与 P4552 是它的一维应用，P4552 → P3948 再叠一次数据结构；P3131 用到前缀和取模，P2280 是二维前缀和。

邻项交换与排序贪心

flowchart TD
  nP1093["P1093 奖学金"]
  nP2652["P2652 同花顺"]
  nP1080["P1080 国王游戏"]
  nP2123["P2123 皇后游戏"]
  nP5521["P5521 梅深不见冬"]

  nP1093 --> nP2652
  nP1080 --> nP2123
  nP2123 --> nP5521

P1093 奖学金练多关键字排序，P2652 同花顺是排序加扫描；P1080 国王游戏是邻项交换的经典推导，P2123 皇后游戏是它的变体，P5521 梅深不见冬再到树上。

双指针与排序取数

flowchart TD
  nP1208["P1208 混合牛奶"]
  nP4995["P4995 跳跳！"]
  nP1094["P1094 纪念品分组"]
  nP2672["P2672 推销员"]

  nP1208 --> nP4995
  nP1208 --> nP1094

P1208 混合牛奶排序后取单价，P4995 跳跳与 P1094 纪念品分组都是排完序之后两头取。

递归与模拟

flowchart TD
  nP1010["P1010 幂次方"]
  nP1498["P1498 南蛮图腾"]

  nP1010 --> nP1498

P1010 幂次方是递归分解，P1498 南蛮图腾是递归画图。

P1102（二分数对）、P1462（二分加最短路）、P1868（线性 DP）、P1493（排序加前缀）、P2048（堆加区间）、P1052（DP 加路径压缩）、P1115（最大子段和）、P1908（归并逆序对）、P1593（因子和）、P1923（第 k 小）、P2097（模拟）、P1199（博弈）与上面八张图都没有前置关系。

搜索 - 罗勇军《算法竞赛》

洛谷子题单 · 28 题

DFS 与剪枝

flowchart TD
  nP1120["P1120 小木棍"]
  nP1074["P1074 靶形数独"]
  nP1312["P1312 Mayan 游戏"]
  nP2324["P2324 骑士精神"]
  nP2346["P2346 四子连棋"]

  nP1120 --> nP1074
  nP1120 --> nP1312
  nP1312 --> nP2324
  nP1312 --> nP2346

P1120 小木棍是剪枝集大成的一题，P1074 靶形数独与 P1312 Mayan 游戏都在它之上；P1312 → P2324 / P2346 是 IDA* 与模拟类搜索。

网格连通块

flowchart TD
  nP8662["P8662 全球变暖"]
  nP1162["P1162 填涂颜色"]
  nP1506["P1506 拯救 oibh 总部"]

  nP8662 --> nP1162
  nP1162 --> nP1506

P8662 全球变暖是数被淹没的连通块，P1162 填涂颜色把外圈灌满再判断，P1506 拯救 oibh 总部是同一套边界处理。

网格最短路

flowchart TD
  nP1443["P1443 马的遍历"]
  nP1126["P1126 机器人搬重物"]
  nP1649["P1649 Obstacle Course S"]
  nP3956["P3956 棋盘"]

  nP1443 --> nP1126
  nP1443 --> nP1649
  nP1126 --> nP3956

P1443 马的遍历是 BFS 求最短步数模板，P1126 机器人搬重物要加上朝向状态，P1649 加了障碍代价，P3956 棋盘是 0-1 BFS。

折半与状压搜索

flowchart TD
  nP5194["P5194 Scales S"]
  nP4799["P4799 世界冰球锦标赛"]
  nP1433["P1433 吃奶酪"]

  nP5194 --> nP4799
  nP4799 --> nP1433

P5194 Scales S 是折半搜索入门，P4799 世界冰球锦标赛是同一模板的大规模版，P1433 吃奶酪是状压加剪枝。

图上搜索

flowchart TD
  nP4779["P4779 单源最短路径（标准版）"]
  nP4667["P4667 Switch the Lamp On"]
  nP2483["P2483 k 短路"]
  nP3047["P3047 Nearby Cows G"]

  nP4779 --> nP4667
  nP4779 --> nP2483
  nP4779 --> nP3047

P4779 单源最短路是入口，P4667 把 0-1 BFS 写成最短路，P2483 求 k 短路，P3047 Nearby Cows 是树上的距离统计。

P1219（八皇后）、P1019（单词接龙）、P5440（奇迹）、P1378（油滴扩展）、P1118（数字三角形搜索）、P1514（引水入城）、P5195（Knights of Ni）、P1032（字串变换）、P2534（铁盘整理）与上面五张图没有前置关系。

高级数据结构 - 罗勇军《算法竞赛》

洛谷子题单 · 148 题

第一层：从并查集到线段树

flowchart TD
  ndsu["并查集<br/>P2024 起"]
  nbit["树状数组<br/>P3374 起"]
  nseg["线段树<br/>P3372 起"]

  ndsu --> nbit
  nbit --> nseg

这三块是本节的骨架，后面的可持久化、树套树、分块都以它们为前提。

并查集（P2024 起）另有 P1111、P3958、P1525、P4185、P1197、P1196、P1955、P3402；树状数组（P3374 起）另有 P3368、P1908、P1774、P4479、P1966、P3605、P3586、P4054、P4113；线段树（P3372 起）另有 P4514、P3373、P3870、P4145、P6242、P1856、P5490、P4588、P1502、P2471、P2824、P3722、P4097、P4198、P4513、P4556、P5324、P5327、P3960、P3992。

第二层：可持久化与分块

flowchart TD
  npst["可持久化线段树<br/>P3919 起"]
  nblock["分块<br/>P2801 起"]
  nmo["莫队<br/>P2709 起"]

  npst --> nblock
  nblock --> nmo

可持久化线段树与分块是两条平行的进阶线，莫队建在分块之上。

可持久化线段树（P3919 起）另有 P3834、P2468、P3302、P3168、P4559、P3293、P2633、P4618；分块（P2801 起）另有 P3396、P3863、P1975、P3710、P2325；莫队（P2709 起）另有 P1972、SP10707、P4168、P4119、P1494、P1903、P5906、P4887、P3674、P3709、P4074、P5501。

第三层：树上的结构

flowchart TD
  ntree1["树的直径与 LCA<br/>B4016 起"]
  ncentroid["点分治<br/>P3806 起"]
  nhld["树链剖分<br/>P3384 起"]

  ntree1 --> ncentroid
  ntree1 --> nhld
  ncentroid --> nhld

先在树上拿到 LCA 与直径这两件工具，再学点分治与树链剖分；树链剖分是后面许多树上套数据结构的载体。

树的直径与 LCA（B4016 起）另有 P3629、P1099、P3128、P1967、P2680、P1600、P3379、P3938、P4281；点分治（P3806 起）另有 P4178、P6329、P2056、P3345、P4183、P5306、P2634、P2664、P3714、P4149、P3241、P4075、P4292；树链剖分（P3384 起）另有 P2146、P3178、P3038、P3313、P2590、P1505、P2486、P3258、P4069、P4211、P4592、P5305、P5354。

第四层：平衡树与动态树

flowchart TD
  nbst["平衡树与 Splay<br/>P3369 起"]
  nkdt["KD-Tree<br/>P4148 起"]
  nlct["LCT 动态树<br/>P3690 起"]

  nbst --> nlct
  nbst --> nkdt

平衡树是本节最后一个基础件，KD-Tree 与 LCT 都在它之后。

平衡树与 Splay（P3369 起）另有 P4008、P5055、P3835、P5854、P1377、P5044、P3793、P1440、P4567、P3391、P3850、P5338、P2042、P1110、P3644、P1486、P2710、P3224、P3285、P5321、P5499；KD-Tree（P4148 起）另有 P4169、P4357、P7883、P2479、P3769、P4390、P4475、P2093、P5471；LCT 动态树（P3690 起）另有 P3203、P4338、P1501、P3348、P3703、P4172、P4219、P5489、P2387。

动态规划 - 罗勇军《算法竞赛》

洛谷子题单 · 86 题

第一层：三种基本形态

flowchart TD
  nlinear["线性 DP<br/>P1216 起"]
  ninterval["区间 DP<br/>P1775 起"]
  ntree["树形 DP<br/>P1352 起"]

  nlinear --> ninterval
  nlinear --> ntree

线性、区间、树形是 DP 的三种基本形态，先把它们练熟再谈优化。

线性 DP（P1216 起）另有 P1048、P2758、P1020、P1091、P1095、P1541、P1868、P2679、P2501、P3336、P3558、P4158、P5301；区间 DP（P1775 起）另有 P1880、CF1198D、P3146、P1063、P1005、P4170、P4302、P2466；树形 DP（P1352 起）另有 P2015、P4322、P1040、P1122、P1273、P2014、P2585、P3047、P3698、P5658、P2607、P3177、P4395、P4516。

第二层：状态设计

flowchart TD
  nsubset["状压 DP<br/>P1896 起"]
  ndigit["数位 DP<br/>P2602 起"]

  nsubset --> ndigit

状压与数位是「状态怎么表示」的两类套路，难度比第一层高一档。

状压 DP（P1896 起）另有 P1433、P10975、P2831、P2704、P1879、P3092、P3694、P4925、P2157、P2167、P2396、P4363、P5005、P2150；数位 DP（P2602 起）另有 P2657、P4124、P4798、P3281、P2518、P3286、P4999。

第三层：优化手段

flowchart TD
  nmono["单调队列与斜率优化<br/>P1725 起"]
  ndecmono["决策单调性<br/>UVA10304 起"]

  nmono --> ndecmono

先是单调队列与斜率优化，再是决策单调性；这两块都要求先把第一层的朴素转移写出来。

单调队列与斜率优化（P1725 起）另有 P3287、P2605、P2627、P3957、P1776、P3089、P3572、P3522、P4544、P5665、P1973、P2569、P4852、P2900、P3628、P3648、P4360、P5468、P2305、P3195；决策单调性（UVA10304 起）另有 P1912、P4767、P4072。

数论和线性代数 - 罗勇军《算法竞赛》

洛谷子题单 · 113 题

第一层：四件基础工具

flowchart TD
  ngcd["gcd 与同余基础<br/>P1029 起"]
  nmatrix["矩阵与快速幂<br/>P3390 起"]
  ngauss["高斯消元<br/>P3389 起"]
  nbasis["线性基<br/>P3812 起"]

  ngcd --> nmatrix
  nmatrix --> ngauss
  ngauss --> nbasis

gcd 与同余是全部数论的前提，矩阵、高斯消元、线性基是三条并列的代数工具。

gcd 与同余基础（P1029 起）另有 P2152、P1890、P5435、P5436、P1414、P1072、P4549、P1516、P1082、P2613、P3811、P5431、P3951；矩阵与快速幂（P3390 起）另有 P1226、P2886、P1349、P1939、P1306、P2044、P5175、P4783、P1962、P4000、P3758、P4967、P5343、P5337、P5303；高斯消元（P3389 起）另有 P2447、P4035、P5516、P4111、P4457；线性基（P3812 起）另有 P3857、P4570、P3292、P4151。

第二层：进阶数论

flowchart TD
  ncrt["CRT 与欧拉定理<br/>P4777 起"]
  nmobius["莫比乌斯反演与筛<br/>P2261 起"]
  nfrac["01 分数规划<br/>P4377 起"]

  ncrt --> nmobius

CRT 与欧拉定理建在第一层的同余之上，莫比乌斯反演再往上走一层；01 分数规划只要求会二分与最短路，和它们平行。

CRT 与欧拉定理（P4777 起）另有 P3868、P2480、P4774、P5345、P4718、P1075、P2441、P5535、P2158、P2568、P2398、P4139；莫比乌斯反演与筛（P2261 起）另有 P5221、P3935、P3172、P2522、P3455、P3327、P1829、P4619、P3704、P5518、P4213；01 分数规划（P4377 起）另有 P3199、P3288、P3705、P4322。

第三层：多项式与概率

flowchart TD
  npoly["多项式<br/>P3803 起"]
  nprob["概率与期望<br/>P2473 起"]

  npoly --> nprob

多项式是本节最重的一块，建议放到最后；概率与期望可以独立推进，只要求会写期望 DP。

多项式（P3803 起）另有 P1919、P4238、P4245、P4512、P4717、P4721、P4725、P4726、P4781、P5050、P5158、P5205、P5245、P5273、P5282、P5373、P5383、P5393、P5394、P3338、P3723、P5437、P5293、P5432、P5472、P5577；概率与期望（P2473 起）另有 P4525、P5104、P1850、P3830、P4564、P2221、P3239、P3750、P4284、P5249、P2081、P3343、P3600、P5326。

组合数学 - 罗勇军《算法竞赛》

洛谷子题单 · 59 题

组合数与 Lucas

flowchart TD
  nP2822["P2822 组合数问题"]
  nP1313["P1313 计算系数"]
  nP3807["P3807 卢卡斯定理"]
  nP4345["P4345 超能粒子炮·改"]
  nP1680["P1680 奇怪的分组"]
  nP4931["P4931 情侣？给我烧了！（加强版…"]

  nP2822 --> nP1313
  nP2822 --> nP3807
  nP3807 --> nP4345
  nP3807 --> nP1680
  nP2822 --> nP4931

P2822 递推组合数是入口，P1313 用二项式定理，P3807 Lucas 定理之后 P4345 与 P1680 是它的变体。

容斥

flowchart TD
  nP3197["P3197 越狱"]
  nP1450["P1450 硬币购物"]
  nP3349["P3349 小星星"]
  nP4336["P4336 黑暗前的幻想乡"]
  nP3270["P3270 成绩比较"]
  nP4491["P4491 染色"]

  nP3197 --> nP1450
  nP3197 --> nP3349
  nP3197 --> nP4336
  nP3197 --> nP3270
  nP3197 --> nP4491

P3197 越狱是容斥入门，P1450 硬币购物是背包型容斥，P3349 小星星是树上容斥，P4336 黑暗前的幻想乡是矩阵树加容斥。

Catalan 与格路计数

flowchart TD
  nP1044["P1044 栈"]
  nP2532["P2532 树屋阶梯"]
  nP3200["P3200 有趣的数列"]
  nP1641["P1641 生成字符串"]
  nP1722["P1722 矩阵 II"]
  nP1976["P1976 鸡蛋饼"]

  nP1044 --> nP2532
  nP2532 --> nP3200
  nP1044 --> nP1641
  nP1641 --> nP1722
  nP1641 --> nP1976

P1044 栈是 Catalan 的最直观模型，P2532 树屋阶梯与 P3200 有趣的数列是同一个数的两种包装；P1641 生成字符串走格路计数，P1722 与 P1976 都在它之上。

斯特林数

flowchart TD
  nP5395["P5395 第二类斯特林数·行"]
  nP5396["P5396 第二类斯特林数·列"]
  nP5408["P5408 第一类斯特林数·行"]
  nP5409["P5409 第一类斯特林数·列"]
  nP1655["P1655 小朋友的球"]

  nP5395 --> nP5396
  nP5408 --> nP5409
  nP5395 --> nP1655

P5395 第二类斯特林数·行与 P5396·列是一对，P5408 / P5409 是第一类的一对；P1655 小朋友的球是第二类斯特林数的应用题。

Polya 与置换群

flowchart TD
  nP4980["P4980 Pólya 定理"]
  nP2561["P2561 黑白瓷砖"]
  nP4128["P4128 有色图"]
  nP4727["P4727 图的同构计数"]
  nP1446["P1446 Cards"]

  nP4980 --> nP2561
  nP4980 --> nP4128
  nP4980 --> nP4727
  nP2561 --> nP1446

P4980 Polya 定理是模板，P2561 黑白瓷砖与 P4128 有色图、P4727 图的同构计数都是它的应用，P1446 Cards 是 Burnside 的另一道题。

树的计数

flowchart TD
  nP2290["P2290 树的计数"]
  nP6598["P6598 烷烃计数"]
  nP5818["P5818 同分异构体计数"]
  nP6597["P6597 烯烃计数"]

  nP2290 --> nP6598
  nP6598 --> nP6597
  nP6598 --> nP5818

P2290 树的计数用 prufer 序列，P6598 烷烃计数是它的生成函数版，P6597 烯烃与 P5818 同分异构体在它之上。

博弈论

flowchart TD
  nP4018["P4018 Roy&October之…"]
  nP2252["P2252 威佐夫博弈"]
  nP2953["P2953 Cow Digit Game S"]
  nP2575["P2575 高手过招"]
  nP2599["P2599 取石子游戏"]
  nP1290["P1290 欧几里德的游戏"]
  nP5675["P5675 取石子游戏"]

  nP4018 --> nP2953
  nP4018 --> nP2575
  nP2252 --> nP2599
  nP2252 --> nP1290
  nP2599 --> nP5675

P4018 是 SG 函数入门，P2953 与 P2575 都是 SG 的直接套用；P2252 威佐夫博弈与 P2599 取石子是另一支，P1290 欧几里德的游戏与 P5675 都在它之上。

P5520（插板法）、P5596、P3726（抛硬币）、P2480（古代猪文）、P2675、P5664（计数 DP）、P4769（冒泡排序）、P3978（概率论）、P4448、P5400、P5339（容斥加 DP）、P4827（斯特林加树形 DP）、P4708（Burnside）、P4451、P4463、P4705（生成函数）、P2000、P5652、P3210、P1288 与上面七张图没有前置关系。

计算几何 - 罗勇军《算法竞赛》

洛谷子题单 · 16 题

凸包

flowchart TD
  nP1355["P1355 神秘大三角"]
  nP2742["P2742 二维凸包"]
  nP1452["P1452 Beauty Contest G"]
  nP3829["P3829 信用卡凸包"]
  nP3187["P3187 最小矩形覆盖"]

  nP1355 --> nP2742
  nP2742 --> nP1452
  nP2742 --> nP3829
  nP1452 --> nP3187

P1355 练基本向量运算，P2742 二维凸包是模板，P1452 旋转卡壳求直径、P3829 信用卡凸包是凸包的曲线版，P3187 最小矩形覆盖是旋转卡壳的进一步应用。

最近点对与最小圆覆盖

flowchart TD
  nP1257["P1257 平面上的最接近点对"]
  nP1742["P1742 最小圆覆盖"]
  nP2287["P2287 最佳包裹"]

  nP1257 --> nP1742
  nP1257 --> nP2287

P1257 平面最近点对是分治模板，P1742 最小圆覆盖是随机增量，P2287 最佳包裹是三维版。

半平面交

flowchart TD
  nP4196["P4196 半平面交"]
  nP4557["P4557 战争"]
  nP4250["P4250 小凸想跑步"]
  nP3297["P3297 逃考"]

  nP4196 --> nP4557
  nP4196 --> nP4250
  nP4557 --> nP3297

P4196 半平面交是模板，P4557 战争是半平面交判可行域，P4250 小凸想跑步是它的概率版，P3297 逃考再用一次。

P5403（田野）、P3256（赛车）、P2600（瞭望塔）、P5328（浙江省选）与上面三张图没有前置关系。

字符串 - 罗勇军《算法竞赛》

洛谷子题单 · 56 题

哈希

flowchart TD
  nP3370["P3370 字符串哈希"]
  nP3501["P3501 ANT-Antisymmetry"]
  nP4391["P4391 Radio"]
  nP5270["P5270 无论怎样神树大人都会删库…"]
  nP5537["P5537 系统设计"]

  nP3370 --> nP3501
  nP3370 --> nP4391
  nP4391 --> nP5270
  nP4391 --> nP5537

P3370 字符串哈希是模板，P3501 判反对称、P4391 求最小循环节，P5270 与 P5537 都在它之上。

Manacher

flowchart TD
  nP3805["P3805 Manacher"]
  nP1659["P1659 拉拉队排练"]
  nP4555["P4555 最长双回文串"]

  nP3805 --> nP1659
  nP3805 --> nP4555

P3805 Manacher 是模板，P1659 拉拉队排练按回文长度统计，P4555 求最长双回文串。

Trie 基础

flowchart TD
  nP2580["P2580 于是他错误的点名开始了"]
  nP3879["P3879 阅读理解"]
  nP2922["P2922 Secret Message G"]
  nP2292["P2292 L 语言"]

  nP2580 --> nP3879
  nP2580 --> nP2922
  nP2580 --> nP2292

P2580 点名单是 Trie 模板，P3879 阅读理解建倒排表，P2922 与 P2292 都在 Trie 上数前缀。

Trie 进阶

flowchart TD
  nP2580["P2580 于是他错误的点名开始了"]
  nP3065["P3065 First! G"]
  nP3294["P3294 背单词"]
  nP4407["P4407 电子字典"]

  nP2580 --> nP3065
  nP3065 --> nP3294
  nP2580 --> nP4407

P3065 First! 判前缀冲突，P3294 背单词在它之上定输出顺序，P4407 判一位编辑距离。

01-Trie 与输出控制

flowchart TD
  nP2580["P2580 于是他错误的点名开始了"]
  nP4551["P4551 最长异或路径"]
  nP4683["P4683 Type Printer"]

  nP2580 --> nP4551
  nP2580 --> nP4683

P4551 把字符换成二进制位（01-Trie），P4683 Type Printer 用 Trie 控制打印顺序。

KMP 与 Z 函数

flowchart TD
  nP3375["P3375 KMP"]
  nP3435["P3435 OKR-Periods of Wor…"]
  nP2375["P2375 动物园"]
  nP3426["P3426 SZA-Template"]
  nP3193["P3193 GT考试"]
  nP5410["P5410 扩展 KMP"]

  nP3375 --> nP3435
  nP3435 --> nP2375
  nP3435 --> nP3426
  nP3375 --> nP3193
  nP3375 --> nP5410

P3375 KMP 是模板，P3435 与 P3426 都用失配树，P2375 在失配树上叠倍增；P3193 GT 考试是 KMP 加矩阵，P5410 扩展 KMP 是另一套 Z 数组。

AC 自动机模板

flowchart TD
  nP3808["P3808 AC 自动机（简单版）"]
  nP3796["P3796 AC 自动机（简单版 I…"]
  nP5357["P5357 AC 自动机"]

  nP3808 --> nP3796
  nP3808 --> nP5357

P3808 是 AC 自动机模板，P3796 多模式串统计、P5357 二次加强版。

fail 树与 fail 上的 DP

flowchart TD
  nP5357["P5357 AC 自动机"]
  nP2414["P2414 阿狸的打字机"]
  nP3966["P3966 单词"]
  nP3311["P3311 数数"]
  nP4052["P4052 文本生成器"]

  nP5357 --> nP2414
  nP5357 --> nP3966
  nP5357 --> nP3311
  nP3311 --> nP4052

P2414 阿狸的打字机与 P3966 单词要建 fail 树统计；P3311 数数在 fail 树上做数位 DP，P4052 文本生成器是同一形态。

AC 自动机加判环

flowchart TD
  nP3808["P3808 AC 自动机（简单版）"]
  nP3121["P3121 Censoring G"]
  nP2444["P2444 病毒"]

  nP3808 --> nP3121
  nP3121 --> nP2444

P3121 Censoring 在 AC 自动机上做栈式删除，P2444 病毒判 fail 图上的环。

后缀排序

flowchart TD
  nP3809["P3809 后缀排序"]
  nP5353["P5353 树上后缀排序"]
  nP2336["P2336 喵星球上的点名"]
  nP2463["P2463 Sandy 的卡片"]

  nP3809 --> nP5353
  nP3809 --> nP2336
  nP3809 --> nP2463

P3809 后缀排序是模板，P5353 把它搬到树上，P2336 与 P2463 都在 height 数组上数出现次数。

height 数组的应用

flowchart TD
  nP3809["P3809 后缀排序"]
  nP2852["P2852 Milk Patterns G"]
  nP4051["P4051 字符加密"]
  nP1117["P1117 优秀的拆分"]
  nP2178["P2178 品酒大会"]

  nP3809 --> nP2852
  nP3809 --> nP4051
  nP3809 --> nP1117
  nP1117 --> nP2178

P2852 找最长重复子串、P4051 处理循环串、P1117 优秀的拆分配合哈希，P2178 品酒大会是后缀数组加并查集。

回文自动机

flowchart TD
  nP5496["P5496 回文树"]
  nP3649["P3649 回文串"]
  nP4287["P4287 双倍回文"]
  nP4762["P4762 Virus synthesis"]
  nP4824["P4824 Censoring S"]

  nP5496 --> nP3649
  nP5496 --> nP4287
  nP4287 --> nP4762
  nP5496 --> nP4824

P5496 回文树是模板，P3649 数回文串出现次数、P4287 双倍回文、P4762 Virus synthesis 与 P4824 Censoring 都建在它之上。

后缀自动机

flowchart TD
  nP3804["P3804 后缀自动机（SAM）"]
  nP3975["P3975 弦论"]
  nP4248["P4248 差异"]
  nP5341["P5341 甲苯先生和大中锋的字符串"]
  nP4770["P4770 你的名字"]
  nP5284["P5284 字符串问题"]
  nP5319["P5319 奥术神杖"]

  nP3804 --> nP3975
  nP3804 --> nP4248
  nP3804 --> nP5341
  nP3804 --> nP4770
  nP4770 --> nP5284
  nP4770 --> nP5319

P3804 后缀自动机是模板，P3975 弦论求第 k 小子串、P4248 差异求两两 LCP 和、P5341 数出现次数、P4770 你的名字、P5284 与 P5319 都是 SAM 的进阶应用。

P5537（系统设计）、P3783（天才黑客）、P5599（文本编辑器）、P5346（柯南家族）、P5576（口头禅）与上面八张图没有前置关系。

图论 - 罗勇军《算法竞赛》

洛谷子题单 · 112 题

第一层：建图与遍历

flowchart TD
  ntopo["拓扑排序<br/>P1113 起"]
  neuler["欧拉路径<br/>P2731 起"]
  ntarjan["Tarjan 与连通性<br/>P2863 起"]
  nsat["2-SAT<br/>P4782 起"]

  ntopo --> neuler
  ntopo --> ntarjan
  ntarjan --> nsat

拓扑、欧拉路、Tarjan 是三种「怎么走一张图」的基本功，2-SAT 建在 Tarjan 缩点之上。

拓扑排序（P1113 起）另有 P1347、P1685、P3243、P1983、P1038、P4934、P4017、P2597；欧拉路径（P2731 起）另有 UVA10054、P1341、P1333、P1127、P6066、P6628；Tarjan 与连通性（P2863 起）另有 P3387、P3388、P2341、P2746、P1407、P2272、P3225、P5058、P2515、P2607、P5049、P4381、P1399、P1453；2-SAT（P4782 起）另有 P4171、P3825、P5332。

第二层：最短路与生成树

flowchart TD
  nsp["最短路<br/>P3371 起"]
  nmst["最小生成树<br/>P3366 起"]

  nsp --> nmst

最短路与 MST 是图论的两条老主线，货车运输这类题会把它们接起来。

最短路（P3371 起）另有 B3647、P1119、P1613、P2865、P2868、P5960、P1730、P2419、P3385、P1993、P4779、P5905、P1144、P1462、P1522、P1266、P4568、P3238、P5304、P3275、P2294、P4926、P5590；最小生成树（P3366 起）另有 P2121、P4180、P4951、P2872、P1991、P1967、P4047。

第三层：网络流

flowchart TD
  nflow["网络流<br/>P3376 起"]
  nmatch["二分图匹配与最小割<br/>P3386 起"]
  ncost["最小费用最大流<br/>P3381 起"]

  nflow --> nmatch
  nmatch --> ncost

先在最大流上练手，再看二分图匹配与最小割怎么互相翻译，最后是最小费用流。

网络流（P3376 起）另有 P2472、P2754、P2765、P2766、P2805、P4722；二分图匹配与最小割（P3386 起）另有 P2071、P2756、P1129、P1559、P2423、P2764、P2825、P3033、P3731、P4014、P4617、P2065、P2763、P1344、P1345、P2057、P2598、P2774、P4126、P5039、P3749、P4897、P4001；最小费用最大流（P3381 起）另有 P4452、P2045、P2050、P2053、P2604、P2770、P3159、P3356、P3358、P4013、P4015、P5331、P3705。

罗勇军《算法竞赛》题单