洛谷综合题单 2021-08-16 OI 暂无评论 492 次阅读 - 对于初学者，建议先完成 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 的内容（具体内容见下），在此基础上继续完成其他内容。 - 每个专题下的题目先给出模板，剩下的题目均按照难度递增顺序排序，部分难度较高的综合性题目建议达到一定能力后再尝试解决。 ## Part 0 试机题 > 三道试机题目。 - [x][P1000 超级玛丽游戏](https://www.luogu.com.cn/problem/P1000) - [x][P1001 A+B Problem](https://www.luogu.com.cn/problem/P1001) - [x][P1008 三连击](https://www.luogu.com.cn/problem/P1008) ## Part 1 入门阶段 > 本部分内容针对入门 OIer ，主要是语言基础内容。 ### Part 1.1 从零开始 > 语言基础题。 - [x][P1421 小玉买文具](https://www.luogu.com.cn/problem/P1421) - [x][P1909 买铅笔](https://www.luogu.com.cn/problem/P1909) - [x][P1089 津津的储蓄计划](https://www.luogu.com.cn/problem/P1089) - [x][P1085 不高兴的津津](https://www.luogu.com.cn/problem/P1085) - [x][P1035 级数求和](https://www.luogu.com.cn/problem/P1035) - [x][P1980 计数问题](https://www.luogu.com.cn/problem/P1980) - [x][P1014 Cantor表](https://www.luogu.com.cn/problem/P1014) - [x][P1307 数字反转](https://www.luogu.com.cn/problem/P1307) ### Part 1.2 数组基础 > 数组可以用于存储大量的信息。 - [x][P1046 陶陶摘苹果](https://www.luogu.com.cn/problem/P1046) - [x][P1047 校门外的树](https://www.luogu.com.cn/problem/P1047) - [x][P1427 小鱼的数字游戏](https://www.luogu.com.cn/problem/P1427) - [x][P2141 珠心算测验](https://www.luogu.com.cn/problem/P2141) - [x][P5594 【XR-4】模拟赛](https://www.luogu.com.cn/problem/P5594) ### Part 1.3 字符串基础 > 字符串是特殊的数组，但它也有很多自身的特点。 - [x][P5015 标题统计](https://www.luogu.com.cn/problem/P5015) - [x][P1055 ISBN号码](https://www.luogu.com.cn/problem/P1055) - [x][P1308 统计单词数](https://www.luogu.com.cn/problem/P1308) - [x][P2010 回文日期](https://www.luogu.com.cn/problem/P2010) - [x][P1012 拼数](https://www.luogu.com.cn/problem/P1012) - [ ][P5587 打字练习](https://www.luogu.com.cn/problem/P5587) ### Part 1.4 函数，递归及递推 > 这是初学者最难理解的部分，建议画出递归图来理解递归的过程。 - [x][P1028 数的计算](https://www.luogu.com.cn/problem/P1028) - [x][P1036 选数](https://www.luogu.com.cn/problem/P1036) - [x][P1464 Function](https://www.luogu.com.cn/problem/P1464) - [x][P5534 【XR-3】等差数列](https://www.luogu.com.cn/problem/P5534) - [x][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) - [ ][P1824 进击的奶牛](https://www.luogu.com.cn/problem/P1824) - [ ][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) - [ ][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 多项式 > 对多项式的运算进行优化，从而能够解决规模更大的问题。 - [ ][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) - [ ][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) #### Part 10.5.2 交互题 > 在交互题中，选手程序需要通过与测评程序交互来完成任务。 - [ ][P1733 猜数（IO交互版）](https://www.luogu.com.cn/problem/P1733) - [ ][P1947 猜数](https://www.luogu.com.cn/problem/P1947) - [ ][P5208 [WC2019]I 君的商店](https://www.luogu.com.cn/problem/P5208) - [ ][P5473 [NOI2019]I 君的探险](https://www.luogu.com.cn/problem/P5473) - [ ][P6541 [WC2018]即时战略](https://www.luogu.com.cn/problem/P6541) - [ ][P6558 [APIO2017]考拉的游戏](https://www.luogu.com.cn/problem/P6558) 标签: none 本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。