对于初学者，建议先完成 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 试机题

三道试机题目。

P1000 超级玛丽游戏P1001 A+B ProblemP1008 三连击

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 FunctionP5534 【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 跳石头P1824 进击的奶牛P1902 刺杀大使P1314 聪明的质监员P1083 借教室P4343 [SHOI2015]自动刷题机

Part 2.4 分治

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

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

Part 2.5 贪心

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

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

Part 2.6 构造

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

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

Part 2.7 高精度

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

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

Part 2.8 前缀和 & 差分

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

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

Part 3 搜索

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

Part 3.1 深度优先搜索

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

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

P1219 八皇后P1019 单词接龙P5194 [USACO05DEC]ScalesP5440 【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 SubsetsP4799 [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-BytecomputerP4158 [SCOI2009]粉刷匠P5301 [GXOI/GZOI2019]宝牌一大堆

Part 4.2 背包动态规划

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

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

Part 4.3 区间动态规划

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

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

Part 4.4 树形动态规划

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

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

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

Part 4.5 状态压缩动态规划

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

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

Part 4.6 倍增优化动态规划

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

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

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

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

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

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

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

P1776 宝物筛选P3089 [USACO13NOV]Pogo-CowP3572 [POI2014]PTA-Little BirdP3522 [POI2011]TEM-TemperatureP4544 [USACO10NOV]Buying FeedP5665 划分P1973 [NOI2011]Noi嘉年华P2569 [SCOI2010]股票交易P4852 yyf hates choukapai

Part 4.9 斜率优化动态规划

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

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

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

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

P3515 [POI2011]Lightning ConductorP4767 [IOI2000]邮局P1912 [NOI2009]诗人小GP1973 [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 【模板】插头dpP2289 [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 TransmissionP3435 [POI2006]OKR-Periods of WordsP4824 [USACO15FEB]Censoring (Silver)P2375 [NOI2014]动物园P3426 [POI2005]SZA-TemplateP3193 [HNOI2008]GT考试

Part 5.3 Manacher

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

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

Part 5.4 Trie树

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

P3879 [TJOI2010]阅读理解P2292 [HNOI2004]L语言P2922 [USACO08DEC]Secret MessageP3065 [USACO12DEC]First!P3294 [SCOI2016]背单词P4407 [JSOI2009]电子字典P4551 最长异或路径P4683 [IOI2008]Type PrinterP3783 [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 PatternsP4051 [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]meP5539 【XR-3】Unknown Mother-GooseP5523 [yLOI2019]珍珠

Part 6.2 整除相关

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

Part 6.2.1 素数

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

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

Part 6.2.2 最大公约数

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

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

P5435 【模板】快速 GCDP5436 【XR-2】缘分P1029 最大公约数和最小公倍数问题P1414 又是毕业季IIP2152 [SDOI2009]SuperGCDP1072 Hankson 的趣味题

Part 6.2.3 欧拉函数

欧拉函数 $ \varphi (x) $ 表示了小于 $ x $ 的数字中，与 $ x $ 互质的数字个数。

P2158 [SDOI2008]仪仗队P2568 GCDP2398 GCD SUMP4139 上帝与集合的正确用法

Part 6.3 同余方程

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

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

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

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

Part 6.3.2 中国剩余定理

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

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

Part 6.3.3 高次同余方程

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

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

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

Part 6.4 博弈论

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

P2197 【模板】nim游戏P1288 取数游戏IIP1290 欧几里德的游戏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 【模板】高斯消元法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 多项式

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

P3803 【模板】多项式乘法（FFT）P4238 【模板】多项式求逆P4245 【模板】任意模数NTTP4512 【模板】多项式除法P4717 【模板】快速沃尔什变换P4721 【模板】分治 FFTP4725 【模板】多项式对数函数P4726 【模板】多项式指数函数P4781 【模板】拉格朗日插值P5050 【模板】多项式多点求值P5158 【模板】多项式快速插值P5205 【模板】多项式开根P5245 【模板】多项式快速幂P5273 【模板】多项式幂函数 (加强版)P5282 【模板】快速阶乘算法P5373 【模板】多项式复合函数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 bP3455 [POI2007]ZAP-QueriesP3327 [SDOI2015]约数个数和P1829 [国家集训队]Crash的数字表格 / JZPTABP4619 [SDOI2018]旧试题P3704 [SDOI2017]数字表格P5518 [MtOI2019]幽灵乐团

Part 6.10 筛法

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

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

Part 6.11 线性规划

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

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

Part 6.12 数值方法

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

Part 6.12.1 三分法

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

P3382 【模板】三分法P1883 函数

Part 6.12.2 自适应辛普森法

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

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

Part 6.13 置换群

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

P4980 【模板】Polya定理P1446 [HNOI2008]CardsP2561 [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 GP2024 [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 LineupP5012 水の数列P5344 【XR-1】逛森林P2048 [NOI2010]超级钢琴

Part 7.7 树状数组

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

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

Part 7.8 线段树

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

P3372 【模板】线段树 1P3373 【模板】线段树 2P5490 【模板】扫描线P4588 [TJOI2018]数学计算P1502 窗口的星星P2471 [SCOI2007]降雨量P2824 [HEOI2016/TJOI2016]排序P3722 [AH2017/HNOI2017]影魔P4097 [HEOI2013]SegmentP4198 楼房重建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 KingP1552 [APIO2012]派遣P3261 [JLOI2015]城池攻占P3273 [SCOI2011]棘手的操作P4331 [BOI2004]Sequence

Part 7.11 主席树

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

P2468 [SDOI2010]粟粟的书架P3302 [SDOI2013]森林P3168 [CQOI2015]任务查询系统P4559 [JSOI2018]列队P2633 Count on a treeP3293 [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]方伯伯的OJP5321 [BJOI2019]送别

Part 7.13 树链剖分

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

P3384 【模板】树链剖分P3313 [SDOI2014]旅行P2590 [ZJOI2008]树的统计P1505 [国家集训队]旅游P2486 [SDOI2011]染色P3258 [JLOI2014]松鼠的新家P4069 [SDOI2016]游戏P4211 [LNOI2014]LCAP4592 [TJOI2018]异或P5305 [GXOI/GZOI2019]旧词P5354 [Ynoi2017]由乃的OJP5499 [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]OTOCIP1501 [国家集训队]Tree IIP2387 [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]TATTP4169 [Violet]天使玩偶/SJY摆棋子P4390 [BOI2007]MokiaP4475 巧克力王国P2093 [国家集训队]JZPFARP5471 [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 ToursP1266 速度限制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 RoadsP1991 无线通讯网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 PromP2746 [USACO5.3]Network of SchoolsP1407 [国家集训队]稳定婚姻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 SteeplechaseP3731 [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 ControlP1345 [USACO5.4]TelecowmunicationP2057 [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 【模板】点分治1P2634 [国家集训队]聪聪可可P2664 树上游戏P3714 [BJOI2017]树的难题P4149 [IOI2011]RaceP3241 [HNOI2015]开店P4075 [SDOI2016]模式字符串P4183 [USACO18JAN]Cow at Large PP4292 [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 ContestP3187 [HNOI2007]最小矩形覆盖

Part 9.3 半平面交

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

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

Part 10 杂项

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

Part 10.1 模拟退火

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

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

Part 10.2 0/1 分数规划

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

P4377 [USACO18OPEN]Talent ShowP3199 [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 RankingsP3527 [POI2011]MET-MeteorsP4602 [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棋 IIP3640 [APIO2013]出题人P3782 [WC2017]排序P3836 NowruzP4920 [WC2015]未来程序P5402 [CTS2019]无处安放P5418 [CTSC2016]NOIP十合一P5600 【XR-4】尺规作图

Part 10.5.2 交互题

在交互题中，选手程序需要通过与测评程序交互来完成任务。

P1733 猜数（IO交互版）P1947 猜数P5208 [WC2019]I 君的商店P5473 [NOI2019]I 君的探险P6541 [WC2018]即时战略P6558 [APIO2017]考拉的游戏

Copyleft

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-J0Xt39cG-1613870443314)(https://i.creativecommons.org/l/by-sa/4.0/88x31.png)]

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

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