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