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

**这个题单的历史使命已经完成了，很长一段时间里将不再更新。** **在 [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://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)