省选计划

用户头像 发布于 2022-11-21 最后更新于 2025-11-20 146 次阅读

AI 摘要

踏上省选之路，数学、图论、DP、数据结构，你是否准备好了？从矩阵乘法到差分约束，从状压DP到可持久化线段树，海量知识点与精选试题，助你解锁算法的奥秘，冲刺更高峰！

【准备1】数学与数论

刷题不局限于洛谷的，所以你可以去其它地方交洛谷没有的题目。

BZOJ题目提交网址：https://darkbzoj.tk/

HDU：http://acm.hdu.edu.cn/

POJ：http://poj.org/

UOJ：https://uoj.ac/

LOJ：https://loj.ac/

以下是 NOIP 选手可以提升的知识点和题单

  • 矩阵快速幂：P1397、P3990 https://www.cnblogs.com/liuwenyao/p/8514920.html

  • 同余方程与中国剩余定理：P2421、P4296 https://www.luogu.com.cn/blog/1239004072Angel/post-shuo-xue-qiu-xie-yi-lei-fang-cheng-di-fang-fa （到第二点线性同余为止）

  • 取模和逆元：P1641、P2155 https://www.luogu.com.cn/blog/1239004072Angel/post-shuo-xue-sheng-fa-ni-yuan

  • 高斯消元法：P2455、BZOJ3270 https://www.cnblogs.com/xcg123/p/10679600.html

  • 概率与期望：P4206、P3232、HDU4652、BZOJ1419 https://www.luogu.com.cn/blog/lx-2003/random-variables

  • 素数筛法：BZOJ1968、BZOJ2190 https://www.luogu.com.cn/problem/P3383

一些需要了解的tricks：

位运算：

https://www.luogu.com.cn/blog/chengni5673/er-jin-zhi-yu-wei-yun-suan
https://www.cnblogs.com/dudujerry/p/11275205.html

或者直接在 OI Wiki 中查看。位运算是状压 DP 等算法中中常用到的状态压缩技巧，需要熟练掌握，但部分位运算对代码时间优化微弱，不可剑走偏锋。

快速乘：https://www.cnblogs.com/812-xiao-wen/p/10543023.html

读入与输出优化：https://www.luogu.com.cn/blog/encore/io-you-hua-nei-suo-shi 如果读入量不高（1e6以内），不一定需要优化。
- P2158 [SDOI2008]仪仗队
- P1403 [AHOI2005]约数研究
- P1397 [NOI2013] 矩阵游戏
- P3990 [SHOI2013]超级跳马
- P2421 [NOI2002] 荒岛野人
- P4296 [AHOI2007]密码箱
- P1641 [SCOI2010]生成字符串
- P2155 [SDOI2008]沙拉公主的困惑
- P2455 [SDOI2006]线性方程组
- CF113D Museum
- P4206 [NOI2005] 聪聪与可可
- P3232 [HNOI2013]游走

【准备2】图论

以下是 NOIP 选手可以提升的知识点和题单

  • 最短路：P1821、P1875、P2047
  • 生成树：P1265、P1991、P2323、P4047 https://www.cnblogs.com/zhchoutai/p/8687614.html
  • 拓扑排序：P3243
    差分约束（以下两个都是最短路的变形）：P1260、P3275、P1993 http://www.cppblog.com/menjitianya/archive/2015/11/19/212292.html 整理了很多练习题。差分约束目前来看不常考察，但是是不一定能在考场中及时看出算法的类型，因此仍然建议熟练学习。
  • 传递闭包：P4306
    以下内容略微超纲，但可供提升，有时有可能可以用到

  • 联通分量（Tarjan）：P2403、P3225 https://www.luogu.com.cn/blog/styx-ferryman/chu-tan-tarjan-suan-fa-qiu-qiang-lian-tong-fen-liang-post

  • 二分图：P1129、P1155 https://www.luogu.com.cn/blog/xht37/er-fen-tu-yu-wang-lao-liu
  • 次短路：BZOJ1736
    一些需要了解的tricks：

图论的小技巧以及扩展https://www.luogu.com.cn/blog/chengni5673/tu-lun-di-xiao-ji-qiao-yi-ji-kuo-zhan

各种最短路算法的介绍和比较 https://www.luogu.com.cn/blog/FrozaFerrari/xue-tu-lun-ni-zhen-di-liao-xie-zui-duan-lu-ma-post

【准备4】动态规划

需要了解一些比较常见的动态规划的套路。当然已经假设您已经学会了普及组难度的动态规划和基本概念——背包问题、最长不降子序列、最长公共子序列等。下面的动规是 NOIP 中可能会考的类型。

【准备5】数据结构

  1. 一些基本的维护数据的 trick：

- 前缀和：LuoguAT2412、P3406、P1115
- 差分：P3128、P4515、P3066、HDU6514
- 离散化：P1360、P2061
- 单调栈：BZOJ1307、P3194
- 单调队列：P1091、P2216、P2564
2. 具体的数据结构算法（NOIP级别）
- 栈&队列&堆：P2341、P3551、P2564、P3594、P1090
- 并查集：P3068、P4147
- 线段树&树状数组：P1972、P2023、P4560
- 倍增、RMQ
- P2341 [USACO03FALL][HAOI2006]受欢迎的牛 G
- P3551 [POI2013]USU-Take-out
- P2564 [SCOI2009]生日礼物
- P3594 [POI2015]WIL-Wilcze doły
- P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G
- P3068 [USACO13JAN]Party Invitations S
- P4147 玉蟾宫
- P1972 [SDOI2009]HH的项链
- P2023 [AHOI2009] 维护序列
- P4560 [IOI2014]Wall 砖墙
- AT2412 [JOI 2007 Final]最大の和
- P3406 海底高铁
- P1115 最大子段和
- P3128 [USACO15DEC]Max Flow P
- P4515 [COCI2009-2010#6] XOR
- P3066 [USACO12DEC]Running Away From the Barn G
- P1360 [USACO07MAR]Gold Balanced Lineup G
- P2061 [USACO07OPEN]City Horizon S
- P3194 [HNOI2008]水平可见直线
- P1091 [NOIP2004 提高组] 合唱队形
- P2216 [HAOI2007]理想的正方形

【准备6，重要】综合思维题目

这些题目的难度和范围大约等于 NOIP 较难的题目。如果能够可以完成的话最好，但是如果没有时间的话也可以嘴巴 AC。

有条件的话可以限时、随便抽选 3 题没有写过的题目，先不要看题解，当做 OI 赛制自行进行模拟测试。

【前期 1】数据结构 1

数据结构是处理数据的骨架。本周已经假设大家学习完了准备阶段 DS 的知识,直接从基础省选的内容开开始。

以下题解的板子各有特点，请选择一个符合自己习惯的板子并熟练掌握。

基础任务（尽可能全部掌握）

线段树入门：

  • 线段树入门 https://www.luogu.com.cn/blog/pks-LOVING/senior-data-structure-qian-tan-xian-duan-shu-segment-tree
  • 位运算线段树 https://www.luogu.com.cn/blog/82152/Introduction-of-zkwSegmentTree
    题目：

P2023，P4513，P1471，P6327，P3792

题单（如果有多余的功夫可以嘴巴 AC，选择一些感兴趣的完成）：

  • https://www.luogu.com.cn/training/1124
  • https://www.luogu.com.cn/training/1010

线段树进阶：

P5278，P6617，P5069，P5608，HDU6315，UOJ228，P3747

平衡树：

treap：

https://www.luogu.com.cn/blog/Chanis/fhq-treap

https://www.luogu.com.cn/blog/HOJQVFNA/qian-xi-treap-ping-heng-shu

https://www.luogu.com.cn/blog/85514/fhq-treap-xue-xi-bi-ji

替罪羊树：

https://www.luogu.com.cn/blog/Apocrypha/scapegoattree-yang-xie

https://www.luogu.com.cn/blog/hanzhongtlx-juruo/ti-zui-yang-shu-xue-xi-bi-ji

splay：

https://www.luogu.com.cn/blog/tiger0132/slay-notes

题目：

P2042，P5482，P4036，P3586，P6105，P5610，P5068，P5066

题单：

https://www.luogu.com.cn/training/3174

https://www.luogu.com.cn/training/5005

进阶任务（供学有余力的同学学习）

成都七中openjudge的数据结构部分

http://cdqz.openjudge.cn/ds/

“李超线段树”类问题：

https://www.luogu.com.cn/blog/infinity-dimension/Li-Chao-Tree

题目：P4097，P4069

题单：https://www.luogu.com.cn/training/3243

“楼房重建”类问题：

https://www.luogu.com.cn/blog/PinkRabbit/Segment-Tree-and-Prefix-Maximums
基本够用的方法

其余技巧

https://www.luogu.com.cn/blog/PinkRabbit/solution-cf1340f 题目
https://www.luogu.com.cn/problem/P6781 题目
https://www.cnblogs.com/jz-597/p/14070633.html 题目
https://peehs-moorhsum.blog.uoj.ac/blog/5486 C题

题目：P4198，CF1340F，P6781，UOJ515

所谓的“ODT”算法：

https://zhuanlan.zhihu.com/p/102786071

题目：https://www.luogu.com.cn/problem/CF896C

【前期 6】数据结构 2

可持久化线段树与可持久化trie：

https://www.luogu.com.cn/blog/your-alpha1022/WeightSegmentTree-ChairmanTree

https://www.luogu.com.cn/blog/sdlang/Trie-study-text

题目：

HDU4757,P3567,P2839,UOJ218,P3402,P3293,P4197,P4899,P3302

题单：

https://www.luogu.com.cn/training/2971 的第二个部分

https://www.luogu.com.cn/training/1176

可持久化可合并堆：

https://www.luogu.com.cn/blog/cytus/ke-bing-dui-zhi-zuo-pian-shu

可持久化平衡树：

https://blog.sengxian.com/algorithms/treap

题目：

HDU 6087,P5055,P5350,P5586

树套树：

https://www.luogu.com.cn/blog/qiuly/qian-tan-shu-tao-shu-xian-duan-shu-tao-ping-heng-shu-post

https://www.luogu.com.cn/blog/3383669u/zong-shu-tao-shu-qian-xi-chang-yong-jie-gou-di-te-xing

https://www.luogu.com.cn/blog/bfqaq/qian-tan-shu-zhuang-shuo-zu-quan-zhi-shu

题目：

P3380,P4396,P3810,P4054,P3759,P3157,P3332,P3242,P4690,P5445,P3688

题单：

https://www.luogu.com.cn/training/1176

【前期 2】数学 1

之前调查了一下，大家似乎多少有点数学基础，太基础的内容就不强调了吧……

本来想自己多写点东西，但这周被一串事情和ddl安排了……也许晚些时候可以和大家见面。不过，对任何地方有任何问题可以随时找我，我之后也可能会往里面补充点东西。

现在 luogu 的 markdown 似乎不支持 - [ ] 和 - [x] 之类的写法，- [x] 表示基础任务，- [ ] 表示目前阶段可选择性了解（题单中部分题也是选择性的（比如需要选学知识的题，推导太困难的题））。

呃……东西有点多的样子……听说有同学是打印的，大概可以先看看内容再选择地打印一些吧……（群里讨论吧

  • 找规律！找规律！！一定要找规律！！！这很重要，看到题一定要先试试能不能找规律，不然，万一你推式子水平不够到位，还碰上了 NOIP 2018 D2T2，或是 NOI 2019 D2T2，你就会像我一样，爱上这款████的游戏
  • 数论
    • 整除性
      • 定义：整除、带余除法、gcd
        -[x] 裴蜀定理、欧几里得算法

        • 扩展欧几里得算法 https://oi-wiki.org/math/gcd/
          • 方程：$ax + by = c$
        • 类欧几里得 https://oi-wiki.org/math/euclidean/
  • 素数
    • 定义：素数
    • 算术基本定理
    • 整除偏序的结构 自己写的一点东西，建议配合常见Möbius反演定理教程食用
      • Möbius反演公式：zeta变换，Möbius变换，lcm卷积，gcd卷积 同上 https://oi-wiki.org/math/mobius/ https://www.luogu.com.cn/blog/lx-2003/mobius-inversion
    • 埃氏筛法、欧拉筛法、求任意积性函数 1~n 处的值 https://oi-wiki.org/math/sieve/
    • 整数分解：试除法、筛法预处理
  • 同余
    • 线性同余方程组
      • 线性同余方程 $bx\equiv a\pmod n$ https://oi-wiki.org/math/linear-equation/
      • 合并两个形如 x\equiv a\pmod nx≡a(modn) 的方程 链接同下，不知为何被人称为“exCRT”
      • 中国剩余定理、直接构造解 https://oi-wiki.org/math/crt/
        • 将 $\bmod n$ 的问题分解为 $\bmod p^k$
          的问题，然后合并
    • Lucas定理 https://oi-wiki.org/math/lucas/
  • $\mathbb{Z}/n\mathbb{Z}$
    • 费马小定理、欧拉定理 https://oi-wiki.org/math/fermat/
      • 素性测试：Miller-Rabin primality test https://oi-wiki.org/math/prime/
    • 乘法逆元、$O(n+\log p)$ 时间求 $n$ 个数的乘法逆元 https://oi-wiki.org/math/inverse/
    • 模 $n$ 整数的乘法群 $(\mathbb{Z}/n\mathbb{Z})^\times$
      、原根、指标 / 离散对数。

      • 离散对数：BSGS https://oi-wiki.org/math/bsgs/
        • 方程：$x^b=a$、$b^x=a$同上https://www.luogu.com.cn/blog/ShadderLeave/5days-equiv-from-beginner-to-killer
      • 整数分解：Pollard's rho algorithm https://oi-wiki.org/math/pollard-rho/
  • 计数组合学
    • 基础 https://oi-wiki.org/math/combination/
    • 斯特林数 https://oi-wiki.org/math/stirling/
    • 容斥 自己写的一点容斥原理简介 https://oi-wiki.org/math/inclusion-exclusion-principle/
      https://www.luogu.com.cn/blog/KingSann/chu-tan-rong-chi-yuan-li https://www.luogu.com.cn/blog/command-block/min-max-rong-chi-xiao-ji
    • 生成函数 https://www.luogu.com.cn/blog/lx-2003/generating-function https://www.luogu.com.cn/blog/lx-2003/generating-function-advanced https://oi-wiki.org/math/gen-func/ogf/ https://oi-wiki.org/math/gen-func/egf/
  • 代数
    • 多项式的一些基本概念（不，当然不是你想的那种多项式（这部分其实我非常想自己写介绍的（而且资料中还有点小问题……），但可能要过两天才能写完吧（明天又有一堆ddl，sigh
    • 拉格朗日插值 https://oi-wiki.org/math/poly/lagrange/
    • 多项式乘法、FFT https://oi-wiki.org/math/poly/fft/ https://www.luogu.com.cn/blog/105254/qian-tan-fft-zong-ft-dao-fft https://www.luogu.com.cn/blog/KingSann/post-ye-hu-shi-leng-men-suan-fa-dan-wei-gen-fan-yan（有一说一这个所谓的“单位根反演”（同样不知道怎么来的名字）是 DFT 推导的一部分）
    • FMT、FWT https://oi-wiki.org/math/poly/fwt/

推荐阅读：
- 如果想学推组合式子的话
- 《具体数学》
- https://www.cnblogs.com/meowww/p/6410869.html
- P3383 【模板】线性筛素数
- P3811 【模板】乘法逆元
- P4549 【模板】裴蜀定理
- P5656 【模板】二元一次不定方程 (exgcd)
- P1082 [NOIP2012 提高组] 同余方程
- P5091 【模板】扩展欧拉定理
- P3807 【模板】卢卡斯定理
- P6091 【模板】原根
- P3846 [TJOI2007] 可爱的质数/【模板】BSGS
- P2303 [SDOI2012] Longge 的问题
- P1463 [POI2002][HAOI2007]反素数
- P1128 [HNOI2001] 求正整数
- P3868 [TJOI2009]猜数字
- P4777 【模板】扩展中国剩余定理（EXCRT）
- P4774 [NOI2018] 屠龙勇士
- P2522 [HAOI2011]Problem b
- P3312 [SDOI2014]数表
- P3327 [SDOI2015]约数个数和
- P1829 [国家集训队]Crash的数字表格 / JZPTAB
- P5330 [SNOI2019]数论
- P5323 [BJOI2019]光线
- P4454 [CQOI2018]破解D-H协议
- P4195 【模板】扩展BSGS
- P4720 【模板】扩展卢卡斯
- P4619 [SDOI2018]旧试题
- P4607 [SDOI2018]反回文串
- P3197 [HNOI2008]越狱
- P2822 [NOIP2016 提高组] 组合数问题
- P2606 [ZJOI2010]排列计数
- P4461 [CQOI2018]九连环
- P4562 [JXOI2018]游戏
- P3223 [HNOI2012]排队
- P5023 [NOIP2018 提高组] 填数游戏
- P6620 [省选联考 2020 A 卷] 组合数问题
- P4492 [HAOI2018]苹果树
- P5339 [TJOI2019]唱、跳、rap和篮球
- P5472 [NOI2019] 斗主地
- P5342 [TJOI2019]甲苯先生的线段树
- P7136 [THUPC2021 初赛] 方格游戏
- P4781 【模板】拉格朗日插值
- P3803 【模板】多项式乘法（FFT）
- P4717 【模板】快速莫比乌斯/沃尔什变换 (FMT/FWT)
- CF662C Binary Table
- P4491 [HAOI2018]染色
- P5293 [HNOI2019]白兔之舞

【前期 7】数学2与计算几何

还在做.jpg

数学部分剩下的东西很多很杂.jpg 所以下面写的很多东西都没什么关系。

需要优先掌握的（会作为别的东西的前置知识 or 经常考）会用 粗体 标注。

很难掌握，或者代码很复杂的会用 斜体 标注。

数学部分

【前期 3】字符串

本周需要大家掌握的知识点有：

  1. Trie 树（其实这个东西非常基础，大家应该都会吧）
  2. kmp（这个应当熟练掌握，今年 NOIP 都有考到）
  3. AC 自动机（这个东西就是 kmp 的进阶版，对于没有接触过自动机结构的同学来说这个可能是最容易理解的自动机之一了）
  4. 后缀数组（即 Suffix Array，简称 SA。这个东西是解决字符串问题的一大利器，其精华在于 height 数组。学好了可以用它做很多字符串题）
  5. 后缀自动机（即 Suffix Automaton，简称 SAM。这个东西相当强大，但是相对 SA 来说较难理解。然后由于 CYJian 是 SA 党而 SAM 学了之后不经常使用所以现在对其理解不是很深刻，所以有关 SAM 的 CYJian 无法解决的问题可以询问 CYJian 的同学 Kewth，当然如果后面 Kewth 负责的专题周有问题也可以来找 CYJian）
  6. Manacher（俗称马拉车。是一个求每个位置作为回文中心时最长回文半径的算法。这个东西可以配合使用回文串的各种优良性质来解决问题）
  7. 回文树（貌似也会被称作回文自动机。当你对自动机结构相当熟练之后，你会觉得这个东西如同 AC 自动机一样相当的简单。然而由于Manacher 能解决绝大多数的回文串问题，所以这个算法其实相对来说比较鸡肋。不过仍然存在回文树能做而 Manacher 不能做的题目）

如果以上知识点没有学过，可以到 OIwiki 上进行学习（如果会这个算法但几乎完全不了解一些实际使用的小 trick，也可以上 OIwiki 翻阅一下，了解一些实用小 trick）。我本人学习这些字符串算法的时候都是在 OIwiki 上学的，因此感觉只要好好阅读 OIwiki 上的内容就足够学懂了。当然下面也会推荐一些博客给大家，大家可以视自身情况选择性的阅读（持续更新）：

yyb 的字符串合集

洛谷日报内容收集：

SA：初学资料

SAM：初学资料

Manacher：初学资料

PAM：初学资料

选读内容：

后缀树

SA_IS

Lyndon Word

Hash

一些补充：

  1. 字符串哈希能做的题，一般来说用其他的字符串算法应该也能处理，故此份题单不会专门涉及此方面算法。
  2. 如果觉得时间比较紧张，难以一下子全部掌握，那么我建议大家按照上面我写下来的顺序依次学习（如果觉得 SAM 太难也可以选择先学 Manacher 再啃 SAM）
  3. 题单里头除了模板题之外，都是可能存在多种解法的题。大家可以多多思考一下，试试能不能用其它算法解决。另外，这里头的题有的可能比较难，不一定要求能够全部都做出来。实在不会的题可以翻看题解学习其解题的思路，积累经验。
  4. 这里是我在 NOI 前写给自己看的字符串的简易复习小结，由于是给自己复习用，所以写的东西可能比较简略，可能没有那么规范，并且带有一定的主观看法。大家可以看情况阅读。其实我大部分字符串都是直接看 OIwiki 学的，所以这里头有些内容和 OIwiki 上的重合率比较高。其实在 OIwiki 上学应该就能学会了，缺的可能就只有做题的经验。所以如果在学习算法的时候有困惑可以先自己试着思考一下，实在不会就可以直接提问。
  5. 如果实在学不会 SAM 其实问题也不是很大，只要把 SA 钻研得够深，就能整出一些弱化的替代品出来。——SA 党忠实拥簇者。 最好还是要学会 SAM，不然做某些题的时候会比较吃力，比如 [NOI2018]你的名字。
  6. OIwiki 的字符串部分在下方都会有一些经典应用，大家可以先试着做做那些简单例题加深理解。
  7. 一点心得：字符串算法，其实学会 AC 自动机、SAM、Manacher 就基本能解决字符串相关题目了。如果实在不能熟练掌握 SAM，可以先试着上手 SA，这个还是比较容易熟练掌握的。但是字符串问题中许多困难的问题基本都是以 SAM 为基础进行考察的，所以对于怀有梦想，不仅仅局限于“只要进省队就好了”“只要蹭上 Au 分数线就好了”的同学们来说，熟练掌握这些东西仅仅只是基础。这一周我也没有安排更加深入的东西（比如 runs，比如 border 的各种理论），是因为考虑到大家平均水平可能不是很高，所以最好还是先学好基础的东西以确保能够有进入省队，甚至触及 Au 分数线的底子。

- P3375 【模板】KMP字符串匹配
- P5357 【模板】AC自动机（二次加强版）
- P3809 【模板】后缀排序
- P3804 【模板】后缀自动机 (SAM)
- P3805 【模板】manacher算法
- P5496 【模板】回文自动机（PAM）
- CF471D MUH and Cube Walls
- P2375 [NOI2014] 动物园
- P4555 [国家集训队]最长双回文串
- P1659 [国家集训队]拉拉队排练
- P3426 [POI2005]SZA-Template
- CF808G Anthem of Berland
- P3121 [USACO15FEB]Censoring G
- P2444 [POI2000]病毒
- P2414 [NOI2011] 阿狸的打字机
- P2336 [SCOI2012]喵星球上的点名
- P2463 [SDOI2008]Sandy的卡片
- P3181 [HAOI2016]找相同字符
- P3346 [ZJOI2015]诸神眷顾的幻想乡
- P4081 [USACO17DEC]Standing Out from the Herd P
- P3649 [APIO2014]回文串
- P3975 [TJOI2015]弦论
- P6257 [ICPC2019 WF]First of Her Name
- P7046 「MCOI-03」诗韵
- P2178 [NOI2015] 品酒大会
- P4156 [WC2016]论战捆竹竿
- P6292 区间本质不同子串个数
- P4022 [CTSC2012]熟悉的文章
- P5287 [HNOI2019]JOJO
- P5284 [十二省联考2019]字符串问题
- P4384 [八省联考2018]制胡窜
- P5115 Check,Check,Check one two!
- CF587F Duff is Mad
- P4770 [NOI2018] 你的名字
- CF954I Yet Another String Matching Problem
- CF1073G Yet Another LCP Problem
- CF547E Mike and Friends
- P4482 [BJWC2018]Border 的四种求法
- P1117 [NOI2016] 优秀的拆分
- CF932G Palindrome Partition

【前期 4】图论与网络流

这里默认大家有 NOIP 级别的图论基础（包括：DFS/BFS，最短路，拓扑排序，最小生成树等）。

下面收录了一部分（大部分，除了一些质量欠佳的）相关的洛谷日报，以及 OI-wiki 的相关内容。所有未标明来源的链接均为网络上选取的写的较好的博客。

红色星星 $\color{red}{\star}$ 表示选学（学有余力的情况下可以去学）内容。

图论部分

  • 双连通或强连通相关：
    • Tarjan 算法 OI-wiki 求点双连通/边双连通分量，求割点和桥；求有向图强连通分量 OI-wiki
    • 缩点；$\color{red}{\star}$ 圆方树 日报#153
  • 二分图相关 日报#148 的前半部分：
    • 基础：定义，dfs 二染色
    • 二分图最大匹配: 匈牙利算法 OI-wiki，复杂度 $O(NM)$，或转化成最大流使用 Dinic 算法复杂度为 $O(M\sqrt{N})$ 日报#302
    • 二分图最大权匹配: KM 算法 OI-wiki，复杂度 $O(N^3)$，日报#302
    • 二分图最大独立集/最小点覆盖/最小边覆盖及其构造算法 _rqy 的 blog
    • Hall 定理，正则二分图 _rqy 的 blog 这个我没听说哪里考过，没有时间可以先不学
  • 生成树相关：
    • Borůvka 算法 OI-wiki: 最小生成树的另一种算法，可了解，有时候很好用
    • Kruskal 重构树 OI-wiki：同上，不学也行，但是有时很好用
    • 次小生成树 OI-wiki
    • 最小斯坦纳树 OI-wiki: 本质上是状压 DP
    • 矩阵树定理 OI-wiki，日报#272
    • $\color{red}{\star}$ 最小树形图: 朱-刘算法，或优化后的 Tarjan 算法 OI-wiki
  • 最短路相关：
  • 杂项：

网络流部分

这部分的一个优秀参考文献：《网络流的一些建模方法》 东营市胜利第一中学 姜志豪 （2016年候选队论文集）。

做网络流题的时候需要注意不要把最小割和最大流搞混。

基础练习题见 网络流24题。本题单里收录了其中一部分。

日报#148 的后半部分（网络流部分）写的也非常好，建议阅读。

【前期 5】动态规划

tips: 这里动态规划囊括了一般的递推，而不局限于最优化。大多时候用不着区分它们。

动态规划算是个常考的点，希望大家能够熟练掌握动态规划的各种模型和优化方法。

我整理的题单主要目标是尽可能囊括更多的基本模型和方法，而设计 DP 的技巧有很多，需要大家自己多多在练习中积累。如需按知识点刷题可以参照 此处 。标注 * 的是 20 道好欺负的题

标注 (x) 的是不是特别重要的部分，时间不够可以暂时搁置。

【前期 6.5】树上问题

树上差分

题目：P3128,P2680,P4216

LCA，倍增

https://www.luogu.com.cn/blog/TheDawn/qian-xi-lca

题目：P3379,P1967,P5024

DFS序：

题目：Bzoj3306,P3979,P1600,P4219,loj6276

树链剖分：

https://www.luogu.com.cn/blog/communist/shu-lian-pou-fen-yang-xie

题目：P2590,P4211,CF757G,P3178,P4315,P2146

题单：https://www.luogu.com.cn/training/1654
- P3128 [USACO15DEC]Max Flow P
- P2680 [NOIP2015 提高组] 运输计划
- P4216 [SCOI2015]情报传递
- P3379 【模板】最近公共祖先（LCA）
- P1967 [NOIP2013 提高组] 货车运输
- P5024 [NOIP2018 提高组] 保卫王国
- P3979 遥远的国度
- P1600 [NOIP2016 提高组] 天天爱跑步
- P4219 [BJOI2014]大融合
- P2590 [ZJOI2008]树的统计
- P4211 [LNOI2014]LCA
- CF757G Can Bash Save the Day?
- P3178 [HAOI2015]树上操作
- P4315 月下“毛景树”
- P2146 [NOI2015] 软件包管理器

学习，便是发现自己越来越菜的过程
最后更新于 2025-11-20