一个动态更新的洛谷综合题单（原版）

一个动态更新的洛谷综合题单

---

洛谷试炼场的题目确实很具有代表性，但是近几年以来，又有许多经典题目出现在 OI 界中，这个大题单就是作为洛谷试炼场的扩展和补充。

Copyleft

本项目采用 知识共享署名-相同方式共享 4.0 国际许可协议 以及附加的 The Star And Thank Author License 进行许可。

换言之，您可以自由的共享并演绎该项目，但是必须给出必要的署名，并以相同方式共享本项目，并为本项目的 Github 仓库 点赞（Star）。

新版本食用指南

本次版本更新变更较大，建议您仔细阅读下面的内容！

在刚刚更新的 2.0 版本中，我们改变了原来按知识难度排列知识点的目录结构，改为按照专题大类组织目录结构。

为了方便按知识难度刷题的用户，这里给出一些建议：

• 对于初学者，建议先完成 Part 1,2 两部分内容，为接下来的学习打好基础。
• 对于要参加 CSP-S 的选手，建议在前面的基础上优先完成 Part 3.1-3.4, 4.1-4.4, 6.1-6.5, 7.1-7.8, 8.1-8.7 的内容（具体内容见下），在此基础上继续完成其他内容。
• 每个专题下的题目先给出模板，剩下的题目均按照难度递增顺序排序，部分难度较高的综合性题目建议达到一定能力后再尝试解决。

更新日志

3.0.2 2020/2/28：

1. 添加了少量比赛题目；
2. 移除了一些做法重复的题目。

3.0.1 2019/12/8：

1. 添加了 CSP2019 和一些公开赛的题目；
2. 跟进洛谷域名更换，将题目链接全部更新。

3.0 2019/10/13：

1. 新增专题：回文自动机，K-D Tree，自适应辛普森法，左偏树，置换群，离线算法，构造，DLX，三分法，珂朵莉树。
2. 添加了一些最近的公开比赛题目，部分专题补充了一些优质题目。
3. 移除了部分重复题目。
4. 对之前没有介绍的专题补充了介绍。

更早版本的更新日志请点击这里查看

Part 0 试机题

三道试机题目。

• P1000 超级玛丽游戏
• P1001 A+B Problem
• P1008 三连击

Part 1 入门阶段

本部分内容针对入门 OIer ，主要是语言基础内容。

Part 1.1 从零开始

语言基础题。

• P1421 小玉买文具
• P1909 买铅笔
• P1089 津津的储蓄计划
• P1085 不高兴的津津
• P1035 级数求和
• P1980 计数问题
• P1014 Cantor表
• P1307 数字反转

Part 1.2 数组基础

数组可以用于存储大量的信息。

• P1046 陶陶摘苹果
• P1047 校门外的树
• P1427 小鱼的数字游戏
• P2141 珠心算测验
• P5594 【XR-4】模拟赛

Part 1.3 字符串基础

字符串是特殊的数组，但它也有很多自身的特点。

• P5015 标题统计
• P1055 ISBN号码
• P1308 统计单词数
• P2010 回文日期
• P1012 拼数
• P5587 打字练习

Part 1.4 函数，递归及递推

这是初学者最难理解的部分，建议画出递归图来理解递归的过程。

• P1028 数的计算
• P1036 选数
• P1464 Function
• P5534 【XR-3】等差数列
• P1192 台阶问题
• P1025 数的划分
• P4994 终于结束的起点

Part 2 基础算法

这一部分的内容包含了 OI 中的基础算法，供各位巩固基础。

当然，这里面也有一些难度比较高的题目。

Part 2.1 模拟

模拟，顾名思义就是题目要求你做什么你就做什么，这样的题目很考验选手的代码组织能力。

这里不仅仅有非常基础的模拟，也有一些非常复杂的题目。

• P1003 铺地毯
• P1067 多项式输出
• P1328 生活大爆炸版石头剪刀布
• P1563 玩具谜题
• P1042 乒乓球
• P1179 数字统计
• P2615 神奇的幻方
• P3952 时间复杂度
• P2482 [SDOI2010]猪国杀
• P5380 [THUPC2019]鸭棋

Part 2.2 排序算法

通过排序，我们可以将数据有序化，这让我们对数据的处理方便了很多。

• P1177 【模板】快速排序
• P1059 明明的随机数
• P1068 分数线划定
• P1051 谁拿了最多奖学金
• P1309 瑞士轮
• P1908 逆序对

Part 2.3 二分答案

对一个满足单调性质的问题，我们可以采用二分答案的方法来解决。

• P1024 一元三次方程求解
• P2678 跳石头
• P1316 丢瓶盖
• P1902 刺杀大使
• P1314 聪明的质监员
• P1083 借教室
• P4343 [SHOI2015]自动刷题机

Part 2.4 分治

分治，即分而治之，将大问题分解为小问题，分别求解，最后合并结果。

• P1226 【模板】快速幂||取余运算
• P1010 幂次方
• P1429 平面最近点对（加强版）
• P3612 [USACO17JAN]Secret Cow Code

Part 2.5 贪心

贪心，指的是决策时都采取当前最优解的算法。有的时候，这样做确实可以获得最优解。

• P1208 [USACO1.3]Mixing Milk
• P4995 跳跳！
• P1094 纪念品分组
• P1199 三国游戏
• P2672 推销员
• P1080 国王游戏
• P2123 皇后游戏
• P5521 [yLOI2019]梅深不见冬

Part 2.6 构造

构造题是一种形式灵活多样的题型。正是因为这个特点，使得构造题没有一种通用的方法。

• P3599 Koishi Loves Construction
• P5441 【XR-2】伤痕
• P5595 【XR-4】歌唱比赛

Part 2.7 高精度

在 C++ 中，long long 都无法表示我们需要的整数时怎么办？那就用高精度吧！

• P1601 A+B Problem（高精）
• P2142 高精度减法
• P1303 A*B Problem
• P1480 A/B Problem
• P1009 阶乘之和

Part 2.8 前缀和 & 差分

前缀和是一种重要的预处理，能大大降低查询的时间复杂度，而差分则是一种和前缀和相对的策略。

• P3131 [USACO16JAN]Subsequences Summing to Sevens
• P1387 最大正方形
• P3397 地毯
• P2280 [HNOI2003]激光炸弹
• P4552 [Poetize6] IncDec Sequence

Part 3 搜索

搜索其实就是高级的枚举，很多题目都可以用搜索完成。就算不能，搜索也是骗分神器。

Part 3.1 深度优先搜索

深度优先搜索（DFS），即按照深度优先的顺序搜索的算法。

深度优先搜索一般使用栈来实现。

• P1219 八皇后
• P1019 单词接龙
• P5194 [USACO05DEC]Scales
• P5440 【XR-2】奇迹
• P1378 油滴扩展

Part 3.2 广度优先搜索

广度优先搜索（BFS），即优先扩展浅层节点，逐渐深入的搜索算法。

广度优先搜索一般使用队列来实现。

• P1162 填涂颜色
• P1443 马的遍历
• P3956 棋盘
• P1032 字串变换
• P1126 机器人搬重物

Part 3.3 记忆化搜索

通过将已经遍历的状态记录下来，从而减少重复的搜索量，这就是记忆化搜索。

动态规划的时候，记忆化搜索也是一种高效简洁的实现方式。

• P1514 引水入城
• P1535 游荡的奶牛
• P1434 [SHOI2002]滑雪
• P3953 逛公园

Part 3.4 搜索的剪枝

对于一些不必要搜索的部分，我们可以避免访问这些状态，从而提高搜索效率。

• P1120 小木棍 ［数据加强版］
• P1312 Mayan游戏
• P1074 靶形数独

Part 3.5 双向搜索

在搜索时，如果能从初态和终态出发，同时进行搜索，就可以减小搜索树的规模，提高时间效率。

• P3067 [USACO12OPEN]Balanced Cow Subsets
• P4799 [CEOI2015 Day2]世界冰球锦标赛
• P5195 [USACO05DEC]Knights of Ni

Part 3.6 A*

在 BFS 中，如果能设计一个合理的估价函数，就可以更快扩展到最优解。这就是 A*算法。

• P1379 八数码难题

Part 3.7 IDA*

像 BFS 那样，每次只扩展一层节点，却采用 DFS 方式来遍历搜索树，这就是迭代加深搜索。

再加上一个估价函数来减小搜索量，就是 IDA*了。

• P2324 [SCOI2005]骑士精神
• P2534 [AHOI2012]铁盘整理

Part 3.8 DLX

算法 X 是通过回溯法求解精确覆盖问题的算法，而删除列这一操作可以使用舞蹈链加速。

• P4929 【模板】舞蹈链（DLX）
• P4205 [NOI2005]智慧珠游戏

Part 4 动态规划

动态规划是一种重要的思维方法，通过利用已有的子问题信息高效求出当前问题的最优解。

Part 4.1 线性动态规划

线性动态规划，即具有线性阶段划分的动态规划。

• P1216 数字三角形
• P1020 导弹拦截
• P1091 合唱队形
• P1095 守望者的逃离
• P1541 乌龟棋
• P1868 饥饿的奶牛
• P2679 子串
• P2501 [HAOI2006]数字序列
• P3336 [ZJOI2013]话旧
• P3558 [POI2013]BAJ-Bytecomputer
• P4158 [SCOI2009]粉刷匠
• P5301 [GXOI/GZOI2019]宝牌一大堆

Part 4.2 背包动态规划

背包动态规划是线性动态规划中特殊的一类，NOIP中考到的次数也不少。

• P1048 采药
• P1060 开心的金明
• P1855 榨取kkksc03
• P5020 货币系统
• P1757 通天之分组背包
• P1064 金明的预算方案
• P2946 [USACO09MAR]Cow Frisbee Team
• P1156 垃圾陷阱
• P5322 [BJOI2019]排兵布阵
• P5289 [十二省联考2019]皮配

Part 4.3 区间动态规划

区间动态规划一般以区间作为动态规划的阶段。

• P1880 [NOI1995]石子合并
• P3146 [USACO16OPEN]248
• P1063 能量项链
• P1005 矩阵取数游戏
• P4170 [CQOI2007]涂色
• P4302 [SCOI2003]字符串折叠
• P2466 [SDOI2008]Sue的小球

Part 4.4 树形动态规划

树形动态规划，即在树上进行的动态规划。

因为树的递归性质，树形动态规划一般都是递归求解的。

• P1352 没有上司的舞会
• P1040 加分二叉树
• P1122 最大子树和
• P1273 有线电视网
• P2014 选课
• P2585 [ZJOI2006]三色二叉树
• P3047 [USACO12FEB]Nearby Cows
• P3698 [CQOI2017]小Q的棋盘
• P5658 括号树
• P2607 [ZJOI2008]骑士
• P3177 [HAOI2015]树上染色
• P4395 [BOI2003]Gem
• P4516 [JSOI2018]潜入行动

Part 4.5 状态压缩动态规划

将一个状态压缩为一个整数（通常为二进制数），就可以在更为方便地进行状态转移的同时，达到节约空间的目的。

• P2704 [NOI2001]炮兵阵地
• P1879 [USACO06NOV]Corn Fields
• P1896 [SCOI2005]互不侵犯
• P3092 [USACO13NOV]No Change
• P3694 邦邦的大合唱站队
• P4925 [1007]Scarlet的字符串不可能这么可爱
• P2157 [SDOI2009]学校食堂
• P2167 [SDOI2009]Bill的挑战
• P2396 yyy loves Maths VII
• P4363 [九省联考2018]一双木棋
• P5005 中国象棋 – 摆上马
• P2150 [NOI2015]寿司晚宴

Part 4.6 倍增优化动态规划

利用倍增的方式，我们可以将状态转移的效率大大提高。

• P1613 跑路
• P1081 开车旅行
• P5024 保卫王国

Part 4.7 数据结构优化动态规划

利用数据结构来维护已有信息，也可以达到优化状态转移的目的。

• P4719 【模板】动态dp
• P4751 动态dp【加强版】
• P3287 [SCOI2014]方伯伯的玉米田
• P2605 [ZJOI2010]基站选址

Part 4.8 单调队列优化动态规划

借助单调队列，排除不可能的决策，可以起到优化状态转移的效果。

• P1776 宝物筛选
• P3089 [USACO13NOV]Pogo-Cow
• P3572 [POI2014]PTA-Little Bird
• P3522 [POI2011]TEM-Temperature
• P4544 [USACO10NOV]Buying Feed
• P5665 划分
• P1973 [NOI2011]Noi嘉年华
• P2569 [SCOI2010]股票交易
• P4852 yyf hates choukapai

Part 4.9 斜率优化动态规划

通过用单调队列维护一个凸壳，来达到优化转移的目的。

• P2900 [USACO08MAR]Land Acquisition
• P3195 [HNOI2008]玩具装箱
• P3628 [APIO2010]特别行动队
• P3648 [APIO2014]序列分割
• P4027 [NOI2007]货币兑换
• P4360 [CEOI2004]锯木厂选址
• P5468 [NOI2019]回家路线
• P2305 [NOI2014]购票

Part 4.10 决策单调性优化动态规划

利用决策间的递变规律，也能实现优化状态转移的目的。

• P3515 [POI2011]Lightning Conductor
• P4767 [IOI2000]邮局
• P1912 [NOI2009]诗人小G
• P1973 [NOI2011]Noi嘉年华
• P3724 [AH2017/HNOI2017]大佬
• P5574 [CmdOI2019]任务分配问题

Part 4.11 数位统计类动态规划

统计一个区间中满足条件的数有多少，就是数位统计类动态规划。

• P2602 [ZJOI2010]数字计数
• P3281 [SCOI2013]数数
• P2518 [HAOI2010]计数
• P2657 [SCOI2009]windy数
• P3286 [SCOI2014]方伯伯的商场之旅
• P4124 [CQOI2016]手机号码
• P4999 烦人的数学作业
• P2606 [ZJOI2010]排列计数
• P4798 [CEOI2015 Day1]卡尔文球锦标赛

Part 4.12 轮廓线动态规划

轮廓线动态规划（即常说的插头 DP）是一种特殊的状压动态规划，通过以轮廓线为状态来实现状态转移。

• P5056 【模板】插头dp
• P2289 [HNOI2004]邮递员
• P2337 [SCOI2012]喵星人的入侵
• P5347 【XR-1】俄罗斯方块

Part 5 字符串

字符串问题有很多自己的特点。

Part 5.1 字符串哈希

字符串哈希通过牺牲很小的准确率，达到快速进行字符串匹配的效果。

• P3370 【模板】字符串哈希
• P5270 无论怎样神树大人都会删库跑路
• P5537 【XR-3】系统设计

Part 5.2 KMP

KMP 算法可以用来解决模式串匹配问题。

• P3375 【模板】KMP字符串匹配
• P4391 [BOI2009]Radio Transmission
• P3435 [POI2006]OKR-Periods of Words
• P4824 [USACO15FEB]Censoring (Silver)
• P2375 [NOI2014]动物园
• P3426 [POI2005]SZA-Template
• P3193 [HNOI2008]GT考试

Part 5.3 Manacher

Manacher 可以在线性时间内求出一个字符串的最长回文子串。

• P3805 【模板】manacher算法
• P4555 [国家集训队]最长双回文串
• P1659 [国家集训队]拉拉队排练

Part 5.4 Trie树

Trie树可以像查字典一样把多个字符串组织到一棵树上。

• P3879 [TJOI2010]阅读理解
• P2292 [HNOI2004]L语言
• P2922 [USACO08DEC]Secret Message
• P3065 [USACO12DEC]First!
• P3294 [SCOI2016]背单词
• P4407 [JSOI2009]电子字典
• P4551 最长异或路径
• P4683 [IOI2008]Type Printer
• P3783 [SDOI2017]天才黑客

Part 5.5 AC自动机

AC自动机可以看成是 KMP 和 Trie 的结合体，用于解决多字符串匹配问题。

• P3808 【模板】AC自动机（简单版）
• P3796 【模板】AC自动机（加强版）
• P5357 【模板】AC自动机（二次加强版）
• P3121 [USACO15FEB]Censoring (Gold)
• P2414 [NOI2011]阿狸的打字机
• P3966 [TJOI2013]单词
• P2444 [POI2000]病毒
• P3311 [SDOI2014]数数
• P4052 [JSOI2007]文本生成器
• P5599 【XR-4】文本编辑器

Part 5.6 回文自动机

回文自动机是解决回文串问题的有力工具。

• P5496 【模板】回文自动机（PAM）
• P3649 [APIO2014]回文串
• P4287 [SHOI2011]双倍回文
• P4762 [CERC2014]Virus synthesis

Part 5.7 后缀数组

后缀数组可以解决很多字符串匹配的问题。

• P3809 【模板】后缀排序
• P5353 【模板】树上后缀排序
• P2336 [SCOI2012]喵星球上的点名
• P2463 [SDOI2008]Sandy的卡片
• P2852 [USACO06DEC]Milk Patterns
• P4051 [JSOI2007]字符加密
• P1117 [NOI2016]优秀的拆分
• P2178 [NOI2015]品酒大会
• P5346 【XR-1】柯南家族
• P5576 [CmdOI2019]口头禅

Part 5.8 后缀自动机

后缀自动机是一种处理字符串问题的强大工具。

• P3804 【模板】后缀自动机
• P3649 [APIO2014]回文串
• P3975 [TJOI2015]弦论
• P4248 [AHOI2013]差异
• P5341 [TJOI2019]甲苯先生和大中锋的字符串
• P4770 [NOI2018]你的名字
• P5284 [十二省联考2019]字符串问题
• P5319 [BJOI2019]奥术神杖

Part 6 数学

OI 中的数学知识很多，也有些杂乱。

Part 6.1 位运算

将十进制整数转换为二进制后，有很多按位运算的运算符。

如果能善于利用位运算的一些性质，往往能达到事半功倍的效果。

• P5657 格雷码
• P5514 [MtOI2019]永夜的报应
• P5538 【XR-3】Namid[A]me
• P5539 【XR-3】Unknown Mother-Goose
• P5523 [yLOI2019]珍珠

Part 6.2 整除相关

与整除相关的概念有很多，比较常用的有素数，最大公约数和欧拉函数。

Part 6.2.1 素数

素数，指的是除 1 和它本身之外没有其他约数的数。

• P4718 【模板】Pollard-Rho算法
• P1075 质因数分解
• P2441 角色属性树
• P5535 【XR-3】小道消息

Part 6.2.2 最大公约数

如果两个数有一个共同的约数，那么这个约数就被称为公约数。最大公约数就是指这两个数的所有公约数中，最大的一个。

求解两个数的最大公约数，可以采用欧几里得算法解决。

• P5435 【模板】快速 GCD
• P5436 【XR-2】缘分
• P1029 最大公约数和最小公倍数问题
• P1414 又是毕业季II
• P2152 [SDOI2009]SuperGCD
• P1072 Hankson 的趣味题

Part 6.2.3 欧拉函数

欧拉函数 表示了小于 的数字中，与 互质的数字个数。

• P2158 [SDOI2008]仪仗队
• P2568 GCD
• P2398 GCD SUM
• P4139 上帝与集合的正确用法

Part 6.3 同余方程

求解同余方程往往可以引出不少话题。

Part 6.3.1 线性同余方程&乘法逆元

线性同余方程是同余方程中最基础的内容。

• P4549 【模板】裴蜀定理
• P2613 【模板】有理数取余
• P3811 【模板】乘法逆元
• P5431 【模板】乘法逆元2
• P1082 同余方程
• P3951 小凯的疑惑
• P1516 青蛙的约会

Part 6.3.2 中国剩余定理

中国剩余定理可以快速解一元线性同余方程组。

• P4777 【模板】扩展中国剩余定理（EXCRT）
• P3868 [TJOI2009]猜数字
• P2480 [SDOI2010]古代猪文
• P4774 [NOI2018]屠龙勇士
• P5345 【XR-1】快乐肥宅

Part 6.3.3 高次同余方程

BSGS 算法可以高效计算离散对数。

而高次剩余的求解更加复杂，其中二次剩余作为高次剩余中比较特殊的情况，可以使用 Cipolla 法求解。

• P4195 【模板】exBSGS
• P5491 【模板】二次剩余
• P3306 [SDOI2013]随机数生成器
• P2485 [SDOI2011]计算器

Part 6.4 博弈论

博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。

• P2197 【模板】nim游戏
• P1288 取数游戏II
• P1290 欧几里德的游戏
• P1247 取火柴游戏
• P2252 取石子游戏

Part 6.5 概率与期望

概率和期望是紧密相连的，OI 中往往会出现和概率期望相关的动态规划问题。

• P5104 红包发红包
• P1850 换教室
• P3830 [SHOI2012]随机树
• P4564 [CTSC2018]假面
• P2473 [SCOI2008]奖励关
• P2221 [HAOI2012]高速公路
• P3239 [HNOI2015]亚瑟王
• P3750 [六省联考2017]分手是祝愿
• P4284 [SHOI2014]概率充电器
• P5249 [LnOI2019]加特林轮盘赌
• P2081 [NOI2012]迷失游乐园
• P3343 [ZJOI2015]地震后的幻想乡
• P3600 随机数生成器
• P5326 [ZJOI2019]开关

Part 6.6 组合数学

组合数学常常与计数问题，概率期望紧密相连。

Part 6.6.1 排列组合

排列组合是组合数学的基础。

• P3807 【模板】卢卡斯定理
• P2822 组合数问题
• P5520 [yLOI2019]青原樱
• P3197 [HNOI2008]越狱
• P2290 [HNOI2004]树的计数
• P4981 父子
• P4769 [NOI2018]冒泡排序
• P4931 情侣？给我烧了！（加强版）
• P5596 【XR-4】题
• P5598 【XR-4】混乱度

Part 6.6.2 卡特兰数&斯特林数

卡特兰数和斯特林数是两类常见的组合递推数列。

• P5395 【模板】第二类斯特林数·行
• P5396 【模板】第二类斯特林数·列
• P5408 【模板】第一类斯特林数·行
• P5409 【模板】第一类斯特林数·列
• P1655 小朋友的球
• P2532 [AHOI2012]树屋阶梯
• P3200 [HNOI2009]有趣的数列
• P3978 [TJOI2015]概率论
• P4091 [HEOI2016/TJOI2016]求和
• P4827 [国家集训队]Crash 的文明世界

Part 6.6.3 容斥原理

容斥原理常常用于解决集合的计数问题。

• P5664 Emiya 家今天的饭
• P1450 [HAOI2008]硬币购物
• P3214 [HNOI2011]卡农
• P3270 [JLOI2016]成绩比较
• P4336 [SHOI2016]黑暗前的幻想乡
• P4448 [AHOI2018初中组]球球的排列
• P4491 [HAOI2018]染色
• P5339 [TJOI2019]唱、跳、rap和篮球
• P5400 [CTS2019]随机立方体

Part 6.7 线性代数

线性代数主要用于解决线性关系问题。

Part 6.7.1 矩阵

利用矩阵优化数列递推，可以实现复杂度从线性到对数级的转变。

• P3390 【模板】矩阵快速幂
• P1939 【模板】矩阵加速（数列）
• P4783 【模板】矩阵求逆
• P1962 斐波那契数列
• P1349 广义斐波那契数列
• P4000 斐波那契数列
• P3758 [TJOI2017]可乐
• P4967 黑暗打击
• P5343 【XR-1】分块
• P5337 [TJOI2019]甲苯先生的字符串
• P5303 [GXOI/GZOI2019]逼死强迫症

Part 6.7.2 高斯消元

高斯消元可以用来求解方程组。

• P3389 【模板】高斯消元法
• P4387 付公主的函数
• P2447 [SDOI2010]外星千足虫
• P4035 [JSOI2008]球形空间产生器
• P5516 [MtOI2019]小铃的烦恼
• P4111 [HEOI2015]小Z的房间
• P4457 [BJOI2018]治疗之雨

Part 6.7.3 线性基

线性基可以求解最大异或和的一类问题。

• P3812 【模板】线性基
• P3857 [TJOI2008]彩灯
• P4570 [BJWC2011]元素
• P4301 [CQOI2013]新Nim游戏
• P3292 [SCOI2016]幸运数字
• P4151 [WC2011]最大XOR和路径

Part 6.8 多项式

对多项式的运算进行优化，从而能够解决规模更大的问题。

• P1919 【模板】A*B Problem升级版（FFT快速傅里叶）
• P3803 【模板】多项式乘法（FFT）
• P4238 【模板】多项式求逆
• P4245 【模板】任意模数NTT
• P4512 【模板】多项式除法
• P4717 【模板】快速沃尔什变换
• P4721 【模板】分治 FFT
• P4725 【模板】多项式对数函数
• P4726 【模板】多项式指数函数
• P4781 【模板】拉格朗日插值
• P5050 【模板】多项式多点求值
• P5158 【模板】多项式快速插值
• P5205 【模板】多项式开根
• P5245 【模板】多项式快速幂
• P5273 【模板】多项式幂函数 (加强版)
• P5282 【模板】快速阶乘算法
• P5373 【模板】多项式复合函数
• P5383 【模板】普通多项式转下降幂多项式
• P5393 【模板】下降幂多项式转普通多项式
• P5394 【模板】下降幂多项式乘法
• P3338 [ZJOI2014]力
• P3723 [AH2017/HNOI2017]礼物
• P5437 【XR-2】约定
• P5293 [HNOI2019]白兔之舞
• P5432 A/B Problem (加强版)
• P5472 [NOI2019]斗主地
• P5577 [CmdOI2019]算力训练

Part 6.9 莫比乌斯反演

运用莫比乌斯反演，我们可以将一些函数转化，从而降低计算难度。

• P3172 [CQOI2015]选数
• P2522 [HAOI2011]Problem b
• P3455 [POI2007]ZAP-Queries
• P3327 [SDOI2015]约数个数和
• P1829 [国家集训队]Crash的数字表格 / JZPTAB
• P4619 [SDOI2018]旧试题
• P3704 [SDOI2017]数字表格
• P5518 [MtOI2019]幽灵乐团

Part 6.10 筛法

利用数列的性质，有多种筛法可以求出我们想要的信息。

• P3383 【模板】线性筛素数
• P4213 【模板】杜教筛（Sum）
• P5325 【模板】Min_25筛
• P1865 A % B Problem
• P1621 集合
• P3768 简单的数学题
• P5438 【XR-2】记忆

Part 6.11 线性规划

线性规划是研究线性约束条件下线性目标函数极值问题的方法。

• P3980 [NOI2008]志愿者招募
• P4232 无意识之外的捉迷藏

Part 6.12 数值方法

在算法领域，有很多求近似值的数值方法。

Part 6.12.1 三分法

三分法可以求出一个单峰 / 单谷函数的极值。

• P3382 【模板】三分法
• P1883 函数

Part 6.12.2 自适应辛普森法

自适应辛普森法可以高效求出给定函数的数值积分。

• P4525 【模板】自适应辛普森法1
• P4526 【模板】自适应辛普森法2
• P3779 [SDOI2017]龙与地下城

Part 6.13 置换群

置换群通常用来解决一些涉及“本质不同”的计数问题。

• P4980 【模板】Polya定理
• P1446 [HNOI2008]Cards
• P2561 [AHOI2002]黑白瓷砖
• P4128 [SHOI2006]有色图
• P4727 [HNOI2009]图的同构记数

Part 7 数据结构

灵活地运用数据结构可以高效地查询并处理需要的信息。

Part 7.1 链表

在一个数列中高效插入一个元素，链表毫无疑问是最好的选择。

• P1996 约瑟夫问题
• P1160 队列安排

Part 7.2 栈

栈，是一种后进先出（FILO）的数据结构。

• P1449 后缀表达式
• P1739 表达式括号匹配
• P1981 表达式求值
• P1175 表达式的转换

Part 7.3 队列

队列，是一种先进先出（FIFO）的数据结构。

• P1540 机器翻译

Part 7.4 并查集

并查集常用于处理一些不相交集合的合并和查询问题。

• P1111 修复公路
• P3958 奶酪
• P1525 关押罪犯
• P4185 [USACO18JAN]MooTube G
• P2024 [NOI2001]食物链
• P1197 [JSOI2008]星球大战
• P1196 [NOI2002]银河英雄传说
• P1955 [NOI2015]程序自动分析

Part 7.5 二叉堆

二叉堆是一棵完全二叉树，堆中某个节点的值总是不大于或不小于其父节点的值。

• P3378 【模板】堆
• P1090 合并果子
• P1168 中位数
• P2085 最小函数值
• P2827 蚯蚓
• P3045 [USACO12FEB]Cow Coupons

Part 7.6 ST表

ST表可以离线查询区间最值。

• P3865 【模板】ST表
• P2251 质量检测
• P1816 忠诚
• P1198 [JSOI2008]最大数
• P2880 [USACO07JAN]Balanced Lineup
• P5012 水の数列
• P5344 【XR-1】逛森林
• P2048 [NOI2010]超级钢琴

Part 7.7 树状数组

树状数组是一种简洁高效的树形数据结构。

• P3374 【模板】树状数组 1
• P3368 【模板】树状数组 2
• P1908 逆序对
• P1966 火柴排队
• P3605 [USACO17JAN]Promotion Counting
• P1972 [SDOI2009]HH的项链
• P3586 [POI2015]LOG
• P4054 [JSOI2009]计数问题
• P4113 [HEOI2012]采花
• P3960 列队

Part 7.8 线段树

线段树的通用性比树状数组更强，可以处理更多涉及区间操作的题目。

• P3372 【模板】线段树 1
• P3373 【模板】线段树 2
• P5490 【模板】扫描线
• P4588 [TJOI2018]数学计算
• P1502 窗口的星星
• P2471 [SCOI2007]降雨量
• P2824 [HEOI2016/TJOI2016]排序
• P3722 [AH2017/HNOI2017]影魔
• P4097 [HEOI2013]Segment
• P4198 楼房重建
• P4513 小白逛公园
• P4556 [Vani有约会]雨天的尾巴
• P5324 [BJOI2019]删数
• P5327 [ZJOI2019]语言

Part 7.9 分块

分块是一种非常通用的暴力方法，虽然效率不如线段树和树状数组，但可以解决很多线段树和树状数组处理不了的问题。

• P3870 [TJOI2009]开关
• P3396 哈希冲突
• P3863 序列
• P1975 [国家集训队]排队
• P3710 方方方的数据结构
• P3992 [BJOI2017]开车
• P4168 [Violet]蒲公英
• P4119 [Ynoi2018]未来日记

Part 7.10 可并堆

可并堆分为左偏树和配对堆两种，它们都具有堆的性质，且可以高效合并。

• P3377 【模板】左偏树（可并堆）
• P2713 罗马游戏
• P1456 Monkey King
• P1552 [APIO2012]派遣
• P3261 [JLOI2015]城池攻占
• P3273 [SCOI2011]棘手的操作
• P4331 [BOI2004]Sequence

Part 7.11 主席树

主席树，即可持久化权值线段树。

• P2468 [SDOI2010]粟粟的书架
• P3302 [SDOI2013]森林
• P3168 [CQOI2015]任务查询系统
• P4559 [JSOI2018]列队
• P2633 Count on a tree
• P3293 [SCOI2016]美味
• P4618 [SDOI2018]原题识别

Part 7.12 平衡树

二叉搜索树可以用来维护有序序列。

为了保证查询效率，有多种使二叉搜索树保持平衡的实现方法。

• P3369 【模板】普通平衡树
• P3391 【模板】文艺平衡树（Splay）
• P3850 [TJOI2007]书架
• P4008 [NOI2003]文本编辑器
• P5338 [TJOI2019]甲苯先生的滚榜
• P2042 [NOI2005]维护数列
• P1110 [ZJOI2007]报表统计
• P3644 [APIO2015]八邻旁之桥
• P1486 [NOI2004]郁闷的出纳员
• P2710 数列
• P3224 [HNOI2012]永无乡
• P3285 [SCOI2014]方伯伯的OJ
• P5321 [BJOI2019]送别

Part 7.13 树链剖分

树链剖分可以将任意一条树上路径划分成若干条连续的链，并用线段树等数据结构高效维护链上信息。

• P3384 【模板】树链剖分
• P3313 [SDOI2014]旅行
• P2590 [ZJOI2008]树的统计
• P1505 [国家集训队]旅游
• P2486 [SDOI2011]染色
• P3258 [JLOI2014]松鼠的新家
• P4069 [SDOI2016]游戏
• P4211 [LNOI2014]LCA
• P4592 [TJOI2018]异或
• P5305 [GXOI/GZOI2019]旧词
• P5354 [Ynoi2017]由乃的OJ
• P5499 [LnOI2019]Abbi并不想研学

Part 7.14 树套树

树套树可以用来维护多维度信息。

• P3380 【模板】二逼平衡树（树套树）
• P1975 [国家集训队]排队
• P3332 [ZJOI2013]K大数查询
• P4278 带插入区间K小值
• P1903 [国家集训队]数颜色 / 维护队列
• P3759 [TJOI2017]不勤劳的图书管理员
• P3242 [HNOI2015]接水果
• P3248 [HNOI2016]树
• P5445 [APIO2019]路灯

Part 7.15 动态树

Link-Cut Tree 可以用来解决动态树一类问题。

• P3690 【模板】Link Cut Tree （动态树）
• P3203 [HNOI2010]弹飞绵羊
• P4338 [ZJOI2018]历史
• P4312 [COCI2009]OTOCI
• P1501 [国家集训队]Tree II
• P2387 [NOI2014]魔法森林
• P3348 [ZJOI2016]大森林
• P3703 [SDOI2017]树点涂色
• P4172 [WC2006]水管局长
• P4219 [BJOI2014]大融合
• P5489 EntropyIncreaser 与 动态图

Part 7.16 可持久化数据结构

可持久化数据结构实现了在更新信息的时候保留历史版本。

• P3919 【模板】可持久化数组（可持久化线段树/平衡树）
• P3834 【模板】可持久化线段树 1（主席树）
• P3402 【模板】可持久化并查集
• P3835 【模板】可持久化平衡树
• P5055 【模板】可持久化文艺平衡树
• P5283 [十二省联考2019]异或粽子

Part 7.17 K-D Tree

K-D Tree 是一种高效处理 维信息的数据结构。

• P4357 [CQOI2016]K远点对
• P4148 简单题
• P2479 [SDOI2010]捉迷藏
• P3769 [CH弱省胡策R2]TATT
• P4169 [Violet]天使玩偶/SJY摆棋子
• P4390 [BOI2007]Mokia
• P4475 巧克力王国
• P2093 [国家集训队]JZPFAR
• P5471 [NOI2019]弹跳

Part 7.18 珂朵莉树

珂朵莉树，是一种基于 std::set 的暴力数据结构，在数据随机的情况下表现优秀。

• P5251 [LnOI2019]第二代图灵机
• P5350 序列

Part 8 图论

图论是数学的一个分支，它以图为研究的对象。

Part 8.1 图的存储与遍历

这里的图论内容都比较简单，涉及图的存储以及遍历图的方式。

• P2661 信息传递
• P2921 [USACO08DEC]Trick or Treat on the Farm

Part 8.2 最短路问题

很多题目都可以转化为最短路的模型。因此，掌握最短路算法非常重要。

• P3371 【模板】单源最短路径（弱化版）
• P4779 【模板】单源最短路径（标准版）
• P5905 【模板】Johnson 全源最短路
• P1144 最短路计数
• P1462 通往奥格瑞玛的道路
• P1522 Cow Tours
• P1266 速度限制
• P4001 [ICPC-Beijing 2006]狼抓兔子
• P4568 [JLOI2011]飞行路线
• P3238 [HNOI2014]道路堵塞
• P5304 [GXOI/GZOI2019]旅行者

Part 8.3 树上问题

作为一种特殊的图，树上的问题具有很多鲜明的特点。

Part 8.3.1 二叉树

二叉树是一种特殊的树，它有很多特殊的性质。

• P1087 FBI树
• P1030 求先序排列
• P1305 新二叉树
• P1229 遍历问题
• P5018 对称二叉树
• P5597 【XR-4】复读

Part 8.3.2 树的直径

树的直径被定义为树上最远的两点间的距离。

计算树的直径，可以通过两遍 DFS 解决。

• P2195 HXY造公园
• P3629 [APIO2010]巡逻
• P5536 【XR-3】核心城市
• P1099 树网的核
• P4408 [NOI2003]逃学的小孩

Part 8.3.3 最近公共祖先

两个点的最近公共祖先，即两个点的所有公共祖先中，离根节点最远的一个节点。

求解最近公共祖先，常用的方法是树上倍增或者树链剖分。

• P3379 【模板】最近公共祖先（LCA）
• P3938 斐波那契
• P4281 [AHOI2008]紧急集合 / 聚会

Part 8.4 生成树

用 条边将图上的 个点连接起来，形成的树就被称为生成树。

• P3366 【模板】最小生成树
• P4180 【模板】严格次小生成树[BJWC2010]
• P2872 [USACO07DEC]Building Roads
• P1991 无线通讯网
• P1967 货车运输
• P4047 [JSOI2010]部落划分

Part 8.5 拓扑排序

将一个有向无环图排序，使得所有排在前面的节点不能依赖于排在后面的节点，这就是拓扑排序。

• P1113 杂务
• P1983 车站分级
• P1038 神经网络

Part 8.6 差分约束

差分约束要解决的问题是：求出一组 元不等式的一组解，使得所有约束关系都能得到满足。

• P5960 【模板】差分约束算法
• P3275 [SCOI2011]糖果
• P2294 [HNOI2005]狡猾的商人
• P4926 [1007]倍杀测量者
• P5590 赛车游戏

Part 8.7 图的连通性相关

利用 Tarjan 算法，我们可以解决很多与图的连通性相关的问题。

• P3387 【模板】缩点
• P3388 【模板】割点（割顶）
• P2341 [HAOI2006]受欢迎的牛
• P2863 [USACO06JAN]The Cow Prom
• P2746 [USACO5.3]Network of Schools
• P1407 [国家集训队]稳定婚姻
• P2272 [ZJOI2007]最大半连通子图
• P3225 [HNOI2012]矿场搭建
• P5058 [ZJOI2004]嗅探器
• P2515 [HAOI2010]软件安装

Part 8.8 二分图

二分图上的不少问题都可以转化成网络流解决，当然也有独特的其他方法。

• P3386 【模板】二分图匹配
• P2756 飞行员配对方案问题
• P1129 [ZJOI2007]矩阵游戏
• P1559 运动员最佳匹配问题
• P2423 [HEOI2012]朋友圈
• P2764 最小路径覆盖问题
• P2825 [HEOI2016/TJOI2016]游戏
• P3033 [USACO11NOV]Cow Steeplechase
• P3731 [HAOI2017]新型城市化
• P4014 分配问题
• P4617 [COCI2017-2018#5] Planinarenje

Part 8.9 网络流

网络流是图论中一个重要的分支，很多题目都可以通过建立网络流的模型来解决。

Part 8.9.1 最大流

最大流，即求网络中最大的流量。

• P3376 【模板】网络最大流
• P4722 【模板】最大流 加强版 / 预流推进
• P2065 [TJOI2011]卡片
• P2763 试题库问题
• P2472 [SCOI2007]蜥蜴
• P2754 [CTSC1999]家园
• P2765 魔术球问题
• P2766 最长不下降子序列问题
• P2805 [NOI2009]植物大战僵尸
• P3749 [六省联考2017]寿司餐厅

Part 8.9.2 最小割

最小割，即求一个边权最小的边集，使得源点和汇点不再连通。

可以证明，最大流=最小割。

• P1344 [USACO4.4]Pollutant Control
• P1345 [USACO5.4]Telecowmunication
• P2057 [SHOI2007]善意的投票
• P2598 [ZJOI2009]狼和羊的故事
• P2774 方格取数问题
• P4126 [AHOI2009]最小割
• P5039 [SHOI2010]最小生成树

Part 8.9.3 费用流

在网络流中给边加上一个参数——费用，就出现了费用流。

• P3381 【模板】最小费用最大流
• P4016 负载平衡问题
• P4452 [国家集训队]航班安排
• P2045 方格取数加强版
• P2050 [NOI2012]美食节
• P2053 [SCOI2007]修车
• P2604 [ZJOI2010]网络扩容
• P2770 航空路线问题
• P3159 [CQOI2012]交换棋子
• P3356 火星探险问题
• P3358 最长k可重区间集问题
• P4013 数字梯形问题
• P4015 运输问题
• P5331 [SNOI2019]通信

Part 8.9.4 上下界网络流

在网络流问题中给每条边的流量增加一个下界，就有了上下界网络流。

• P3980 [NOI2008]志愿者招募
• P4043 [AHOI2014/JSOI2014]支线剧情
• P4553 80人环游世界
• P4843 清理雪道

Part 8.10 2-SAT

k-SAT 问题的目标是对一些布尔变量赋值，满足限定的条件。

在 k-SAT 问题中，2-SAT 问题属于较为容易解决的一类。

• P4782 【模板】2-SAT 问题
• P4171 [JSOI2010]满汉全席
• P3825 [NOI2017]游戏
• P5332 [JSOI2019]精准预测

Part 8.11 点分治

点分治是一种可以高效统计树上路径信息的算法。

• P3806 【模板】点分治1
• P2634 [国家集训队]聪聪可可
• P2664 树上游戏
• P3714 [BJOI2017]树的难题
• P4149 [IOI2011]Race
• P3241 [HNOI2015]开店
• P4075 [SDOI2016]模式字符串
• P4183 [USACO18JAN]Cow at Large P
• P4292 [WC2010]重建计划
• P5306 [COCI2019]Transport

Part 8.12 虚树

将一些无用的点从树上删去，从而达到降低树的规模的效果。

• P2495 [SDOI2011]消耗战
• P3233 [HNOI2014]世界树
• P5360 [SDOI2019]世界地图
• P5439 【XR-2】永恒

Part 8.13 矩阵树定理

矩阵树定理可以解决图的生成树计数问题。

• P4111 [HEOI2015]小Z的房间
• P2144 [FJOI2007]轮状病毒
• P3317 [SDOI2014]重建
• P4208 [JSOI2008]最小生成树计数

Part 9 计算几何

试着用计算机来解决几何问题吧！

Part 9.1 凸包

凸包指在平面上能包含所有给定点的最小凸多边形。

• P2742 【模板】二维凸包
• P2287 [HNOI2004]最佳包裹
• P3829 [SHOI2012]信用卡凸包
• P4680 [Ynoi2018]末日时在做什么?有没有空?可以来拯救吗?
• P4557 [JSOI2018]战争
• P5403 [CTS2019]田野

Part 9.2 旋转卡壳

旋转卡壳是一种求出凸包所有对踵点对的算法。

• P1452 Beauty Contest
• P3187 [HNOI2007]最小矩形覆盖

Part 9.3 半平面交

多个半平面的交集称之为半平面交。

• P3256 [JLOI2013]赛车
• P2600 [ZJOI2008]瞭望塔
• P4196 [CQOI2006]凸多边形
• P3297 [SDOI2013]逃考
• P4250 [SCOI2015]小凸想跑步
• P5328 [ZJOI2019]浙江省选

Part 10 杂项

这里的专题，有很多都难以纳入前面的类别中，故将他们单独列入了杂项。

Part 10.1 模拟退火

模拟退火是一种随机化算法。当一个问题的方案数量极大（甚至是无穷的）而且不是一个单峰函数时，我们常使用模拟退火求解。

• P1337 [JSOI2004]平衡点 / 吊打XXX
• P2503 [HAOI2006]均分数据
• P3878 [TJOI2010]分金币

Part 10.2 0/1 分数规划

0/1 分数规划用来求一个分式的极值。

• P4377 [USACO18OPEN]Talent Show
• P3199 [HNOI2009]最小圈
• P3288 [SCOI2014]方伯伯运椰子
• P3705 [SDOI2017]新生舞会
• P4322 [JSOI2016]最佳团体

Part 10.3 离线算法

当题目不要求强制在线时，我们可以一次性读入所有询问来处理。

Part 10.3.1 CDQ 分治

CDQ 分治是一个基于分治思想的离线算法。

• P3810 【模板】三维偏序（陌上花开）
• P3157 [CQOI2011]动态逆序对
• P2487 [SDOI2011]拦截导弹
• P4690 [Ynoi2016]镜中的昆虫
• P3206 [HNOI2010]城市建设

Part 10.3.2 整体二分

整体二分，顾名思义就是把多个查询一起二分解决。

• P1527 [国家集训队]矩阵乘法
• P2617 Dynamic Rankings
• P3527 [POI2011]MET-Meteors
• P4602 [CTSC2018]混合果汁

Part 10.3.3 莫队

莫队算法可以解决不少离线区间询问问题。

• P1494 [国家集训队]小Z的袜子 /【模板】莫队
• P1903 [国家集训队]数颜色 / 维护队列 /【模板】带修莫队
• P5906 【模板】回滚莫队
• P4887 【模板】莫队二次离线（第十四分块(前体)）
• P2709 小B的询问
• P3674 小清新人渣的本愿
• P3709 大爷的字符串题
• P4074 [WC2013]糖果公园
• P5501 [LnOI2019]来者不拒，去者不追

Part 10.4 奇怪的题目

OI 界中有一些非常规套路的题目，这里放出来分享。

• P4920 [WC2015]未来程序
• P5042 [国家集训队]丢失的题面（ydc的题面）
• P5285 [十二省联考2019]骗分过样例
• P5246 [集训队互测2016]消失的源代码

Part 10.5 非传统题

在 NOI 等比赛中，非传统题正越来越频繁出现。

非传统题主要包括以下几类：提交答案题，交互题，通信题。

Part 10.5.1 提交答案题

给你一些输入，你只需要提交这些输入对应的答案，即为提交答案题。

• P1335 [NOI2013]小Q的修炼
• P1737 [NOI2016]旷野大计算
• P3614 yyy棋 II
• P3640 [APIO2013]出题人
• P3782 [WC2017]排序
• P3836 Nowruz
• P4920 [WC2015]未来程序
• P5402 [CTS2019]无处安放
• P5418 [CTSC2016]NOIP十合一
• P5600 【XR-4】尺规作图

转载与 https://studyingfather.com/archives/841