省选计划

dream_qwq · 2022-11-21 13:05:46 · 个人记录

【准备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

• P1821 [USACO07FEB] Cow Party S
• P1875 佳佳的魔法药水
• P2047 [NOI2007] 社交网络
• P1265 公路修建
• P1991 无线通讯网
• P2323 [HNOI2006]公路修建问题
• P4047 [JSOI2010]部落划分
• P3243 [HNOI2015]菜肴制作
• P1260 工程规划
• P3275 [SCOI2011]糖果
• P1993 小 K 的农场
• P4306 [JSOI2010]连通数
• P2403 [SDOI2010]所驼门王的宝藏
• P3225 [HNOI2012]矿场搭建
• P1129 [ZJOI2007] 矩阵游戏
• P1155 [NOIP2008 提高组] 双栈排序

【准备4】动态规划

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

• 状压DP：P2704、P3999 https://www.luogu.com.cn/blog/yijan/zhuang-ya-dp
• 数位DP：P2602 https://www.luogu.com.cn/blog/virus2017/shuweidp
• 区间DP：P1880、P3205
• 前缀和/差分优化：P1043、P1437
• 单调队列优化：P1725、P2034
• P2704 [NOI2001] 炮兵阵地
• P3999 [SHOI2013]二重镇
• P2602 [ZJOI2010]数字计数
• P1880 [NOI1995] 石子合并
• P3205 [HNOI2010]合唱队
• P1043 [NOIP2003 普及组] 数字游戏
• P1437 [HNOI2004]敲砖块
• P1725 琪露诺
• P2034 选择数字

【准备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 赛制自行进行模拟测试。

• P1119,P4588
• P4079,P4302,P5522,P1979,P5994,P3398,P3959
• P2048,P3264,P2272,BZOJ2238
• P1119 灾后重建
• P4588 [TJOI2018]数学计算
• P4079 [SDOI2016]齿轮
• P4302 [SCOI2003]字符串折叠
• P5522 [yLOI2019] 棠梨煎雪
• P5994 [PA2014]Kuglarz
• P3398 仓鼠找sugar
• P1979 [NOIP2013 提高组] 华容道
• P3959 [NOIP2017 提高组] 宝藏
• P2048 [NOI2010] 超级钢琴
• P3264 [JLOI2015]管道连接
• P2272 [ZJOI2007]最大半连通子图

【前期 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

• P2023 [AHOI2009] 维护序列
• P4513 小白逛公园
• P1471 方差
• P6327 区间加区间sin和
• P5482 [JLOI2011]不等式组
• P3792 由乃与大母神原型和偶像崇拜
• P5278 算术天才⑨与等差数列
• P6617 查找 Search
• P5069 [Ynoi2015] 纵使日薄西山
• P3747 [六省联考 2017] 相逢是问候
• P2042 [NOI2005] 维护数列
• P4036 [JSOI2008]火星人
• P3586 [POI2015]LOG
• P6105 [Ynoi2010] y-fast trie
• P5610 [Ynoi2013] 大学
• P5068 [Ynoi2015] 我回来了
• P5608 [Ynoi2013] 文化课
• P5066 [Ynoi2014] 人人本着正义之名
• P4097 [HEOI2013]Segment
• P4069 [SDOI2016]游戏
• P4198 楼房重建
• CF1340F Nastya and CBS
• P6781 [Ynoi2008] rupq
• CF896C Willem, Chtholly and Seniorious

【前期 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

• P3567 [POI2014]KUR-Couriers
• P2839 [国家集训队]middle
• P3402 可持久化并查集
• P3293 [SCOI2016]美味
• P4197 Peaks
• P4899 [IOI2018] werewolf 狼人
• P3302 [SDOI2013]森林
• P5055 【模板】可持久化文艺平衡树
• P5350 序列
• P5586 [P5350] 序列 (加强版)
• P3380 【模板】二逼平衡树（树套树）
• P4396 [AHOI2013]作业
• P3810 【模板】三维偏序（陌上花开）
• P4054 [JSOI2009]计数问题
• P3759 [TJOI2017]不勤劳的图书管理员
• P3157 [CQOI2011]动态逆序对
• P3332 [ZJOI2013]K大数查询
• P3242 [HNOI2015] 接水果
• P4690 [Ynoi2016] 镜中的昆虫
• P5445 [APIO2019]路灯
• P3688 [ZJOI2017] 树状数组

【前期 2】数学 1

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

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

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

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

• [x] 找规律！找规律！！一定要找规律！！！这很重要，看到题一定要先试试能不能找规律，不然，万一你推式子水平不够到位，还碰上了 NOIP 2018 D2T2，或是 NOI 2019 D2T2，你就会像我一样，爱上这款████的游戏
• [x] 数论
  • [x] 整除性
    • [x] 定义：整除、带余除法、gcd -[x] 裴蜀定理、欧几里得算法
      • [x] 扩展欧几里得算法 https://oi-wiki.org/math/gcd/
        • [x] 方程：ax + by = c
      • [ ] 类欧几里得 https://oi-wiki.org/math/euclidean/
• [x] 素数
  • [x] 定义：素数
  • [x] 算术基本定理
  • [x] 整除偏序的结构 自己写的一点东西，建议配合常见Möbius反演定理教程食用
    • [x] Möbius反演公式：zeta变换，Möbius变换，lcm卷积，gcd卷积 同上 https://oi-wiki.org/math/mobius/ https://www.luogu.com.cn/blog/lx-2003/mobius-inversion
  • [x] 埃氏筛法、欧拉筛法、求任意积性函数 1~n 处的值 https://oi-wiki.org/math/sieve/
  • [x] 整数分解：试除法、筛法预处理
• [x] 同余
  • [x] 线性同余方程组
    • [x] 线性同余方程 bx\equiv a\pmod n https://oi-wiki.org/math/linear-equation/
    • [x] 合并两个形如 x\equiv a\pmod nx≡a(modn) 的方程 链接同下，不知为何被人称为“exCRT”
    • [x] 中国剩余定理、直接构造解 https://oi-wiki.org/math/crt/
      • [x] 将 \bmod n 的问题分解为 \bmod p^k 的问题，然后合并
  • [x] Lucas定理 https://oi-wiki.org/math/lucas/
• [x] \mathbb{Z}/n\mathbb{Z}
  • [x] 费马小定理、欧拉定理 https://oi-wiki.org/math/fermat/
    • [ ] 素性测试：Miller-Rabin primality test https://oi-wiki.org/math/prime/
  • [x] 乘法逆元、O(n+\log p) 时间求 n 个数的乘法逆元 https://oi-wiki.org/math/inverse/
  • [x] 模 n 整数的乘法群 (\mathbb{Z}/n\mathbb{Z})^\times 、原根、指标 / 离散对数。
    • [x] 离散对数：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/
• [x] 计数组合学
  • [x] 基础 https://oi-wiki.org/math/combination/
  • [ ] 斯特林数 https://oi-wiki.org/math/stirling/
  • [x] 容斥 自己写的一点容斥原理简介 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/
• [x] 代数
  • [x] 多项式的一些基本概念（不，当然不是你想的那种多项式（这部分其实我非常想自己写介绍的（而且资料中还有点小问题……），但可能要过两天才能写完吧（明天又有一堆ddl，sigh
  • [x] 拉格朗日插值 https://oi-wiki.org/math/poly/lagrange/
  • [x] 多项式乘法、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 推导的一部分）
  • [x] 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 经常考）会用 粗体 标注。

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

数学部分

• 数论：
  • 数学 1 中所有内容（同余相关，同余方程，BSGS，中国剩余定理等，及数论函数，莫比乌斯反演等）。
  • 二次剩余，OI-wiki, rqy's blog。
  • 杜教筛 & 类似的其他筛法（洲阁筛，Min_25筛，etc） OI-wiki 杜教筛，OI-wiki Min_25 筛，rqy's blog 杜教筛, zzq's blog 一个奇怪的辅助方法
• 博弈论：
  • 无偏（公平）博弈，即 SG 函数相关 OI-wiki。
  • 还有很多千奇百怪的人类智慧题.jpg，或者目前 OI 根本没有涉及到的一些以 Surreal number 为基础的博弈。
• 多项式与 FFT 相关：
  • FFT、NTT 等 OI-wiki FFT OI-wiki NTT
  • 拉格朗日插值法 OI-wiki
  • 对上述插值的 O(n \log n)优化算法，即分治 FFT 的一种用法。OI-wiki
  • 利用倍增 FFT 的办法 O(n \log^2 n) n) 地计算多项式逆、对数指数甚至开方等。见 OI-wiki 多项式界面的若干子词条。很容易学，也可以用下面一条替代
  • 利用多项式牛顿迭代 O(n \log n) 求上面那些东西（除非你很会优化，否则大部分情况没有倍增 FFT 快。可以暂时不学。）OI-wiki
  • 拉格朗日反演 某blog
  • 多项式除法/取模 OI-wiki，用处相对较小。
  • 多项式多点求值。有难写且慢的分治取模算法 OI-wiki 和好写且跑得快的利用转置原理的算法 rqy's blog
  • 利用多项式做线性递推 OI-wiki。需要多项式取模。
  • 非正常模数的 FFT。Pick's blog。
• 生成函数相关：
  • 上次 数学 1 部分的所有内容。（目测上次没有找几道这方面的题目）
  • 在上述多项式操作（算法层面）之外的推式子层面的练习。
• 线性代数相关：
  • 基础（矩阵乘法，快速幂等）
  • 高斯消元 OI-wiki; 利用高斯消元解线性方程组、求行列式等。
  • 线性基 OI-wiki
• FMT；集合相关
  • FMT OI-wiki
  • 子集卷积 某blog
• 组合数学：
  • 数学 1 部分全部内容。
  • 容斥相关 OI-wiki, 包括二项式反演，min-max 容斥等。
  • 组合数、斯特林数等、基础的组合恒等式 OI-wiki 斯特林数， OI-wiki 组合数。
• 杂项：
  • 基础的概率论。这方面考的不多，很容易掌握。主要是概率、期望、方差，以及一些涉及到概率/期望的方程/dp问题。OI-wiki, rqy's blog
  • 置换群与 Burnside 引理 OI-wiki
  • 数值积分 OI-wiki
  • 线性规划 OI-wiki
  • Stern-Brocot 树 OI-wiki，有理数二分
• 计算几何部分
  • 基础内容 OI-wiki
  • 平面几何、向量、点积/叉积、正弦定理、余弦定理等
  • 线段/射线/直线相交判定，求交点；圆与直线交点、圆与圆交点等
  • 凸包、半平面交相关
  • 凸包 OI-wiki; riteme.site 的凸包相关 很详细，包含旋转卡壳/动态凸包相关。
  • 半平面交 OI-wiki
  • 判断点是否在凸包内/半平面交内 等
  • 旋转卡壳 某 Blog，以及上面 riteme.site 的内容
  • 凸包的闵可夫斯基和 某 Blog
  • 一些与数据结构有关的算法
  • 动态凸包 riteme.site 的凸包相关 （当然也有动态半平面交，似乎不太常用）
  • 杂项
  • 圆反演 OI-wiki 某 Blog
  • 平面最近点对 OI-wiki
  • 最小圆覆盖问题 OI-wiki
  • 三维凸包
• P5491 【模板】二次剩余
• P4213 【模板】杜教筛（Sum）
• P3768 简单的数学题
• SP20173 DIVCNT2 - Counting Divisors (square)
• P2197 【模板】nim游戏
• P1247 取火柴游戏
• P3803 【模板】多项式乘法（FFT）
• CF438E The Child and Binary Tree
• P4002 [清华集训2017]生成树计数
• P5828 边双连通图计数
• P4841 [集训队作业2013]城市规划
• P6295 有标号 DAG 计数
• P3824 [NOI2017] 泳池
• P3812 【模板】线性基
• P4301 [CQOI2013] 新Nim游戏
• P3389 【模板】高斯消元法
• P4111 [HEOI2015]小 Z 的房间
• P3211 [HNOI2011]XOR和路径
• P4717 【模板】快速莫比乌斯/沃尔什变换 (FMT/FWT)
• P6097 【模板】子集卷积
• P4221 [WC2018]州区划分
• CF914G Sum the Fibonacci
• P3175 [HAOI2015]按位或
• P4491 [HAOI2018]染色
• P1446 [HNOI2008]Cards
• P3307 [SDOI2013]项链
• P4207 [NOI2005] 月下柠檬树
• P2742 [USACO5.1]圈奶牛Fencing the Cows /【模板】二维凸包
• P3829 [SHOI2012]信用卡凸包
• P3194 [HNOI2008]水平可见直线
• P3187 [HNOI2007]最小矩形覆盖
• P6247 [SDOI2012]最近最远点对
• P4557 [JSOI2018]战争
• P2521 [HAOI2011]防线修建
• P1742 最小圆覆盖

【前期 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
• 最短路相关：
  • 差分约束系统 OI-wiki
  • 同余最短路 OI-wiki
• 杂项：
  • 欧拉(回)路 OI-wiki
  • 2-SAT 的判断和构造：Tarjan SCC 缩点 OI-wiki，或更详细的 日报#268
  • 全局最小割：Stoer Wagner 算法
  • 最小割树, (Gomory-Hu Tree)：日报#300
  • ## 网络流部分 这部分的一个优秀参考文献：《网络流的一些建模方法》 东营市胜利第一中学 姜志豪 （2016年候选队论文集）。

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

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

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

• 最大流 OI-wiki。推荐掌握 Dinic 算法，学有余力的同学可以把 ISAP 也学了。
  • 拆点。有时图中的点也有容量限制，此时需要把每个点拆成“入点”和“出点”。
  • 动态开点。用于优化一些特殊的题目，如 [SCOI2007] 修车
• 最小割 OI-wiki。最小割最大流定理。以及要会构造最小割方案。经典题目/模型：
  • 最大权闭合子图。一个很经典也很常见的模型。
  • 切糕 模型，这个名字来自 [HNOI2013] 切糕。也叫做离散变量模型。此模型的另外两个题目（洛谷上没有找到）：TopCoder12727，CodeChef-Rin: Course Selection←都是 Vjudge 链接
• 费用流 OI-wiki。需要掌握最简单的SSP算法（每次跑Dijkstra）；尽量掌握使用 Dijkstra 优化的“原始对偶”方法。图挂了的日报#41；日报#127：ISAP与HLPP（HLPP常数比较满，一般情况下跑不到 Dinic/ISAP 快。可以不学）
• 上下界网络流 OI-wiki。可以有也可以没有费用；可以求最大流也可以求可行流。都应该掌握。
• P3388 【模板】割点（割顶）
• P3387 【模板】缩点
• P3386 【模板】二分图最大匹配
• P6577 【模板】二分图最大权完美匹配
• P4716 【模板】最小树形图
• P6192 【模板】最小斯坦纳树
• P5180 【模板】支配树
• P6178 【模板】Matrix-Tree 定理
• P4782 【模板】2-SAT 问题
• P5632 【模板】Stoer-Wagner算法
• P4897 【模板】最小割树（Gomory-Hu Tree）
• P6113 【模板】一般图最大匹配
• P6699 【模板】一般图最大权匹配
• P3376 【模板】网络最大流
• P3381 【模板】最小费用最大流
• P3852 [TJOI2007]小朋友
• P3275 [SCOI2011]糖果
• P4294 [WC2008]游览计划
• P4202 [NOI2008] 奥运物流
• P4180 [BJWC2010]严格次小生成树
• P4768 [NOI2018] 归程
• CF888G Xor-MST
• P4298 [CTSC2008]祭祀
• P2860 [USACO06JAN]Redundant Paths G
• P4208 [JSOI2008]最小生成树计数
• P2371 [国家集训队]墨墨的等式
• P2483 【模板】k短路 / [SDOI2010]魔法猪学院
• P3825 [NOI2017] 游戏
• P3705 [SDOI2017]新生舞会
• P5361 [SDOI2019]热闹的聚会与尴尬的聚会
• P4606 [SDOI2018]战略游戏
• P4382 [八省联考2018]劈配
• P3254 圆桌问题
• P2762 太空飞行计划问题
• P4313 文理分科
• P3227 [HNOI2013]切糕
• P2469 [SDOI2010]星际竞速
• P2153 [SDOI2009]晨跑
• P2472 [SCOI2007]蜥蜴
• P1231 教辅的组成
• P3358 最长k可重区间集问题
• P2766 最长不下降子序列问题
• P2805 [NOI2009] 植物大战僵尸
• P3980 [NOI2008] 志愿者招募
• P2053 [SCOI2007]修车
• P4843 清理雪道
• P4043 [AHOI2014/JSOI2014]支线剧情

【前期 5】动态规划

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

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

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

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

• DP 结构
  • 序列 DP ： 常常是数列递推的形式。
  • 区间 DP ：以区间作为一个子问题，转移常常是枚举区间中的一个分界点划分为两个子区间。OI-wiki
  • 树形 DP ：在树的结构上 DP ，状态一般是一个子树对应的子问题。有时候需要用到相关的树上算法（如下面提到的长链剖分）优化。CSDN；OI-wiki
  • DAG DP ：在 DAG 的结构上 DP ，注意一些计数 DP 直接搬到 DAG 上可能算重（例如你可以线性求出每个点能到达的点的权值最值，却无法线性求出每个点能到达的点的权值和）。常常结合强连通分量缩点，或是在自动机上 DP。OI-wiki
  • 基环树 DP ：一般有两种处理方式。一种是枚举环上每条边断掉转换为树的情况；另一种是环上每个点的子树做 DP 然后在环上整理结果。CSDN
• DP 模型
  • 背包 DP ：十分常见，变种繁多。背包九讲；OI-wiki
  • 状压 DP ：最常见的状压 DP 是把 n 个布尔状态映射到一个 2^n 的二进制数上，这时常常可以结合其他方法优化（如集合幂级数）。其他的将排列等对象映射到一个自然数的方式也是状压。洛谷日报；牛客博客
  • 数位 DP ：用于处理一些可以在数位上依次考虑限制的记数问题。洛谷日报；洛谷日报
  • (x) 插头 DP /轮廓线 DP ：本质上是一类状压 DP ，通常是在二维矩形上逐行地状压列的情况（或反之）。洛谷日报
  • (x) DP 套 DP ：将内层 DP 的状态与值构成的二元组状压进行外层 DP 。博客园；博客园
• DP 优化
  • 状态优化：尽可能地减少状态大小，这是很重要的 DP 优化方向，冷静思考在状态中什么变量其实并不是必要的。
  • 斜率优化：转移可以描述为在给定若干点的二维平面上找到对应直线的最小截距，维护点集的凸包即可。周弈帆的博客；博客园
  • 数据结构优化：利用数据结构（单调栈，线段树等）维护已知 DP 值，在转移新 DP 值时通过数据结构快速查询。较为灵活多变。
  • 前缀和优化：通过维护 DP 值的前缀和（或前缀积，前缀最值等），做到在转移时快速查询，也可以归入数据结构优化（如果前缀和算数据结构的话）。博客园
  • (x) 凸优化：即 wqs 二分或带权二分。博客园；博客园
  • 决策单调性优化：（打表是发现决策单调的一个非常重要的途径！）洛谷博客
  • 决策栈二分：维护决策栈，转移时二分。CSDN
  • 决策点分治：逐层分治地进行 DP 值转移。洛谷博客
  • 四边形不等式：常用于部分最优化区间 DP 。OI-wiki
  • 矩阵快速幂优化：优化部分序列 DP （非线性 DP 可以状压），有时需用到 kk 进制快速幂。洛谷博客
  • (x) 常系数齐次线性递推：优化部分序列 DP （非线性 DP 可以状压）。虽然可以利用多项式科技做到很优秀的复杂度，不过绝大多数情况下是不需要的。洛谷日报；Kewth 的博客
  • (x) 幂级数优化：把 DP 的转移关系描述为幂级数之间的运算关系，然后通过已知的幂级数运算的加速算法优化 DP 转移。这个应该归类到生成函数了吧。博客园（求逆的例子）
  • bitset 优化：如果 DP 值仅有 01 （存在性 DP），并且转移是一排一排转移的，利用 bitset 可以优化状态和转移。常见于 01 背包。OI-wiki
  • 树形背包优化 ：特殊的树形背包有多种优化方式，其中最常见的是上下界优化。ouuan 的博客
  • (x) 长链剖分优化树形 DP ：优化状态和转移只关注深度的树形 DP 。博客园
• 其他技巧
  • 动态 DP 洛谷日报
  • 序列 DDP ：如果转移可以描述为矩阵乘法，用线段树维护矩阵乘积即可。
  • 树上 DDP ：通过树链剖分套线段树，lct ，全局平衡二叉树等方式维护矩阵乘积。
  • 换根 DP ：普通的树形 DP 适用于有根树，无根树的情况可以套用换根 DP 。洛谷日报
  • 滚动数组 ：常用于优化空间复杂度，并避免使用过高维度的数组。CSDN
  • 记忆化搜索 ：如果你搞不清 DP 状态要先枚举哪个后枚举哪个就硬搜吧。洛谷日报
• P1880 [NOI1995] 石子合并
• P3592 [POI2015]MYJ
• P1352 没有上司的舞会
• P4362 [NOI2002] 贪吃的九头龙
• P3554 [POI2013]LUK-Triumphal arch
• SP3734 PERIODNI - Periodni
• P6381 『MdOI R2』Odyssey
• P2272 [ZJOI2007]最大半连通子图
• P1453 城市环路
• P2081 [NOI2012] 迷失游乐园
• P1399 [NOI2013] 快餐店
• P4037 [JSOI2008]魔兽地图
• P4516 [JSOI2018]潜入行动
• P5853 [USACO19DEC]Tree Depth P
• P1777 帮助
• P5933 [清华集训2012]串珠子
• P6622 [省选联考 2020 A/B 卷] 信号传递
• P2602 [ZJOI2010]数字计数
• P4067 [SDOI2016]储能表
• CF908G New Year and Original Order
• P5074 Eat the Trees
• P3170 [CQOI2015]标识设计
• P4590 [TJOI2018]游园会
• P5664 [CSP-S2019] Emiya 家今天的饭
• P3195 [HNOI2008]玩具装箱
• P5468 [NOI2019] 回家路线
• AT2558 [ARC073D] Many Moves
• UVA12983 The Battle of Chibi
• P6383 『MdOI R2』Resurrection
• CF708E Student's Camp
• CF739E Gosha is hunting
• P5308 [COCI2019] Quiz
• P5244 [USACO19FEB] Mowing Mischief P
• CF868F Yet Another Minimization Problem
• P5504 [JSOI2011] 柠檬
• P3216 [HNOI2011]数学作业
• P3193 [HNOI2008]GT考试
• P6630 [ZJOI2020] 传统艺能
• P3824 [NOI2017] 泳池
• CF1096G Lucky Tickets
• P6775 [NOI2020] 制作菜品
• U53204 【数据加强版】选课
• U53878 【数据加强版】道路重建
• P3899 [湖南集训]谈笑风生
• P5904 [POI2014]HOT-Hotels 加强版
• CF1264C Beautiful Mirrors with queries
• P5024 [NOIP2018 提高组] 保卫王国
• P3647 [APIO2014]连珠线
• AT2268 [AGC008F] Black Radius

【前期 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] 软件包管理器