一个动态更新的洛谷综合题单
StudyingFather
2019-01-16 19:15:11
**这个题单的历史使命已经完成了,很长一段时间里将不再更新。**
**在 [Studying Father's Blog](https://studyingfather.com/archives/841) 上同时可用。(因为添加了 TOC 所以能有更好的体验感)**
**PDF 打印版本可以在 [Github](https://github.com/SFOI-Team/luogu-problem-list/releases) 上下载,您可以根据需要选择合适的版本。**
**本项目已经在 [Github](https://github.com/StudyingFather/luogu-problem-list) 上开源,欢迎各位dalao前来围观/贡献!(求Star QwQ)**
------
洛谷试炼场的题目确实很具有代表性,但是近几年以来,又有许多经典题目出现在 OI 界中,这个大题单就是作为洛谷试炼场的扩展和补充。
## Copyleft
[![](https://i.creativecommons.org/l/by-sa/4.0/88x31.png)](https://creativecommons.org/licenses/by-sa/4.0/deed.zh)
本项目采用 [知识共享署名-相同方式共享 4.0 国际许可协议](https://creativecommons.org/licenses/by-sa/4.0/deed.zh) 以及附加的 [The Star And Thank Author License](https://github.com/zTrix/sata-license) 进行许可。
换言之,您可以自由的共享并演绎该项目,但是必须给出必要的署名,并以相同方式共享本项目,并为本项目的 [Github 仓库](https://github.com/SFOI-Team/luogu-problem-list) 点赞(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. 对之前没有介绍的专题补充了介绍。
[更早版本的更新日志请点击这里查看](https://github.com/SFOI-Team/luogu-problem-list/blob/master/history.md)
## Part 0 试机题
> 三道试机题目。
- [P1000 超级玛丽游戏](https://www.luogu.com.cn/problem/P1000)
- [P1001 A+B Problem](https://www.luogu.com.cn/problem/P1001)
- [P1008 三连击](https://www.luogu.com.cn/problem/P1008)
## Part 1 入门阶段
> 本部分内容针对入门 OIer ,主要是语言基础内容。
### Part 1.1 从零开始
> 语言基础题。
- [P1421 小玉买文具](https://www.luogu.com.cn/problem/P1421)
- [P1909 买铅笔](https://www.luogu.com.cn/problem/P1909)
- [P1089 津津的储蓄计划](https://www.luogu.com.cn/problem/P1089)
- [P1085 不高兴的津津](https://www.luogu.com.cn/problem/P1085)
- [P1035 级数求和](https://www.luogu.com.cn/problem/P1035)
- [P1980 计数问题](https://www.luogu.com.cn/problem/P1980)
- [P1014 Cantor表](https://www.luogu.com.cn/problem/P1014)
- [P1307 数字反转](https://www.luogu.com.cn/problem/P1307)
### Part 1.2 数组基础
> 数组可以用于存储大量的信息。
- [P1046 陶陶摘苹果](https://www.luogu.com.cn/problem/P1046)
- [P1047 校门外的树](https://www.luogu.com.cn/problem/P1047)
- [P1427 小鱼的数字游戏](https://www.luogu.com.cn/problem/P1427)
- [P2141 珠心算测验](https://www.luogu.com.cn/problem/P2141)
- [P5594 【XR-4】模拟赛](https://www.luogu.com.cn/problem/P5594)
### Part 1.3 字符串基础
> 字符串是特殊的数组,但它也有很多自身的特点。
- [P5015 标题统计](https://www.luogu.com.cn/problem/P5015)
- [P1055 ISBN号码](https://www.luogu.com.cn/problem/P1055)
- [P1308 统计单词数](https://www.luogu.com.cn/problem/P1308)
- [P2010 回文日期](https://www.luogu.com.cn/problem/P2010)
- [P1012 拼数](https://www.luogu.com.cn/problem/P1012)
- [P5587 打字练习](https://www.luogu.com.cn/problem/P5587)
### Part 1.4 函数,递归及递推
> 这是初学者最难理解的部分,建议画出递归图来理解递归的过程。
- [P1028 数的计算](https://www.luogu.com.cn/problem/P1028)
- [P1036 选数](https://www.luogu.com.cn/problem/P1036)
- [P1464 Function](https://www.luogu.com.cn/problem/P1464)
- [P5534 【XR-3】等差数列](https://www.luogu.com.cn/problem/P5534)
- [P1192 台阶问题](https://www.luogu.com.cn/problem/P1192)
- [P1025 数的划分](https://www.luogu.com.cn/problem/P1025)
- [P4994 终于结束的起点](https://www.luogu.com.cn/problem/P4994)
## Part 2 基础算法
> 这一部分的内容包含了 OI 中的基础算法,供各位巩固基础。
>
> 当然,这里面也有一些难度比较高的题目。
### Part 2.1 模拟
> 模拟,顾名思义就是题目要求你做什么你就做什么,这样的题目很考验选手的代码组织能力。
>
> 这里不仅仅有非常基础的模拟,也有一些非常复杂的题目。
- [P1003 铺地毯](https://www.luogu.com.cn/problem/P1003)
- [P1067 多项式输出](https://www.luogu.com.cn/problem/P1067)
- [P1328 生活大爆炸版石头剪刀布](https://www.luogu.com.cn/problem/P1328)
- [P1563 玩具谜题](https://www.luogu.com.cn/problem/P1563)
- [P1042 乒乓球](https://www.luogu.com.cn/problem/P1042)
- [P1179 数字统计](https://www.luogu.com.cn/problem/P1179)
- [P2615 神奇的幻方](https://www.luogu.com.cn/problem/P2615)
- [P3952 时间复杂度](https://www.luogu.com.cn/problem/P3952)
- [P2482 [SDOI2010]猪国杀](https://www.luogu.com.cn/problem/P2482)
- [P5380 [THUPC2019]鸭棋](https://www.luogu.com.cn/problem/P5380)
### Part 2.2 排序算法
> 通过排序,我们可以将数据有序化,这让我们对数据的处理方便了很多。
- [P1177 【模板】快速排序](https://www.luogu.com.cn/problem/P1177)
- [P1059 明明的随机数](https://www.luogu.com.cn/problem/P1059)
- [P1068 分数线划定](https://www.luogu.com.cn/problem/P1068)
- [P1051 谁拿了最多奖学金](https://www.luogu.com.cn/problem/P1051)
- [P1309 瑞士轮](https://www.luogu.com.cn/problem/P1309)
- [P1908 逆序对](https://www.luogu.com.cn/problem/P1908)
### Part 2.3 二分答案
> 对一个满足单调性质的问题,我们可以采用二分答案的方法来解决。
- [P1024 一元三次方程求解](https://www.luogu.com.cn/problem/P1024)
- [P2678 跳石头](https://www.luogu.com.cn/problem/P2678)
- [P1316 丢瓶盖](https://www.luogu.com.cn/problem/P1316)
- [P1902 刺杀大使](https://www.luogu.com.cn/problem/P1902)
- [P1314 聪明的质监员](https://www.luogu.com.cn/problem/P1314)
- [P1083 借教室](https://www.luogu.com.cn/problem/P1083)
- [P4343 [SHOI2015]自动刷题机](https://www.luogu.com.cn/problem/P4343)
### Part 2.4 分治
> 分治,即分而治之,将大问题分解为小问题,分别求解,最后合并结果。
- [P1226 【模板】快速幂||取余运算](https://www.luogu.com.cn/problem/P1226)
- [P1010 幂次方](https://www.luogu.com.cn/problem/P1010)
- [P1429 平面最近点对(加强版)](https://www.luogu.com.cn/problem/P1429)
- [P3612 [USACO17JAN]Secret Cow Code](https://www.luogu.com.cn/problem/P3612)
### Part 2.5 贪心
> 贪心,指的是决策时都采取当前最优解的算法。有的时候,这样做确实可以获得最优解。
- [P1208 [USACO1.3]Mixing Milk](https://www.luogu.com.cn/problem/P1208)
- [P4995 跳跳!](https://www.luogu.com.cn/problem/P4995)
- [P1094 纪念品分组](https://www.luogu.com.cn/problem/P1094)
- [P1199 三国游戏](https://www.luogu.com.cn/problem/P1199)
- [P2672 推销员](https://www.luogu.com.cn/problem/P2672)
- [P1080 国王游戏](https://www.luogu.com.cn/problem/P1080)
- [P2123 皇后游戏](https://www.luogu.com.cn/problem/P2123)
- [P5521 [yLOI2019]梅深不见冬](https://www.luogu.com.cn/problem/P5521)
### Part 2.6 构造
> 构造题是一种形式灵活多样的题型。正是因为这个特点,使得构造题没有一种通用的方法。
- [P3599 Koishi Loves Construction](https://www.luogu.com.cn/problem/P3599)
- [P5441 【XR-2】伤痕](https://www.luogu.com.cn/problem/P5441)
- [P5595 【XR-4】歌唱比赛](https://www.luogu.com.cn/problem/P5595)
### Part 2.7 高精度
> 在 C++ 中,long long 都无法表示我们需要的整数时怎么办?那就用高精度吧!
- [P1601 A+B Problem(高精)](https://www.luogu.com.cn/problem/P1601)
- [P2142 高精度减法](https://www.luogu.com.cn/problem/P2142)
- [P1303 A\*B Problem](https://www.luogu.com.cn/problem/P1303)
- [P1480 A/B Problem](https://www.luogu.com.cn/problem/P1480)
- [P1009 阶乘之和](https://www.luogu.com.cn/problem/P1009)
### Part 2.8 前缀和 & 差分
> 前缀和是一种重要的预处理,能大大降低查询的时间复杂度,而差分则是一种和前缀和相对的策略。
- [P3131 [USACO16JAN]Subsequences Summing to Sevens](https://www.luogu.com.cn/problem/P3131)
- [P1387 最大正方形](https://www.luogu.com.cn/problem/P1387)
- [P3397 地毯](https://www.luogu.com.cn/problem/P3397)
- [P2280 [HNOI2003]激光炸弹](https://www.luogu.com.cn/problem/P2280)
- [P4552 [Poetize6] IncDec Sequence](https://www.luogu.com.cn/problem/P4552)
## Part 3 搜索
> 搜索其实就是高级的枚举,很多题目都可以用搜索完成。就算不能,搜索也是骗分神器。
### Part 3.1 深度优先搜索
> 深度优先搜索(DFS),即按照深度优先的顺序搜索的算法。
>
> 深度优先搜索一般使用栈来实现。
- [P1219 八皇后](https://www.luogu.com.cn/problem/P1219)
- [P1019 单词接龙](https://www.luogu.com.cn/problem/P1019)
- [P5194 [USACO05DEC]Scales](https://www.luogu.com.cn/problem/P5194)
- [P5440 【XR-2】奇迹](https://www.luogu.com.cn/problem/P5440)
- [P1378 油滴扩展](https://www.luogu.com.cn/problem/P1378)
### Part 3.2 广度优先搜索
> 广度优先搜索(BFS),即优先扩展浅层节点,逐渐深入的搜索算法。
>
> 广度优先搜索一般使用队列来实现。
- [P1162 填涂颜色](https://www.luogu.com.cn/problem/P1162)
- [P1443 马的遍历](https://www.luogu.com.cn/problem/P1443)
- [P3956 棋盘](https://www.luogu.com.cn/problem/P3956)
- [P1032 字串变换](https://www.luogu.com.cn/problem/P1032)
- [P1126 机器人搬重物](https://www.luogu.com.cn/problem/P1126)
### Part 3.3 记忆化搜索
> 通过将已经遍历的状态记录下来,从而减少重复的搜索量,这就是记忆化搜索。
>
> 动态规划的时候,记忆化搜索也是一种高效简洁的实现方式。
- [P1514 引水入城](https://www.luogu.com.cn/problem/P1514)
- [P1535 游荡的奶牛](https://www.luogu.com.cn/problem/P1535)
- [P1434 [SHOI2002]滑雪](https://www.luogu.com.cn/problem/P1434)
- [P3953 逛公园](https://www.luogu.com.cn/problem/P3953)
### Part 3.4 搜索的剪枝
> 对于一些不必要搜索的部分,我们可以避免访问这些状态,从而提高搜索效率。
- [P1120 小木棍 [数据加强版]](https://www.luogu.com.cn/problem/P1120)
- [P1312 Mayan游戏](https://www.luogu.com.cn/problem/P1312)
- [P1074 靶形数独](https://www.luogu.com.cn/problem/P1074)
### Part 3.5 双向搜索
> 在搜索时,如果能从初态和终态出发,同时进行搜索,就可以减小搜索树的规模,提高时间效率。
- [P3067 [USACO12OPEN]Balanced Cow Subsets](https://www.luogu.com.cn/problem/P3067)
- [P4799 [CEOI2015 Day2]世界冰球锦标赛](https://www.luogu.com.cn/problem/P4799)
- [P5195 [USACO05DEC]Knights of Ni](https://www.luogu.com.cn/problem/P5195)
### Part 3.6 A\*
> 在 BFS 中,如果能设计一个合理的估价函数,就可以更快扩展到最优解。这就是 A\*算法。
- [P1379 八数码难题](https://www.luogu.com.cn/problem/P1379)
### Part 3.7 IDA\*
> 像 BFS 那样,每次只扩展一层节点,却采用 DFS 方式来遍历搜索树,这就是迭代加深搜索。
>
> 再加上一个估价函数来减小搜索量,就是 IDA\*了。
- [P2324 [SCOI2005]骑士精神](https://www.luogu.com.cn/problem/P2324)
- [P2534 [AHOI2012]铁盘整理](https://www.luogu.com.cn/problem/P2534)
### Part 3.8 DLX
> 算法 X 是通过回溯法求解精确覆盖问题的算法,而删除列这一操作可以使用舞蹈链加速。
- [P4929 【模板】舞蹈链(DLX)](https://www.luogu.com.cn/problem/P4929)
- [P4205 [NOI2005]智慧珠游戏](https://www.luogu.com.cn/problem/P4205)
## Part 4 动态规划
> 动态规划是一种重要的思维方法,通过利用已有的子问题信息高效求出当前问题的最优解。
### Part 4.1 线性动态规划
> 线性动态规划,即具有线性阶段划分的动态规划。
- [P1216 数字三角形](https://www.luogu.com.cn/problem/P1216)
- [P1020 导弹拦截](https://www.luogu.com.cn/problem/P1020)
- [P1091 合唱队形](https://www.luogu.com.cn/problem/P1091)
- [P1095 守望者的逃离](https://www.luogu.com.cn/problem/P1095)
- [P1541 乌龟棋](https://www.luogu.com.cn/problem/P1541)
- [P1868 饥饿的奶牛](https://www.luogu.com.cn/problem/P1868)
- [P2679 子串](https://www.luogu.com.cn/problem/P2679)
- [P2501 [HAOI2006]数字序列](https://www.luogu.com.cn/problem/P2501)
- [P3336 [ZJOI2013]话旧](https://www.luogu.com.cn/problem/P3336)
- [P3558 [POI2013]BAJ-Bytecomputer](https://www.luogu.com.cn/problem/P3558)
- [P4158 [SCOI2009]粉刷匠](https://www.luogu.com.cn/problem/P4158)
- [P5301 [GXOI/GZOI2019]宝牌一大堆](https://www.luogu.com.cn/problem/P5301)
### Part 4.2 背包动态规划
> 背包动态规划是线性动态规划中特殊的一类,NOIP中考到的次数也不少。
- [P1048 采药](https://www.luogu.com.cn/problem/P1048)
- [P1060 开心的金明](https://www.luogu.com.cn/problem/P1060)
- [P1855 榨取kkksc03](https://www.luogu.com.cn/problem/P1855)
- [P5020 货币系统](https://www.luogu.com.cn/problem/P5020)
- [P1757 通天之分组背包](https://www.luogu.com.cn/problem/P1757)
- [P1064 金明的预算方案](https://www.luogu.com.cn/problem/P1064)
- [P2946 [USACO09MAR]Cow Frisbee Team](https://www.luogu.com.cn/problem/P2946)
- [P1156 垃圾陷阱](https://www.luogu.com.cn/problem/P1156)
- [P5322 [BJOI2019]排兵布阵](https://www.luogu.com.cn/problem/P5322)
- [P5289 [十二省联考2019]皮配](https://www.luogu.com.cn/problem/P5289)
### Part 4.3 区间动态规划
> 区间动态规划一般以区间作为动态规划的阶段。
- [P1880 [NOI1995]石子合并](https://www.luogu.com.cn/problem/P1880)
- [P3146 [USACO16OPEN]248](https://www.luogu.com.cn/problem/P3146)
- [P1063 能量项链](https://www.luogu.com.cn/problem/P1063)
- [P1005 矩阵取数游戏](https://www.luogu.com.cn/problem/P1005)
- [P4170 [CQOI2007]涂色](https://www.luogu.com.cn/problem/P4170)
- [P4302 [SCOI2003]字符串折叠](https://www.luogu.com.cn/problem/P4302)
- [P2466 [SDOI2008]Sue的小球](https://www.luogu.com.cn/problem/P2466)
### Part 4.4 树形动态规划
> 树形动态规划,即在树上进行的动态规划。
>
> 因为树的递归性质,树形动态规划一般都是递归求解的。
- [P1352 没有上司的舞会](https://www.luogu.com.cn/problem/P1352)
- [P1040 加分二叉树](https://www.luogu.com.cn/problem/P1040)
- [P1122 最大子树和](https://www.luogu.com.cn/problem/P1122)
- [P1273 有线电视网](https://www.luogu.com.cn/problem/P1273)
- [P2014 选课](https://www.luogu.com.cn/problem/P2014)
- [P2585 [ZJOI2006]三色二叉树](https://www.luogu.com.cn/problem/P2585)
- [P3047 [USACO12FEB]Nearby Cows](https://www.luogu.com.cn/problem/P3047)
- [P3698 [CQOI2017]小Q的棋盘](https://www.luogu.com.cn/problem/P3698)
- [P5658 括号树](https://www.luogu.com.cn/problem/P5658)
- [P2607 [ZJOI2008]骑士](https://www.luogu.com.cn/problem/P2607)
- [P3177 [HAOI2015]树上染色](https://www.luogu.com.cn/problem/P3177)
- [P4395 [BOI2003]Gem](https://www.luogu.com.cn/problem/P4395)
- [P4516 [JSOI2018]潜入行动](https://www.luogu.com.cn/problem/P4516)
### Part 4.5 状态压缩动态规划
> 将一个状态压缩为一个整数(通常为二进制数),就可以在更为方便地进行状态转移的同时,达到节约空间的目的。
- [P2704 [NOI2001]炮兵阵地](https://www.luogu.com.cn/problem/P2704)
- [P1879 [USACO06NOV]Corn Fields](https://www.luogu.com.cn/problem/P1879)
- [P1896 [SCOI2005]互不侵犯](https://www.luogu.com.cn/problem/P1896)
- [P3092 [USACO13NOV]No Change](https://www.luogu.com.cn/problem/P3092)
- [P3694 邦邦的大合唱站队](https://www.luogu.com.cn/problem/P3694)
- [P4925 [1007]Scarlet的字符串不可能这么可爱](https://www.luogu.com.cn/problem/P4925)
- [P2157 [SDOI2009]学校食堂](https://www.luogu.com.cn/problem/P2157)
- [P2167 [SDOI2009]Bill的挑战](https://www.luogu.com.cn/problem/P2167)
- [P2396 yyy loves Maths VII](https://www.luogu.com.cn/problem/P2396)
- [P4363 [九省联考2018]一双木棋](https://www.luogu.com.cn/problem/P4363)
- [P5005 中国象棋 - 摆上马](https://www.luogu.com.cn/problem/P5005)
- [P2150 [NOI2015]寿司晚宴](https://www.luogu.com.cn/problem/P2150)
### Part 4.6 倍增优化动态规划
> 利用倍增的方式,我们可以将状态转移的效率大大提高。
- [P1613 跑路](https://www.luogu.com.cn/problem/P1613)
- [P1081 开车旅行](https://www.luogu.com.cn/problem/P1081)
- [P5024 保卫王国](https://www.luogu.com.cn/problem/P5024)
### Part 4.7 数据结构优化动态规划
> 利用数据结构来维护已有信息,也可以达到优化状态转移的目的。
- [P4719 【模板】动态dp](https://www.luogu.com.cn/problem/P4719)
- [P4751 动态dp【加强版】](https://www.luogu.com.cn/problem/P4751)
- [P3287 [SCOI2014]方伯伯的玉米田](https://www.luogu.com.cn/problem/P3287)
- [P2605 [ZJOI2010]基站选址](https://www.luogu.com.cn/problem/P2605)
### Part 4.8 单调队列优化动态规划
> 借助单调队列,排除不可能的决策,可以起到优化状态转移的效果。
- [P1776 宝物筛选](https://www.luogu.com.cn/problem/P1776)
- [P3089 [USACO13NOV]Pogo-Cow](https://www.luogu.com.cn/problem/P3089)
- [P3572 [POI2014]PTA-Little Bird](https://www.luogu.com.cn/problem/P3572)
- [P3522 [POI2011]TEM-Temperature](https://www.luogu.com.cn/problem/P3522)
- [P4544 [USACO10NOV]Buying Feed](https://www.luogu.com.cn/problem/P4544)
- [P5665 划分](https://www.luogu.com.cn/problem/P5665)
- [P1973 [NOI2011]Noi嘉年华](https://www.luogu.com.cn/problem/P1973)
- [P2569 [SCOI2010]股票交易](https://www.luogu.com.cn/problem/P2569)
- [P4852 yyf hates choukapai](https://www.luogu.com.cn/problem/P4852)
### Part 4.9 斜率优化动态规划
> 通过用单调队列维护一个凸壳,来达到优化转移的目的。
- [P2900 [USACO08MAR]Land Acquisition](https://www.luogu.com.cn/problem/P2900)
- [P3195 [HNOI2008]玩具装箱](https://www.luogu.com.cn/problem/P3195)
- [P3628 [APIO2010]特别行动队](https://www.luogu.com.cn/problem/P3628)
- [P3648 [APIO2014]序列分割](https://www.luogu.com.cn/problem/P3648)
- [P4027 [NOI2007]货币兑换](https://www.luogu.com.cn/problem/P4027)
- [P4360 [CEOI2004]锯木厂选址](https://www.luogu.com.cn/problem/P4360)
- [P5468 [NOI2019]回家路线](https://www.luogu.com.cn/problem/P5468)
- [P2305 [NOI2014]购票](https://www.luogu.com.cn/problem/P2305)
### Part 4.10 决策单调性优化动态规划
> 利用决策间的递变规律,也能实现优化状态转移的目的。
- [P3515 [POI2011]Lightning Conductor](https://www.luogu.com.cn/problem/P3515)
- [P4767 [IOI2000]邮局](https://www.luogu.com.cn/problem/P4767)
- [P1912 [NOI2009]诗人小G](https://www.luogu.com.cn/problem/P1912)
- [P1973 [NOI2011]Noi嘉年华](https://www.luogu.com.cn/problem/P1973)
- [P3724 [AH2017/HNOI2017]大佬](https://www.luogu.com.cn/problem/P3724)
- [P5574 [CmdOI2019]任务分配问题](https://www.luogu.com.cn/problem/P5574)
### Part 4.11 数位统计类动态规划
> 统计一个区间中满足条件的数有多少,就是数位统计类动态规划。
- [P2602 [ZJOI2010]数字计数](https://www.luogu.com.cn/problem/P2602)
- [P3281 [SCOI2013]数数](https://www.luogu.com.cn/problem/P3281)
- [P2518 [HAOI2010]计数](https://www.luogu.com.cn/problem/P2518)
- [P2657 [SCOI2009]windy数](https://www.luogu.com.cn/problem/P2657)
- [P3286 [SCOI2014]方伯伯的商场之旅](https://www.luogu.com.cn/problem/P3286)
- [P4124 [CQOI2016]手机号码](https://www.luogu.com.cn/problem/P4124)
- [P4999 烦人的数学作业](https://www.luogu.com.cn/problem/P4999)
- [P2606 [ZJOI2010]排列计数](https://www.luogu.com.cn/problem/P2606)
- [P4798 [CEOI2015 Day1]卡尔文球锦标赛](https://www.luogu.com.cn/problem/P4798)
### Part 4.12 轮廓线动态规划
> 轮廓线动态规划(即常说的插头 DP)是一种特殊的状压动态规划,通过以轮廓线为状态来实现状态转移。
- [P5056 【模板】插头dp](https://www.luogu.com.cn/problem/P5056)
- [P2289 [HNOI2004]邮递员](https://www.luogu.com.cn/problem/P2289)
- [P2337 [SCOI2012]喵星人的入侵](https://www.luogu.com.cn/problem/P2337)
- [P5347 【XR-1】俄罗斯方块](https://www.luogu.com.cn/problem/P5347)
## Part 5 字符串
> 字符串问题有很多自己的特点。
### Part 5.1 字符串哈希
> 字符串哈希通过牺牲很小的准确率,达到快速进行字符串匹配的效果。
- [P3370 【模板】字符串哈希](https://www.luogu.com.cn/problem/P3370)
- [P5270 无论怎样神树大人都会删库跑路](https://www.luogu.com.cn/problem/P5270)
- [P5537 【XR-3】系统设计](https://www.luogu.com.cn/problem/P5537)
### Part 5.2 KMP
> KMP 算法可以用来解决模式串匹配问题。
- [P3375 【模板】KMP字符串匹配](https://www.luogu.com.cn/problem/P3375)
- [P4391 [BOI2009]Radio Transmission](https://www.luogu.com.cn/problem/P4391)
- [P3435 [POI2006]OKR-Periods of Words](https://www.luogu.com.cn/problem/P3435)
- [P4824 [USACO15FEB]Censoring (Silver)](https://www.luogu.com.cn/problem/P4824)
- [P2375 [NOI2014]动物园](https://www.luogu.com.cn/problem/P2375)
- [P3426 [POI2005]SZA-Template](https://www.luogu.com.cn/problem/P3426)
- [P3193 [HNOI2008]GT考试](https://www.luogu.com.cn/problem/P3193)
### Part 5.3 Manacher
> Manacher 可以在线性时间内求出一个字符串的最长回文子串。
- [P3805 【模板】manacher算法](https://www.luogu.com.cn/problem/P3805)
- [P4555 [国家集训队]最长双回文串](https://www.luogu.com.cn/problem/P4555)
- [P1659 [国家集训队]拉拉队排练](https://www.luogu.com.cn/problem/P1659)
### Part 5.4 Trie树
> Trie树可以像查字典一样把多个字符串组织到一棵树上。
- [P3879 [TJOI2010]阅读理解](https://www.luogu.com.cn/problem/P3879)
- [P2292 [HNOI2004]L语言](https://www.luogu.com.cn/problem/P2292)
- [P2922 [USACO08DEC]Secret Message](https://www.luogu.com.cn/problem/P2922)
- [P3065 [USACO12DEC]First!](https://www.luogu.com.cn/problem/P3065)
- [P3294 [SCOI2016]背单词](https://www.luogu.com.cn/problem/P3294)
- [P4407 [JSOI2009]电子字典](https://www.luogu.com.cn/problem/P4407)
- [P4551 最长异或路径](https://www.luogu.com.cn/problem/P4551)
- [P4683 [IOI2008]Type Printer](https://www.luogu.com.cn/problem/P4683)
- [P3783 [SDOI2017]天才黑客](https://www.luogu.com.cn/problem/P3783)
### Part 5.5 AC自动机
> AC自动机可以看成是 KMP 和 Trie 的结合体,用于解决多字符串匹配问题。
- [P3808 【模板】AC自动机(简单版)](https://www.luogu.com.cn/problem/P3808)
- [P3796 【模板】AC自动机(加强版)](https://www.luogu.com.cn/problem/P3796)
- [P5357 【模板】AC自动机(二次加强版)](https://www.luogu.com.cn/problem/P5357)
- [P3121 [USACO15FEB]Censoring (Gold)](https://www.luogu.com.cn/problem/P3121)
- [P2414 [NOI2011]阿狸的打字机](https://www.luogu.com.cn/problem/P2414)
- [P3966 [TJOI2013]单词](https://www.luogu.com.cn/problem/P3966)
- [P2444 [POI2000]病毒](https://www.luogu.com.cn/problem/P2444)
- [P3311 [SDOI2014]数数](https://www.luogu.com.cn/problem/P3311)
- [P4052 [JSOI2007]文本生成器](https://www.luogu.com.cn/problem/P4052)
- [P5599 【XR-4】文本编辑器](https://www.luogu.com.cn/problem/P5599)
### Part 5.6 回文自动机
> 回文自动机是解决回文串问题的有力工具。
- [P5496 【模板】回文自动机(PAM)](https://www.luogu.com.cn/problem/P5496)
- [P3649 [APIO2014]回文串](https://www.luogu.com.cn/problem/P3649)
- [P4287 [SHOI2011]双倍回文](https://www.luogu.com.cn/problem/solution/P4287)
- [P4762 [CERC2014]Virus synthesis](https://www.luogu.com.cn/problem/P4762)
### Part 5.7 后缀数组
> 后缀数组可以解决很多字符串匹配的问题。
- [P3809 【模板】后缀排序](https://www.luogu.com.cn/problem/P3809)
- [P5353 【模板】树上后缀排序](https://www.luogu.com.cn/problem/P5353)
- [P2336 [SCOI2012]喵星球上的点名](https://www.luogu.com.cn/problem/P2336)
- [P2463 [SDOI2008]Sandy的卡片](https://www.luogu.com.cn/problem/P2463)
- [P2852 [USACO06DEC]Milk Patterns](https://www.luogu.com.cn/problem/P2852)
- [P4051 [JSOI2007]字符加密](https://www.luogu.com.cn/problem/P4051)
- [P1117 [NOI2016]优秀的拆分](https://www.luogu.com.cn/problem/P1117)
- [P2178 [NOI2015]品酒大会](https://www.luogu.com.cn/problem/P2178)
- [P5346 【XR-1】柯南家族](https://www.luogu.com.cn/problem/P5346)
- [P5576 [CmdOI2019]口头禅](https://www.luogu.com.cn/problem/P5576)
### Part 5.8 后缀自动机
> 后缀自动机是一种处理字符串问题的强大工具。
- [P3804 【模板】后缀自动机](https://www.luogu.com.cn/problem/P3804)
- [P3649 [APIO2014]回文串](https://www.luogu.com.cn/problem/P3649)
- [P3975 [TJOI2015]弦论](https://www.luogu.com.cn/problem/P3975)
- [P4248 [AHOI2013]差异](https://www.luogu.com.cn/problem/P4248)
- [P5341 [TJOI2019]甲苯先生和大中锋的字符串](https://www.luogu.com.cn/problem/P5341)
- [P4770 [NOI2018]你的名字](https://www.luogu.com.cn/problem/P4770)
- [P5284 [十二省联考2019]字符串问题](https://www.luogu.com.cn/problem/P5284)
- [P5319 [BJOI2019]奥术神杖](https://www.luogu.com.cn/problem/P5319)
## Part 6 数学
> OI 中的数学知识很多,也有些杂乱。
### Part 6.1 位运算
> 将十进制整数转换为二进制后,有很多按位运算的运算符。
>
> 如果能善于利用位运算的一些性质,往往能达到事半功倍的效果。
- [P5657 格雷码](https://www.luogu.com.cn/problem/P5657)
- [P5514 [MtOI2019]永夜的报应](https://www.luogu.com.cn/problem/P5514)
- [P5538 【XR-3】Namid[A]me](https://www.luogu.com.cn/problem/P5538)
- [P5539 【XR-3】Unknown Mother-Goose](https://www.luogu.com.cn/problem/P5539)
- [P5523 [yLOI2019]珍珠](https://www.luogu.com.cn/problem/P5523)
### Part 6.2 整除相关
> 与整除相关的概念有很多,比较常用的有素数,最大公约数和欧拉函数。
#### Part 6.2.1 素数
> 素数,指的是除 1 和它本身之外没有其他约数的数。
- [P4718 【模板】Pollard-Rho算法](https://www.luogu.com.cn/problem/P4718)
- [P1075 质因数分解](https://www.luogu.com.cn/problem/P1075)
- [P2441 角色属性树](https://www.luogu.com.cn/problem/P2441)
- [P5535 【XR-3】小道消息](https://www.luogu.com.cn/problem/P5535)
#### Part 6.2.2 最大公约数
> 如果两个数有一个共同的约数,那么这个约数就被称为公约数。最大公约数就是指这两个数的所有公约数中,最大的一个。
>
> 求解两个数的最大公约数,可以采用欧几里得算法解决。
- [P5435 【模板】快速 GCD](https://www.luogu.com.cn/problem/P5435)
- [P5436 【XR-2】缘分](https://www.luogu.com.cn/problem/P5436)
- [P1029 最大公约数和最小公倍数问题](https://www.luogu.com.cn/problem/P1029)
- [P1414 又是毕业季II](https://www.luogu.com.cn/problem/P1414)
- [P2152 [SDOI2009]SuperGCD](https://www.luogu.com.cn/problem/P2152)
- [P1072 Hankson 的趣味题](https://www.luogu.com.cn/problem/P1072)
#### Part 6.2.3 欧拉函数
> 欧拉函数 $ \varphi (x) $ 表示了小于 $ x $ 的数字中,与 $ x $ 互质的数字个数。
- [P2158 [SDOI2008]仪仗队](https://www.luogu.com.cn/problem/P2158)
- [P2568 GCD](https://www.luogu.com.cn/problem/P2568)
- [P2398 GCD SUM](https://www.luogu.com.cn/problem/P2398)
- [P4139 上帝与集合的正确用法](https://www.luogu.com.cn/problem/P4139)
### Part 6.3 同余方程
> 求解同余方程往往可以引出不少话题。
#### Part 6.3.1 线性同余方程&乘法逆元
> 线性同余方程是同余方程中最基础的内容。
- [P4549 【模板】裴蜀定理](https://www.luogu.com.cn/problem/P4549)
- [P2613 【模板】有理数取余](https://www.luogu.com.cn/problem/P2613)
- [P3811 【模板】乘法逆元](https://www.luogu.com.cn/problem/P3811)
- [P5431 【模板】乘法逆元2](https://www.luogu.com.cn/problem/P5431)
- [P1082 同余方程](https://www.luogu.com.cn/problem/P1082)
- [P3951 小凯的疑惑](https://www.luogu.com.cn/problem/P3951)
- [P1516 青蛙的约会](https://www.luogu.com.cn/problem/P1516)
#### Part 6.3.2 中国剩余定理
> 中国剩余定理可以快速解一元线性同余方程组。
- [P4777 【模板】扩展中国剩余定理(EXCRT)](https://www.luogu.com.cn/problem/P4777)
- [P3868 [TJOI2009]猜数字](https://www.luogu.com.cn/problem/P3868)
- [P2480 [SDOI2010]古代猪文](https://www.luogu.com.cn/problem/P2480)
- [P4774 [NOI2018]屠龙勇士](https://www.luogu.com.cn/problem/P4774)
- [P5345 【XR-1】快乐肥宅](https://www.luogu.com.cn/problem/P5345)
#### Part 6.3.3 高次同余方程
> BSGS 算法可以高效计算离散对数。
>
> 而高次剩余的求解更加复杂,其中二次剩余作为高次剩余中比较特殊的情况,可以使用 Cipolla 法求解。
- [P4195 【模板】exBSGS](https://www.luogu.com.cn/problem/P4195)
- [P5491 【模板】二次剩余](https://www.luogu.com.cn/problem/P5491)
- [P3306 [SDOI2013]随机数生成器](https://www.luogu.com.cn/problem/P3306)
- [P2485 [SDOI2011]计算器](https://www.luogu.com.cn/problem/P2485)
### Part 6.4 博弈论
> 博弈论考虑游戏中的个体的预测行为和实际行为,并研究它们的优化策略。
- [P2197 【模板】nim游戏](https://www.luogu.com.cn/problem/P2197)
- [P1288 取数游戏II](https://www.luogu.com.cn/problem/P1288)
- [P1290 欧几里德的游戏](https://www.luogu.com.cn/problem/P1290)
- [P1247 取火柴游戏](https://www.luogu.com.cn/problem/P1247)
- [P2252 取石子游戏](https://www.luogu.com.cn/problem/P2252)
### Part 6.5 概率与期望
> 概率和期望是紧密相连的,OI 中往往会出现和概率期望相关的动态规划问题。
- [P5104 红包发红包](https://www.luogu.com.cn/problem/P5104)
- [P1850 换教室](https://www.luogu.com.cn/problem/P1850)
- [P3830 [SHOI2012]随机树](https://www.luogu.com.cn/problem/P3830)
- [P4564 [CTSC2018]假面](https://www.luogu.com.cn/problem/P4564)
- [P2473 [SCOI2008]奖励关](https://www.luogu.com.cn/problem/P2473)
- [P2221 [HAOI2012]高速公路](https://www.luogu.com.cn/problem/P2221)
- [P3239 [HNOI2015]亚瑟王](https://www.luogu.com.cn/problem/P3239)
- [P3750 [六省联考2017]分手是祝愿](https://www.luogu.com.cn/problem/P3750)
- [P4284 [SHOI2014]概率充电器](https://www.luogu.com.cn/problem/P4284)
- [P5249 [LnOI2019]加特林轮盘赌](https://www.luogu.com.cn/problem/P5249)
- [P2081 [NOI2012]迷失游乐园](https://www.luogu.com.cn/problem/P2081)
- [P3343 [ZJOI2015]地震后的幻想乡](https://www.luogu.com.cn/problem/P3343)
- [P3600 随机数生成器](https://www.luogu.com.cn/problem/P3600)
- [P5326 [ZJOI2019]开关](https://www.luogu.com.cn/problem/P5326)
### Part 6.6 组合数学
> 组合数学常常与计数问题,概率期望紧密相连。
#### Part 6.6.1 排列组合
> 排列组合是组合数学的基础。
- [P3807 【模板】卢卡斯定理](https://www.luogu.com.cn/problem/P3807)
- [P2822 组合数问题](https://www.luogu.com.cn/problem/P2822)
- [P5520 [yLOI2019]青原樱](https://www.luogu.com.cn/problem/P5520)
- [P3197 [HNOI2008]越狱](https://www.luogu.com.cn/problem/P3197)
- [P2290 [HNOI2004]树的计数](https://www.luogu.com.cn/problem/P2290)
- [P4981 父子](https://www.luogu.com.cn/problem/P4981)
- [P4769 [NOI2018]冒泡排序](https://www.luogu.com.cn/problem/P4769)
- [P4931 情侣?给我烧了!(加强版)](https://www.luogu.com.cn/problem/P4931)
- [P5596 【XR-4】题](https://www.luogu.com.cn/problem/P5596)
- [P5598 【XR-4】混乱度](https://www.luogu.com.cn/problem/P5598)
#### Part 6.6.2 卡特兰数&斯特林数
> 卡特兰数和斯特林数是两类常见的组合递推数列。
- [P5395 【模板】第二类斯特林数·行](https://www.luogu.com.cn/problem/P5395)
- [P5396 【模板】第二类斯特林数·列](https://www.luogu.com.cn/problem/P5396)
- [P5408 【模板】第一类斯特林数·行](https://www.luogu.com.cn/problem/P5408)
- [P5409 【模板】第一类斯特林数·列](https://www.luogu.com.cn/problem/P5409)
- [P1655 小朋友的球](https://www.luogu.com.cn/problem/P1655)
- [P2532 [AHOI2012]树屋阶梯](https://www.luogu.com.cn/problem/P2532)
- [P3200 [HNOI2009]有趣的数列](https://www.luogu.com.cn/problem/P3200)
- [P3978 [TJOI2015]概率论](https://www.luogu.com.cn/problem/P3978)
- [P4091 [HEOI2016/TJOI2016]求和](https://www.luogu.com.cn/problem/P4091)
- [P4827 [国家集训队]Crash 的文明世界](https://www.luogu.com.cn/problem/P4827)
#### Part 6.6.3 容斥原理
> 容斥原理常常用于解决集合的计数问题。
- [P5664 Emiya 家今天的饭](https://www.luogu.com.cn/problem/P5664)
- [P1450 [HAOI2008]硬币购物](https://www.luogu.com.cn/problem/P1450)
- [P3214 [HNOI2011]卡农](https://www.luogu.com.cn/problem/P3214)
- [P3270 [JLOI2016]成绩比较](https://www.luogu.com.cn/problem/P3270)
- [P4336 [SHOI2016]黑暗前的幻想乡](https://www.luogu.com.cn/problem/P4336)
- [P4448 [AHOI2018初中组]球球的排列](https://www.luogu.com.cn/problem/P4448)
- [P4491 [HAOI2018]染色](https://www.luogu.com.cn/problem/P4491)
- [P5339 [TJOI2019]唱、跳、rap和篮球](https://www.luogu.com.cn/problem/P5339)
- [P5400 [CTS2019]随机立方体](https://www.luogu.com.cn/problem/P5400)
### Part 6.7 线性代数
> 线性代数主要用于解决线性关系问题。
#### Part 6.7.1 矩阵
> 利用矩阵优化数列递推,可以实现复杂度从线性到对数级的转变。
- [P3390 【模板】矩阵快速幂](https://www.luogu.com.cn/problem/P3390)
- [P1939 【模板】矩阵加速(数列)](https://www.luogu.com.cn/problem/P1939)
- [P4783 【模板】矩阵求逆](https://www.luogu.com.cn/problem/P4783)
- [P1962 斐波那契数列](https://www.luogu.com.cn/problem/P1962)
- [P1349 广义斐波那契数列](https://www.luogu.com.cn/problem/P1349)
- [P4000 斐波那契数列](https://www.luogu.com.cn/problem/P4000)
- [P3758 [TJOI2017]可乐](https://www.luogu.com.cn/problem/P3758)
- [P4967 黑暗打击](https://www.luogu.com.cn/problem/P4967)
- [P5343 【XR-1】分块](https://www.luogu.com.cn/problem/P5343)
- [P5337 [TJOI2019]甲苯先生的字符串](https://www.luogu.com.cn/problem/P5337)
- [P5303 [GXOI/GZOI2019]逼死强迫症](https://www.luogu.com.cn/problem/P5303)
#### Part 6.7.2 高斯消元
> 高斯消元可以用来求解方程组。
- [P3389 【模板】高斯消元法](https://www.luogu.com.cn/problem/P3389)
- [P4387 付公主的函数](https://www.luogu.com.cn/problem/P4387)
- [P2447 [SDOI2010]外星千足虫](https://www.luogu.com.cn/problem/P2447)
- [P4035 [JSOI2008]球形空间产生器](https://www.luogu.com.cn/problem/P4035)
- [P5516 [MtOI2019]小铃的烦恼](https://www.luogu.com.cn/problem/P5516)
- [P4111 [HEOI2015]小Z的房间](https://www.luogu.com.cn/problem/P4111)
- [P4457 [BJOI2018]治疗之雨](https://www.luogu.com.cn/problem/P4457)
#### Part 6.7.3 线性基
> 线性基可以求解最大异或和的一类问题。
- [P3812 【模板】线性基](https://www.luogu.com.cn/problem/P3812)
- [P3857 [TJOI2008]彩灯](https://www.luogu.com.cn/problem/P3857)
- [P4570 [BJWC2011]元素](https://www.luogu.com.cn/problem/P4570)
- [P4301 [CQOI2013]新Nim游戏](https://www.luogu.com.cn/problem/P4301)
- [P3292 [SCOI2016]幸运数字](https://www.luogu.com.cn/problem/P3292)
- [P4151 [WC2011]最大XOR和路径](https://www.luogu.com.cn/problem/P4151)
### Part 6.8 多项式
> 对多项式的运算进行优化,从而能够解决规模更大的问题。
- [P1919 【模板】A\*B Problem升级版(FFT快速傅里叶)](https://www.luogu.com.cn/problem/P1919)
- [P3803 【模板】多项式乘法(FFT)](https://www.luogu.com.cn/problem/P3803)
- [P4238 【模板】多项式求逆](https://www.luogu.com.cn/problem/P4238)
- [P4245 【模板】任意模数NTT](https://www.luogu.com.cn/problem/P4245)
- [P4512 【模板】多项式除法](https://www.luogu.com.cn/problem/P4512)
- [P4717 【模板】快速沃尔什变换](https://www.luogu.com.cn/problem/P4717)
- [P4721 【模板】分治 FFT](https://www.luogu.com.cn/problem/P4721)
- [P4725 【模板】多项式对数函数](https://www.luogu.com.cn/problem/P4725)
- [P4726 【模板】多项式指数函数](https://www.luogu.com.cn/problem/P4726)
- [P4781 【模板】拉格朗日插值](https://www.luogu.com.cn/problem/P4781)
- [P5050 【模板】多项式多点求值](https://www.luogu.com.cn/problem/P5050)
- [P5158 【模板】多项式快速插值](https://www.luogu.com.cn/problem/P5158)
- [P5205 【模板】多项式开根](https://www.luogu.com.cn/problem/P5205)
- [P5245 【模板】多项式快速幂](https://www.luogu.com.cn/problem/P5245)
- [P5273 【模板】多项式幂函数 (加强版)](https://www.luogu.com.cn/problem/P5273)
- [P5282 【模板】快速阶乘算法](https://www.luogu.com.cn/problem/P5282)
- [P5373 【模板】多项式复合函数](https://www.luogu.com.cn/problem/P5373)
- [P5383 【模板】普通多项式转下降幂多项式](https://www.luogu.com.cn/problem/P5383)
- [P5393 【模板】下降幂多项式转普通多项式](https://www.luogu.com.cn/problem/P5393)
- [P5394 【模板】下降幂多项式乘法](https://www.luogu.com.cn/problem/P5394)
- [P3338 [ZJOI2014]力](https://www.luogu.com.cn/problem/P3338)
- [P3723 [AH2017/HNOI2017]礼物](https://www.luogu.com.cn/problem/P3723)
- [P5437 【XR-2】约定](https://www.luogu.com.cn/problem/P5437)
- [P5293 [HNOI2019]白兔之舞](https://www.luogu.com.cn/problem/P5293)
- [P5432 A/B Problem (加强版)](https://www.luogu.com.cn/problem/P5432)
- [P5472 [NOI2019]斗主地](https://www.luogu.com.cn/problem/P5472)
- [P5577 [CmdOI2019]算力训练](https://www.luogu.com.cn/problem/P5577)
### Part 6.9 莫比乌斯反演
> 运用莫比乌斯反演,我们可以将一些函数转化,从而降低计算难度。
- [P3172 [CQOI2015]选数](https://www.luogu.com.cn/problem/P3172)
- [P2522 [HAOI2011]Problem b](https://www.luogu.com.cn/problem/P2522)
- [P3455 [POI2007]ZAP-Queries](https://www.luogu.com.cn/problem/P3455)
- [P3327 [SDOI2015]约数个数和](https://www.luogu.com.cn/problem/P3327)
- [P1829 [国家集训队]Crash的数字表格 / JZPTAB](https://www.luogu.com.cn/problem/P1829)
- [P4619 [SDOI2018]旧试题](https://www.luogu.com.cn/problem/P4619)
- [P3704 [SDOI2017]数字表格](https://www.luogu.com.cn/problem/P3704)
- [P5518 [MtOI2019]幽灵乐团](https://www.luogu.com.cn/problem/P5518)
### Part 6.10 筛法
> 利用数列的性质,有多种筛法可以求出我们想要的信息。
- [P3383 【模板】线性筛素数](https://www.luogu.com.cn/problem/P3383)
- [P4213 【模板】杜教筛(Sum)](https://www.luogu.com.cn/problem/P4213)
- [P5325 【模板】Min_25筛](https://www.luogu.com.cn/problem/P5325)
- [P1865 A % B Problem](https://www.luogu.com.cn/problem/P1865)
- [P1621 集合](https://www.luogu.com.cn/problem/P1621)
- [P3768 简单的数学题](https://www.luogu.com.cn/problem/P3768)
- [P5438 【XR-2】记忆](https://www.luogu.com.cn/problem/P5438)
### Part 6.11 线性规划
> 线性规划是研究线性约束条件下线性目标函数极值问题的方法。
- [P3980 [NOI2008]志愿者招募](https://www.luogu.com.cn/problem/P3980)
- [P4232 无意识之外的捉迷藏](https://www.luogu.com.cn/problem/P4232)
### Part 6.12 数值方法
> 在算法领域,有很多求近似值的数值方法。
#### Part 6.12.1 三分法
> 三分法可以求出一个单峰 / 单谷函数的极值。
- [P3382 【模板】三分法](https://www.luogu.com.cn/problem/P3382)
- [P1883 函数](https://www.luogu.com.cn/problem/P1883)
#### Part 6.12.2 自适应辛普森法
> 自适应辛普森法可以高效求出给定函数的数值积分。
- [P4525 【模板】自适应辛普森法1](https://www.luogu.com.cn/problem/P4525)
- [P4526 【模板】自适应辛普森法2](https://www.luogu.com.cn/problem/P4526)
- [P3779 [SDOI2017]龙与地下城](https://www.luogu.com.cn/problem/P3779)
### Part 6.13 置换群
> 置换群通常用来解决一些涉及“本质不同”的计数问题。
- [P4980 【模板】Polya定理](https://www.luogu.com.cn/problem/P4980)
- [P1446 [HNOI2008]Cards](https://www.luogu.com.cn/problem/P1446)
- [P2561 [AHOI2002]黑白瓷砖](https://www.luogu.com.cn/problem/P2561)
- [P4128 [SHOI2006]有色图](https://www.luogu.com.cn/problem/P4128)
- [P4727 [HNOI2009]图的同构记数](https://www.luogu.com.cn/problem/P4727)
## Part 7 数据结构
> 灵活地运用数据结构可以高效地查询并处理需要的信息。
### Part 7.1 链表
> 在一个数列中高效插入一个元素,链表毫无疑问是最好的选择。
- [P1996 约瑟夫问题](https://www.luogu.com.cn/problem/P1996)
- [P1160 队列安排](https://www.luogu.com.cn/problem/P1160)
### Part 7.2 栈
> 栈,是一种后进先出(FILO)的数据结构。
- [P1449 后缀表达式](https://www.luogu.com.cn/problem/P1449)
- [P1739 表达式括号匹配](https://www.luogu.com.cn/problem/P1739)
- [P1981 表达式求值](https://www.luogu.com.cn/problem/P1981)
- [P1175 表达式的转换](https://www.luogu.com.cn/problem/P1175)
### Part 7.3 队列
> 队列,是一种先进先出(FIFO)的数据结构。
- [P1540 机器翻译](https://www.luogu.com.cn/problem/P1540)
### Part 7.4 并查集
> 并查集常用于处理一些不相交集合的合并和查询问题。
- [P1111 修复公路](https://www.luogu.com.cn/problem/P1111)
- [P3958 奶酪](https://www.luogu.com.cn/problem/P3958)
- [P1525 关押罪犯](https://www.luogu.com.cn/problem/P1525)
- [P4185 [USACO18JAN]MooTube G](https://www.luogu.com.cn/problem/P4185)
- [P2024 [NOI2001]食物链](https://www.luogu.com.cn/problem/P2024)
- [P1197 [JSOI2008]星球大战](https://www.luogu.com.cn/problem/P1197)
- [P1196 [NOI2002]银河英雄传说](https://www.luogu.com.cn/problem/P1196)
- [P1955 [NOI2015]程序自动分析](https://www.luogu.com.cn/problem/P1955)
### Part 7.5 二叉堆
> 二叉堆是一棵完全二叉树,堆中某个节点的值总是不大于或不小于其父节点的值。
- [P3378 【模板】堆](https://www.luogu.com.cn/problem/P3378)
- [P1090 合并果子](https://www.luogu.com.cn/problem/P1090)
- [P1168 中位数](https://www.luogu.com.cn/problem/P1168)
- [P2085 最小函数值](https://www.luogu.com.cn/problem/P2085)
- [P2827 蚯蚓](https://www.luogu.com.cn/problem/P2827)
- [P3045 [USACO12FEB]Cow Coupons](https://www.luogu.com.cn/problem/P3045)
### Part 7.6 ST表
> ST表可以离线查询区间最值。
- [P3865 【模板】ST表](https://www.luogu.com.cn/problem/P3865)
- [P2251 质量检测](https://www.luogu.com.cn/problem/P2251)
- [P1816 忠诚](https://www.luogu.com.cn/problem/P1816)
- [P1198 [JSOI2008]最大数](https://www.luogu.com.cn/problem/P1198)
- [P2880 [USACO07JAN]Balanced Lineup](https://www.luogu.com.cn/problem/P2880)
- [P5012 水の数列](https://www.luogu.com.cn/problem/P5012)
- [P5344 【XR-1】逛森林](https://www.luogu.com.cn/problem/P5344)
- [P2048 [NOI2010]超级钢琴](https://www.luogu.com.cn/problem/P2048)
### Part 7.7 树状数组
> 树状数组是一种简洁高效的树形数据结构。
- [P3374 【模板】树状数组 1](https://www.luogu.com.cn/problem/P3374)
- [P3368 【模板】树状数组 2](https://www.luogu.com.cn/problem/P3368)
- [P1908 逆序对](https://www.luogu.com.cn/problem/P1908)
- [P1966 火柴排队](https://www.luogu.com.cn/problem/P1966)
- [P3605 [USACO17JAN]Promotion Counting](https://www.luogu.com.cn/problem/P3605)
- [P1972 [SDOI2009]HH的项链](https://www.luogu.com.cn/problem/P1972)
- [P3586 [POI2015]LOG](https://www.luogu.com.cn/problem/P3586)
- [P4054 [JSOI2009]计数问题](https://www.luogu.com.cn/problem/P4054)
- [P4113 [HEOI2012]采花](https://www.luogu.com.cn/problem/P4113)
- [P3960 列队](https://www.luogu.com.cn/problem/P3960)
### Part 7.8 线段树
> 线段树的通用性比树状数组更强,可以处理更多涉及区间操作的题目。
- [P3372 【模板】线段树 1](https://www.luogu.com.cn/problem/P3372)
- [P3373 【模板】线段树 2](https://www.luogu.com.cn/problem/P3373)
- [P5490 【模板】扫描线](https://www.luogu.com.cn/problem/P5490)
- [P4588 [TJOI2018]数学计算](https://www.luogu.com.cn/problem/P4588)
- [P1502 窗口的星星](https://www.luogu.com.cn/problem/P1502)
- [P2471 [SCOI2007]降雨量](https://www.luogu.com.cn/problem/P2471)
- [P2824 [HEOI2016/TJOI2016]排序](https://www.luogu.com.cn/problem/P2824)
- [P3722 [AH2017/HNOI2017]影魔](https://www.luogu.com.cn/problem/P3722)
- [P4097 [HEOI2013]Segment](https://www.luogu.com.cn/problem/P4097)
- [P4198 楼房重建](https://www.luogu.com.cn/problem/P4198)
- [P4513 小白逛公园](https://www.luogu.com.cn/problem/P4513)
- [P4556 [Vani有约会]雨天的尾巴](https://www.luogu.com.cn/problem/P4556)
- [P5324 [BJOI2019]删数](https://www.luogu.com.cn/problem/P5324)
- [P5327 [ZJOI2019]语言](https://www.luogu.com.cn/problem/P5327)
### Part 7.9 分块
> 分块是一种非常通用的暴力方法,虽然效率不如线段树和树状数组,但可以解决很多线段树和树状数组处理不了的问题。
- [P3870 [TJOI2009]开关](https://www.luogu.com.cn/problem/P3870)
- [P3396 哈希冲突](https://www.luogu.com.cn/problem/P3396)
- [P3863 序列](https://www.luogu.com.cn/problem/P3863)
- [P1975 [国家集训队]排队](https://www.luogu.com.cn/problem/P1975)
- [P3710 方方方的数据结构](https://www.luogu.com.cn/problem/P3710)
- [P3992 [BJOI2017]开车](https://www.luogu.com.cn/problem/P3992)
- [P4168 [Violet]蒲公英](https://www.luogu.com.cn/problem/P4168)
- [P4119 [Ynoi2018]未来日记](https://www.luogu.com.cn/problem/P4119)
### Part 7.10 可并堆
> 可并堆分为左偏树和配对堆两种,它们都具有堆的性质,且可以高效合并。
- [P3377 【模板】左偏树(可并堆)](https://www.luogu.com.cn/problem/P3377)
- [P2713 罗马游戏](https://www.luogu.com.cn/problem/P2713)
- [P1456 Monkey King](https://www.luogu.com.cn/problem/P1456)
- [P1552 [APIO2012]派遣](https://www.luogu.com.cn/problem/P1552)
- [P3261 [JLOI2015]城池攻占](https://www.luogu.com.cn/problem/P3261)
- [P3273 [SCOI2011]棘手的操作](https://www.luogu.com.cn/problem/P3273)
- [P4331 [BOI2004]Sequence](https://www.luogu.com.cn/problem/P4331)
### Part 7.11 主席树
> 主席树,即可持久化权值线段树。
- [P2468 [SDOI2010]粟粟的书架](https://www.luogu.com.cn/problem/P2468)
- [P3302 [SDOI2013]森林](https://www.luogu.com.cn/problem/P3302)
- [P3168 [CQOI2015]任务查询系统](https://www.luogu.com.cn/problem/P3168)
- [P4559 [JSOI2018]列队](https://www.luogu.com.cn/problem/P4559)
- [P2633 Count on a tree](https://www.luogu.com.cn/problem/P2633)
- [P3293 [SCOI2016]美味](https://www.luogu.com.cn/problem/P3293)
- [P4618 [SDOI2018]原题识别](https://www.luogu.com.cn/problem/P4618)
### Part 7.12 平衡树
> 二叉搜索树可以用来维护有序序列。
>
> 为了保证查询效率,有多种使二叉搜索树保持平衡的实现方法。
- [P3369 【模板】普通平衡树](https://www.luogu.com.cn/problem/P3369)
- [P3391 【模板】文艺平衡树(Splay)](https://www.luogu.com.cn/problem/P3391)
- [P3850 [TJOI2007]书架](https://www.luogu.com.cn/problem/P3850)
- [P4008 [NOI2003]文本编辑器](https://www.luogu.com.cn/problem/P4008)
- [P5338 [TJOI2019]甲苯先生的滚榜](https://www.luogu.com.cn/problem/P5338)
- [P2042 [NOI2005]维护数列](https://www.luogu.com.cn/problem/P2042)
- [P1110 [ZJOI2007]报表统计](https://www.luogu.com.cn/problem/P1110)
- [P3644 [APIO2015]八邻旁之桥](https://www.luogu.com.cn/problem/P3644)
- [P1486 [NOI2004]郁闷的出纳员](https://www.luogu.com.cn/problem/P1486)
- [P2710 数列](https://www.luogu.com.cn/problem/P2710)
- [P3224 [HNOI2012]永无乡](https://www.luogu.com.cn/problem/P3224)
- [P3285 [SCOI2014]方伯伯的OJ](https://www.luogu.com.cn/problem/P3285)
- [P5321 [BJOI2019]送别](https://www.luogu.com.cn/problem/P5321)
### Part 7.13 树链剖分
> 树链剖分可以将任意一条树上路径划分成若干条连续的链,并用线段树等数据结构高效维护链上信息。
- [P3384 【模板】树链剖分](https://www.luogu.com.cn/problem/P3384)
- [P3313 [SDOI2014]旅行](https://www.luogu.com.cn/problem/P3313)
- [P2590 [ZJOI2008]树的统计](https://www.luogu.com.cn/problem/P2590)
- [P1505 [国家集训队]旅游](https://www.luogu.com.cn/problem/P1505)
- [P2486 [SDOI2011]染色](https://www.luogu.com.cn/problem/P2486)
- [P3258 [JLOI2014]松鼠的新家](https://www.luogu.com.cn/problem/P3258)
- [P4069 [SDOI2016]游戏](https://www.luogu.com.cn/problem/P4069)
- [P4211 [LNOI2014]LCA](https://www.luogu.com.cn/problem/P4211)
- [P4592 [TJOI2018]异或](https://www.luogu.com.cn/problem/P4592)
- [P5305 [GXOI/GZOI2019]旧词](https://www.luogu.com.cn/problem/P5305)
- [P5354 [Ynoi2017]由乃的OJ](https://www.luogu.com.cn/problem/P5354)
- [P5499 [LnOI2019]Abbi并不想研学](https://www.luogu.com.cn/problem/P5499)
### Part 7.14 树套树
> 树套树可以用来维护多维度信息。
- [P3380 【模板】二逼平衡树(树套树)](https://www.luogu.com.cn/problem/P3380)
- [P1975 [国家集训队]排队](https://www.luogu.com.cn/problem/P1975)
- [P3332 [ZJOI2013]K大数查询](https://www.luogu.com.cn/problem/P3332)
- [P4278 带插入区间K小值](https://www.luogu.com.cn/problem/P4278)
- [P1903 [国家集训队]数颜色 / 维护队列](https://www.luogu.com.cn/problem/P1903)
- [P3759 [TJOI2017]不勤劳的图书管理员](https://www.luogu.com.cn/problem/P3759)
- [P3242 [HNOI2015]接水果](https://www.luogu.com.cn/problem/P3242)
- [P3248 [HNOI2016]树](https://www.luogu.com.cn/problem/P3248)
- [P5445 [APIO2019]路灯](https://www.luogu.com.cn/problem/P5445)
### Part 7.15 动态树
> Link-Cut Tree 可以用来解决动态树一类问题。
- [P3690 【模板】Link Cut Tree (动态树)](https://www.luogu.com.cn/problem/P3690)
- [P3203 [HNOI2010]弹飞绵羊](https://www.luogu.com.cn/problem/P3203)
- [P4338 [ZJOI2018]历史](https://www.luogu.com.cn/problem/P4338)
- [P4312 [COCI2009]OTOCI](https://www.luogu.com.cn/problem/P4312)
- [P1501 [国家集训队]Tree II](https://www.luogu.com.cn/problem/P1501)
- [P2387 [NOI2014]魔法森林](https://www.luogu.com.cn/problem/P2387)
- [P3348 [ZJOI2016]大森林](https://www.luogu.com.cn/problem/P3348)
- [P3703 [SDOI2017]树点涂色](https://www.luogu.com.cn/problem/P3703)
- [P4172 [WC2006]水管局长](https://www.luogu.com.cn/problem/P4172)
- [P4219 [BJOI2014]大融合](https://www.luogu.com.cn/problem/P4219)
- [P5489 EntropyIncreaser 与 动态图](https://www.luogu.com.cn/problemnew/solution/P5489)
### Part 7.16 可持久化数据结构
> 可持久化数据结构实现了在更新信息的时候保留历史版本。
- [P3919 【模板】可持久化数组(可持久化线段树/平衡树)](https://www.luogu.com.cn/problem/P3919)
- [P3834 【模板】可持久化线段树 1(主席树)](https://www.luogu.com.cn/problem/P3834)
- [P3402 【模板】可持久化并查集](https://www.luogu.com.cn/problem/P3402)
- [P3835 【模板】可持久化平衡树](https://www.luogu.com.cn/problem/P3835)
- [P5055 【模板】可持久化文艺平衡树](https://www.luogu.com.cn/problem/P5055)
- [P5283 [十二省联考2019]异或粽子](https://www.luogu.com.cn/problem/P5283)
### Part 7.17 K-D Tree
> K-D Tree 是一种高效处理 $ k $ 维信息的数据结构。
- [P4357 [CQOI2016]K远点对](https://www.luogu.com.cn/problem/P4357)
- [P4148 简单题](https://www.luogu.com.cn/problem/P4148)
- [P2479 [SDOI2010]捉迷藏](https://www.luogu.com.cn/problem/P2479)
- [P3769 [CH弱省胡策R2]TATT](https://www.luogu.com.cn/problem/P3769)
- [P4169 [Violet]天使玩偶/SJY摆棋子](https://www.luogu.com.cn/problem/P4169)
- [P4390 [BOI2007]Mokia](https://www.luogu.com.cn/problem/P4390)
- [P4475 巧克力王国](https://www.luogu.com.cn/problem/P4475)
- [P2093 [国家集训队]JZPFAR](https://www.luogu.com.cn/problem/P2093)
- [P5471 [NOI2019]弹跳](https://www.luogu.com.cn/problem/P5471)
### Part 7.18 珂朵莉树
> 珂朵莉树,是一种基于 `std::set` 的暴力数据结构,在数据随机的情况下表现优秀。
- [P5251 [LnOI2019]第二代图灵机](https://www.luogu.com.cn/problem/P5251)
- [P5350 序列](https://www.luogu.com.cn/problem/P5350)
## Part 8 图论
> 图论是数学的一个分支,它以图为研究的对象。
### Part 8.1 图的存储与遍历
> 这里的图论内容都比较简单,涉及图的存储以及遍历图的方式。
- [P2661 信息传递](https://www.luogu.com.cn/problem/P2661)
- [P2921 [USACO08DEC]Trick or Treat on the Farm](https://www.luogu.com.cn/problem/P2921)
### Part 8.2 最短路问题
> 很多题目都可以转化为最短路的模型。因此,掌握最短路算法非常重要。
- [P3371 【模板】单源最短路径(弱化版)](https://www.luogu.com.cn/problem/P3371)
- [P4779 【模板】单源最短路径(标准版)](https://www.luogu.com.cn/problem/P4779)
- [P5905 【模板】Johnson 全源最短路](https://www.luogu.com.cn/problem/P5905)
- [P1144 最短路计数](https://www.luogu.com.cn/problem/P1144)
- [P1462 通往奥格瑞玛的道路](https://www.luogu.com.cn/problem/P1462)
- [P1522 Cow Tours](https://www.luogu.com.cn/problem/P1522)
- [P1266 速度限制](https://www.luogu.com.cn/problem/P1266)
- [P4001 [ICPC-Beijing 2006]狼抓兔子](https://www.luogu.com.cn/problem/P4001)
- [P4568 [JLOI2011]飞行路线](https://www.luogu.com.cn/problem/P4568)
- [P3238 [HNOI2014]道路堵塞](https://www.luogu.com.cn/problem/P3238)
- [P5304 [GXOI/GZOI2019]旅行者](https://www.luogu.com.cn/problem/P5304)
### Part 8.3 树上问题
> 作为一种特殊的图,树上的问题具有很多鲜明的特点。
#### Part 8.3.1 二叉树
> 二叉树是一种特殊的树,它有很多特殊的性质。
- [P1087 FBI树](https://www.luogu.com.cn/problem/P1087)
- [P1030 求先序排列](https://www.luogu.com.cn/problem/P1030)
- [P1305 新二叉树](https://www.luogu.com.cn/problem/P1305)
- [P1229 遍历问题](https://www.luogu.com.cn/problem/P1229)
- [P5018 对称二叉树](https://www.luogu.com.cn/problem/P5018)
- [P5597 【XR-4】复读](https://www.luogu.com.cn/problem/P5597)
#### Part 8.3.2 树的直径
> 树的直径被定义为树上最远的两点间的距离。
>
> 计算树的直径,可以通过两遍 DFS 解决。
- [P2195 HXY造公园](https://www.luogu.com.cn/problem/P2195)
- [P3629 [APIO2010]巡逻](https://www.luogu.com.cn/problem/P3629)
- [P5536 【XR-3】核心城市](https://www.luogu.com.cn/problem/P5536)
- [P1099 树网的核](https://www.luogu.com.cn/problem/P1099)
- [P4408 [NOI2003]逃学的小孩](https://www.luogu.com.cn/problem/P4408)
#### Part 8.3.3 最近公共祖先
> 两个点的最近公共祖先,即两个点的所有公共祖先中,离根节点最远的一个节点。
>
> 求解最近公共祖先,常用的方法是树上倍增或者树链剖分。
- [P3379 【模板】最近公共祖先(LCA)](https://www.luogu.com.cn/problem/P3379)
- [P3938 斐波那契](https://www.luogu.com.cn/problem/P3938)
- [P4281 [AHOI2008]紧急集合 / 聚会](https://www.luogu.com.cn/problem/P4281)
### Part 8.4 生成树
> 用 $ n-1 $ 条边将图上的 $ n $ 个点连接起来,形成的树就被称为生成树。
- [P3366 【模板】最小生成树](https://www.luogu.com.cn/problem/P3366)
- [P4180 【模板】严格次小生成树[BJWC2010]](https://www.luogu.com.cn/problem/P4180)
- [P2872 [USACO07DEC]Building Roads](https://www.luogu.com.cn/problem/P2872)
- [P1991 无线通讯网](https://www.luogu.com.cn/problem/P1991)
- [P1967 货车运输](https://www.luogu.com.cn/problem/P1967)
- [P4047 [JSOI2010]部落划分](https://www.luogu.com.cn/problem/P4047)
### Part 8.5 拓扑排序
> 将一个有向无环图排序,使得所有排在前面的节点不能依赖于排在后面的节点,这就是拓扑排序。
- [P1113 杂务](https://www.luogu.com.cn/problem/P1113)
- [P1983 车站分级](https://www.luogu.com.cn/problem/P1983)
- [P1038 神经网络](https://www.luogu.com.cn/problem/P1038)
### Part 8.6 差分约束
> 差分约束要解决的问题是:求出一组 $ n $ 元不等式的一组解,使得所有约束关系都能得到满足。
- [P5960 【模板】差分约束算法](https://www.luogu.com.cn/problem/P5960)
- [P3275 [SCOI2011]糖果](https://www.luogu.com.cn/problem/P3275)
- [P2294 [HNOI2005]狡猾的商人](https://www.luogu.com.cn/problem/P2294)
- [P4926 [1007]倍杀测量者](https://www.luogu.com.cn/problem/P4926)
- [P5590 赛车游戏](https://www.luogu.com.cn/problem/P5590)
### Part 8.7 图的连通性相关
> 利用 Tarjan 算法,我们可以解决很多与图的连通性相关的问题。
- [P3387 【模板】缩点](https://www.luogu.com.cn/problem/P3387)
- [P3388 【模板】割点(割顶)](https://www.luogu.com.cn/problem/P3388)
- [P2341 [HAOI2006]受欢迎的牛](https://www.luogu.com.cn/problem/P2341)
- [P2863 [USACO06JAN]The Cow Prom](https://www.luogu.com.cn/problem/P2863)
- [P2746 [USACO5.3]Network of Schools](https://www.luogu.com.cn/problem/P2746)
- [P1407 [国家集训队]稳定婚姻](https://www.luogu.com.cn/problem/P1407)
- [P2272 [ZJOI2007]最大半连通子图](https://www.luogu.com.cn/problem/P2272)
- [P3225 [HNOI2012]矿场搭建](https://www.luogu.com.cn/problem/P3225)
- [P5058 [ZJOI2004]嗅探器](https://www.luogu.com.cn/problem/P5058)
- [P2515 [HAOI2010]软件安装](https://www.luogu.com.cn/problem/P2515)
### Part 8.8 二分图
> 二分图上的不少问题都可以转化成网络流解决,当然也有独特的其他方法。
- [P3386 【模板】二分图匹配](https://www.luogu.com.cn/problem/P3386)
- [P2756 飞行员配对方案问题](https://www.luogu.com.cn/problem/P2756)
- [P1129 [ZJOI2007]矩阵游戏](https://www.luogu.com.cn/problem/P1129)
- [P1559 运动员最佳匹配问题](https://www.luogu.com.cn/problem/P1559)
- [P2423 [HEOI2012]朋友圈](https://www.luogu.com.cn/problem/P2423)
- [P2764 最小路径覆盖问题](https://www.luogu.com.cn/problem/P2764)
- [P2825 [HEOI2016/TJOI2016]游戏](https://www.luogu.com.cn/problem/P2825)
- [P3033 [USACO11NOV]Cow Steeplechase](https://www.luogu.com.cn/problem/P3033)
- [P3731 [HAOI2017]新型城市化](https://www.luogu.com.cn/problem/P3731)
- [P4014 分配问题](https://www.luogu.com.cn/problem/P4014)
- [P4617 [COCI2017-2018#5] Planinarenje](https://www.luogu.com.cn/problem/P4617)
### Part 8.9 网络流
> 网络流是图论中一个重要的分支,很多题目都可以通过建立网络流的模型来解决。
#### Part 8.9.1 最大流
> 最大流,即求网络中最大的流量。
- [P3376 【模板】网络最大流](https://www.luogu.com.cn/problem/P3376)
- [P4722 【模板】最大流 加强版 / 预流推进](https://www.luogu.com.cn/problem/P4722)
- [P2065 [TJOI2011]卡片](https://www.luogu.com.cn/problem/P2065)
- [P2763 试题库问题](https://www.luogu.com.cn/problem/P2763)
- [P2472 [SCOI2007]蜥蜴](https://www.luogu.com.cn/problem/P2472)
- [P2754 [CTSC1999]家园](https://www.luogu.com.cn/problem/P2754)
- [P2765 魔术球问题](https://www.luogu.com.cn/problem/P2765)
- [P2766 最长不下降子序列问题](https://www.luogu.com.cn/problem/P2766)
- [P2805 [NOI2009]植物大战僵尸](https://www.luogu.com.cn/problem/P2805)
- [P3749 [六省联考2017]寿司餐厅](https://www.luogu.com.cn/problem/P3749)
#### Part 8.9.2 最小割
> 最小割,即求一个边权最小的边集,使得源点和汇点不再连通。
>
> 可以证明,**最大流=最小割**。
- [P1344 [USACO4.4]Pollutant Control](https://www.luogu.com.cn/problem/P1344)
- [P1345 [USACO5.4]Telecowmunication](https://www.luogu.com.cn/problem/P1345)
- [P2057 [SHOI2007]善意的投票](https://www.luogu.com.cn/problem/P2057)
- [P2598 [ZJOI2009]狼和羊的故事](https://www.luogu.com.cn/problem/P2598)
- [P2774 方格取数问题](https://www.luogu.com.cn/problem/P2774)
- [P4126 [AHOI2009]最小割](https://www.luogu.com.cn/problem/P4126)
- [P5039 [SHOI2010]最小生成树](https://www.luogu.com.cn/problem/P5039)
#### Part 8.9.3 费用流
> 在网络流中给边加上一个参数——费用,就出现了费用流。
- [P3381 【模板】最小费用最大流](https://www.luogu.com.cn/problem/P3381)
- [P4016 负载平衡问题](https://www.luogu.com.cn/problem/P4016)
- [P4452 [国家集训队]航班安排](https://www.luogu.com.cn/problem/P4452)
- [P2045 方格取数加强版](https://www.luogu.com.cn/problem/P2045)
- [P2050 [NOI2012]美食节](https://www.luogu.com.cn/problem/P2050)
- [P2053 [SCOI2007]修车](https://www.luogu.com.cn/problem/P2053)
- [P2604 [ZJOI2010]网络扩容](https://www.luogu.com.cn/problem/P2604)
- [P2770 航空路线问题](https://www.luogu.com.cn/problem/P2770)
- [P3159 [CQOI2012]交换棋子](https://www.luogu.com.cn/problem/P3159)
- [P3356 火星探险问题](https://www.luogu.com.cn/problem/P3356)
- [P3358 最长k可重区间集问题](https://www.luogu.com.cn/problem/P3358)
- [P4013 数字梯形问题](https://www.luogu.com.cn/problem/P4013)
- [P4015 运输问题](https://www.luogu.com.cn/problem/P4015)
- [P5331 [SNOI2019]通信](https://www.luogu.com.cn/problem/P5331)
#### Part 8.9.4 上下界网络流
> 在网络流问题中给每条边的流量增加一个下界,就有了上下界网络流。
- [P3980 [NOI2008]志愿者招募](https://www.luogu.com.cn/problem/P3980)
- [P4043 [AHOI2014/JSOI2014]支线剧情](https://www.luogu.com.cn/problem/P4043)
- [P4553 80人环游世界](https://www.luogu.com.cn/problem/P4553)
- [P4843 清理雪道](https://www.luogu.com.cn/problem/P4843)
### Part 8.10 2-SAT
> k-SAT 问题的目标是对一些布尔变量赋值,满足限定的条件。
>
> 在 k-SAT 问题中,2-SAT 问题属于较为容易解决的一类。
- [P4782 【模板】2-SAT 问题](https://www.luogu.com.cn/problem/P4782)
- [P4171 [JSOI2010]满汉全席](https://www.luogu.com.cn/problem/P4171)
- [P3825 [NOI2017]游戏](https://www.luogu.com.cn/problem/P3825)
- [P5332 [JSOI2019]精准预测](https://www.luogu.com.cn/problem/P5332)
### Part 8.11 点分治
> 点分治是一种可以高效统计树上路径信息的算法。
- [P3806 【模板】点分治1](https://www.luogu.com.cn/problem/P3806)
- [P2634 [国家集训队]聪聪可可](https://www.luogu.com.cn/problem/P2634)
- [P2664 树上游戏](https://www.luogu.com.cn/problem/P2664)
- [P3714 [BJOI2017]树的难题](https://www.luogu.com.cn/problem/P3714)
- [P4149 [IOI2011]Race](https://www.luogu.com.cn/problem/P4149)
- [P3241 [HNOI2015]开店](https://www.luogu.com.cn/problem/P3241)
- [P4075 [SDOI2016]模式字符串](https://www.luogu.com.cn/problem/P4075)
- [P4183 [USACO18JAN]Cow at Large P](https://www.luogu.com.cn/problem/P4183)
- [P4292 [WC2010]重建计划](https://www.luogu.com.cn/problem/P4292)
- [P5306 [COCI2019]Transport](https://www.luogu.com.cn/problem/P5306)
### Part 8.12 虚树
> 将一些无用的点从树上删去,从而达到降低树的规模的效果。
- [P2495 [SDOI2011]消耗战](https://www.luogu.com.cn/problem/P2495)
- [P3233 [HNOI2014]世界树](https://www.luogu.com.cn/problem/P3233)
- [P5360 [SDOI2019]世界地图](https://www.luogu.com.cn/problem/P5360)
- [P5439 【XR-2】永恒](https://www.luogu.com.cn/problem/P5439)
### Part 8.13 矩阵树定理
> 矩阵树定理可以解决图的生成树计数问题。
- [P4111 [HEOI2015]小Z的房间](https://www.luogu.com.cn/problem/P4111)
- [P2144 [FJOI2007]轮状病毒](https://www.luogu.com.cn/problem/P2144)
- [P3317 [SDOI2014]重建](https://www.luogu.com.cn/problem/P3317)
- [P4208 [JSOI2008]最小生成树计数](https://www.luogu.com.cn/problem/P4208)
## Part 9 计算几何
> 试着用计算机来解决几何问题吧!
### Part 9.1 凸包
> 凸包指在平面上能包含所有给定点的最小凸多边形。
- [P2742 【模板】二维凸包](https://www.luogu.com.cn/problem/P2742)
- [P2287 [HNOI2004]最佳包裹](https://www.luogu.com.cn/problem/P2287)
- [P3829 [SHOI2012]信用卡凸包](https://www.luogu.com.cn/problem/P3829)
- [P4680 [Ynoi2018]末日时在做什么?有没有空?可以来拯救吗?](https://www.luogu.com.cn/problem/P4680)
- [P4557 [JSOI2018]战争](https://www.luogu.com.cn/problem/P4557)
- [P5403 [CTS2019]田野](https://www.luogu.com.cn/problem/P5403)
### Part 9.2 旋转卡壳
> 旋转卡壳是一种求出凸包所有对踵点对的算法。
- [P1452 Beauty Contest](https://www.luogu.com.cn/problem/P1452)
- [P3187 [HNOI2007]最小矩形覆盖](https://www.luogu.com.cn/problem/P3187)
### Part 9.3 半平面交
> 多个半平面的交集称之为半平面交。
- [P3256 [JLOI2013]赛车](https://www.luogu.com.cn/problem/P3256)
- [P2600 [ZJOI2008]瞭望塔](https://www.luogu.com.cn/problem/P2600)
- [P4196 [CQOI2006]凸多边形](https://www.luogu.com.cn/problem/P4196)
- [P3297 [SDOI2013]逃考](https://www.luogu.com.cn/problem/P3297)
- [P4250 [SCOI2015]小凸想跑步](https://www.luogu.com.cn/problem/P4250)
- [P5328 [ZJOI2019]浙江省选](https://www.luogu.com.cn/problem/P5328)
## Part 10 杂项
> 这里的专题,有很多都难以纳入前面的类别中,故将他们单独列入了杂项。
### Part 10.1 模拟退火
> 模拟退火是一种随机化算法。当一个问题的方案数量极大(甚至是无穷的)而且不是一个单峰函数时,我们常使用模拟退火求解。
- [P1337 [JSOI2004]平衡点 / 吊打XXX](https://www.luogu.com.cn/problem/P1337)
- [P2503 [HAOI2006]均分数据](https://www.luogu.com.cn/problem/P2503)
- [P3878 [TJOI2010]分金币](https://www.luogu.com.cn/problem/P3878)
### Part 10.2 0/1 分数规划
> 0/1 分数规划用来求一个分式的极值。
- [P4377 [USACO18OPEN]Talent Show](https://www.luogu.com.cn/problem/P4377)
- [P3199 [HNOI2009]最小圈](https://www.luogu.com.cn/problem/P3199)
- [P3288 [SCOI2014]方伯伯运椰子](https://www.luogu.com.cn/problem/P3288)
- [P3705 [SDOI2017]新生舞会](https://www.luogu.com.cn/problem/P3705)
- [P4322 [JSOI2016]最佳团体](https://www.luogu.com.cn/problem/P4322)
### Part 10.3 离线算法
> 当题目不要求强制在线时,我们可以一次性读入所有询问来处理。
#### Part 10.3.1 CDQ 分治
> CDQ 分治是一个基于分治思想的离线算法。
- [P3810 【模板】三维偏序(陌上花开)](https://www.luogu.com.cn/problem/P3810)
- [P3157 [CQOI2011]动态逆序对](https://www.luogu.com.cn/problem/P3157)
- [P2487 [SDOI2011]拦截导弹](https://www.luogu.com.cn/problem/P2487)
- [P4690 [Ynoi2016]镜中的昆虫](https://www.luogu.com.cn/problem/P4690)
- [P3206 [HNOI2010]城市建设](https://www.luogu.com.cn/problem/P3206)
#### Part 10.3.2 整体二分
> 整体二分,顾名思义就是把多个查询一起二分解决。
- [P1527 [国家集训队]矩阵乘法](https://www.luogu.com.cn/problem/P1527)
- [P2617 Dynamic Rankings](https://www.luogu.com.cn/problem/P2617)
- [P3527 [POI2011]MET-Meteors](https://www.luogu.com.cn/problem/P3527)
- [P4602 [CTSC2018]混合果汁](https://www.luogu.com.cn/problem/P4602)
#### Part 10.3.3 莫队
> 莫队算法可以解决不少离线区间询问问题。
- [P1494 [国家集训队]小Z的袜子 /【模板】莫队](https://www.luogu.com.cn/problem/P1494)
- [P1903 [国家集训队]数颜色 / 维护队列 /【模板】带修莫队](https://www.luogu.com.cn/problem/P1903)
- [P5906 【模板】回滚莫队](https://www.luogu.com.cn/problem/P5906)
- [P4887 【模板】莫队二次离线(第十四分块(前体))](https://www.luogu.com.cn/problem/P4887)
- [P2709 小B的询问](https://www.luogu.com.cn/problem/P2709)
- [P3674 小清新人渣的本愿](https://www.luogu.com.cn/problem/P3674)
- [P3709 大爷的字符串题](https://www.luogu.com.cn/problem/P3709)
- [P4074 [WC2013]糖果公园](https://www.luogu.com.cn/problem/P4074)
- [P5501 [LnOI2019]来者不拒,去者不追](https://www.luogu.com.cn/problem/P5501)
### Part 10.4 奇怪的题目
> OI 界中有一些非常规套路的题目,这里放出来分享。
- [P4920 [WC2015]未来程序](https://www.luogu.com.cn/problem/P4920)
- [P5042 [国家集训队]丢失的题面(ydc的题面)](https://www.luogu.com.cn/problem/P5042)
- [P5285 [十二省联考2019]骗分过样例](https://www.luogu.com.cn/problem/P5285)
- [P5246 [集训队互测2016]消失的源代码](https://www.luogu.com.cn/problem/P5246)
### Part 10.5 非传统题
> 在 NOI 等比赛中,非传统题正越来越频繁出现。
>
> 非传统题主要包括以下几类:提交答案题,交互题,通信题。
#### Part 10.5.1 提交答案题
> 给你一些输入,你只需要提交这些输入对应的答案,即为提交答案题。
- [P1335 [NOI2013]小Q的修炼](https://www.luogu.com.cn/problem/P1335)
- [P1737 [NOI2016]旷野大计算](https://www.luogu.com.cn/problem/P1737)
- [P3614 yyy棋 II](https://www.luogu.com.cn/problem/P3614)
- [P3640 [APIO2013]出题人](https://www.luogu.com.cn/problem/P3640)
- [P3782 [WC2017]排序](https://www.luogu.com.cn/problem/P3782)
- [P3836 Nowruz](https://www.luogu.com.cn/problem/P3836)
- [P4920 [WC2015]未来程序](https://www.luogu.com.cn/problem/P4920)
- [P5402 [CTS2019]无处安放](https://www.luogu.com.cn/problem/P5402)
- [P5418 [CTSC2016]NOIP十合一](https://www.luogu.com.cn/problem/P5418)
- [P5600 【XR-4】尺规作图](https://www.luogu.com.cn/problem/P5600)