noip基础知识总结

· · 算法·理论

NOIP 知识总结

（以下都是我学习 oi 以来学过的知识，搭配标题快速找到你需要的一部分）

基础算法

贪心

这个没什么好说的，在很多题里面都要用到。

核心思想 ： 是通过当前每一步的最优策略来得到全局的最优策略。

tips ：

二分主要分两种：二分查找和二分答案。

二分查找

二分查找就是利用单调性在 log 时间内找到序列里一个数，应用比较广泛。

在联赛中一般为了省时间我们就用 stl 函数里的 lowerbound 和 upperbound 函数，一个是找大于等于的，另一个是找严格大于的，在使用的时候注意边界问题即可。 有特殊的手写二分也不是不行。

二分答案

前提：需要答案或你要求的东西有单调性

这个一般作为配合的考点使出，大部分都是贪心，dp，图论等。当答案不好直接确定或者 复杂度特别高的时候，就可以使用这种做法。

例题：P1314 [NOIP 2011 提高组] 聪明的质监员，P1462 通往奥格瑞玛的道路，P3957 [NOIP 2017 普及组] 跳房子。

模拟

这种题出现概率比较小，但是出出来就会有很多人骂的题

这种题要注意的就是处理细节，考虑方方面面，大家都会这种题，就看谁更细节了。

例题：P7075 [CSP-S 2020] 儒略日，P9754 [CSP-S 2023] 结构体，P3952 [NOIP 2017 提高组] 时间复杂度。

搜索

其实就是暴力，把每一种可能包含的情况都枚举出来计算答案，这个就不用讲了，主要讲一下优化暴力的几种方法：

线段树

这个东西太经典了，最万能的数据结构，原理就不讲了，介绍几点注意事项。

注意事项：

例题：SP1043 GSS - Can you answer these queries 系列，P7453 [THUSC 2017] 大魔法师。

分块

其实就是暴力，只是把暴力分成了几个块如果跨越块就可以 O(1) 加上，所以复杂度就是 \sqrt n 的。

莫队

把询问分块，每次尽量只拓展相近的点。可以调块长，来优化复杂度。（带修，回滚认为不会考 考了我也不会啊）

例题：P4477 [BJWC2018] 基础匹配算法练习题，神秘小题目，P4137 Rmq Problem / mex。

树链剖分

重链剖分

每次取子树最大的的儿子，然后连成很多条链，再标个号就可以用处理区间的方式来处理树上问题。

注意：

珂朵莉树

这个就是利用了区间推平的技巧，将相同的地方缩成一个点，这样就可以高效的完成修改操作，但是容易被卡，就搞很多长度为一但是相邻颜色不同 的区间就能使复杂度退化，修改就分区间即可。

例题：P5350 序列。

平衡树

就是让我们在 \log n 时间内完成查询前驱后继排名等操作。

Treap

最普通的平衡树，通过左旋加上随机化完成操作。

FHQ Treap

通过分裂和合并操作替代了普通 Treap 的旋转操作，不同的是它支持可持久化（Treap 的可持久化新建节点过多了）。

Splay

没学不知道，只知道核心是 Splay 操作，而且 spaly 次数越多时间越快。

WBIT

没学不知道，以后再补充。

例题

平衡树没写过多少题，但是感觉大部分都是作为一个辅助数据结构用来查前驱和后继的，而且就算是看出来了我也不一定能在考场上 一遍就写出来 FHQ Treap，所以例题不给了。

主席树

其实就是可持久化权值线段树，用来维护区间 k 大，还有一些其他的操作，但我不会，只写了模板。

例题

同平衡树。

其他

其他的复杂数据结构比如说什么树套树，可持久化数据结构，LCT 什么的考了我也不会，所以就不讲了。

总结

## 动态规划 动态规划是最重要的是状态设计和转移方程，但是基础的还是分几个板块，每种 $dp$ 的侧重点和技巧都不一样，考场上要注意设计 $dp$ 时注意后效性的问题，一般要把后效性的转为无后效性的 $dp$ 或者使用其他方法解决。~~根据lyb大佬的说法只要不知道的就当作状态去转移即可~~ ### 背包 $dp

01 背包

这个算是最基础的一款 dp，设计状态为容量还剩 j 的时候所获得的最大价值，一般就是酱紫： dp_j = \max (dp_j,dp_{j - w_i} + v_i) 复杂度 O(nV)。

分组背包/多重背包/完全背包

其实这些都是 01 背包的变种，将物品转化为一个一个的物品即可。

完全背包：将 01 背包枚举 j 的循环的过来即可。

分组背包：每组物品里只能选一个，我们对每一组进行背包即可。

多重背包：分解常用技巧为二进制拆分，把物品按照二的次方分成 \log 个物品，这样子就能组成他所能取到所有物品的形式，之后就按照 01 背包去解决即可。

树上背包

这个在树形 dp 时在讲。

例题：P1782 旅行商的背包，P1941 [NOIP 2014 提高组] 飞扬的小鸟，P2015 二叉苹果树。

区间 dp

这个东西最大程度上利用了 dp 的子问题的解合并成为大问题的解。这种问题的典型就是要你 dp 的区间一定不会大，因为区间 dp 的时间复杂度至少是 O(n^2) 的。一个区间的答案可以独立求出而且两个区间合并是在复杂度可以接受的单位内。

例题：P1005 [NOIP 2007 提高组] 矩阵取数游戏，P1063 [NOIP 2006 提高组] 能量项链，P4170 [CQOI2007] 涂色。

树形 dp

树形 dp 状态一般都为当前节点的最优解。先 dfs 遍历子树的所有最优解，然后向上传递给子树的父节点来转移，最终根节点的值即为所求的最优解.

树上背包

这样子的东西一般是存在依赖关系的物品，比如说只有选了这个东西才能选下一个东西。我们在每一个子树进行背包即可。

换根 dp

这种东西一般需要求出来以每个点为树根所求出的什么答案，在这个时候我们就可以用换根 dp，考虑每次从父亲遍历到儿子，父亲的其他儿子和儿子的儿子所做的贡献或者说造成的影响是不变的，所以我们就可以在利用一些其他的信息把在父亲节点上的答案转移到儿子节点上，但是这种题一般非常难。

例题：P3478 [POI 2008] STA-Station，P2015 二叉苹果树，P1272 重建道路。

状压 dp

这种题一般数据非常小，但是需要枚举的情况一般是 2^n 或者组合数级别的，这个时候就可以用状压 dp，把每个数是否选取或者是什么其他的状态，类似搜索中标记数组。这样子就可以很快的解决这个问题。

例题：P2150 [NOI2015] 寿司晚宴，P2704 [NOI2001] 炮兵阵地，P1896 [SCOI2005] 互不侵犯。

一般 dp

这种 dp 没有什么特别版的套路，有的只是你对 dp 状态设计的准确和转移的细节，这种题只需要看出来他是一个 dp，然后随便设计几个看起来比较对的状态然后随便猜一下转移式子，猜几个基本上就猜出来了。

例题：P4158 [SCOI2009] 粉刷匠，P1541 [NOIP 2010 提高组] 乌龟棋，P1115 最大子段和。

优化 dp

#### 例题：[P9871 [NOIP2023] 天天爱打卡](https://www.luogu.com.cn/problem/P9871)，[P1776 宝物筛选](https://www.luogu.com.cn/problem/P1776)，[P5665 [CSP-S 2019] 划分](https://www.luogu.com.cn/problem/P5665)。 ### 期望 $dp

放在数学里讲，要不然数学没其他东西我会的了。

总结

## 字符串 $CSP-S$ 以为不考了，结果 $T3$ 爆零了，吓哭了赶紧恶补。 ### 字符串哈希 你如果比较厉害就手写几个 $hash$ 函数比较，实在不行就用 $std::map$ 算了。 #### 例题：这个没啥好写的。。。我也没做过几个这种题。。。。 ### $KMP$ 函数 这个东西不考 $KMP$，考的其实是他的本质就是他的 $next$ 数组，即前缀函数。这个东西在学习后比较简单，但是考法多种多样，要多刷题积累经验。 #### 例题：[P3435 [POI 2006] OKR-Periods of Words](https://www.luogu.com.cn/problem/P3435)，[P4391 [BalticOI 2009] Radio Transmission 无线传输](https://www.luogu.com.cn/problem/P4391)。 ### $Trie

字典树还是比较好用的，可以很快地查询前缀信息和前缀的出现次数之类的东西，而且可以用 01Trie 实现一些二进制上的操作比如异或，代码实现也比较简单。

例题：P4551 最长异或路径，P10470 前缀统计。

其他

### 总结 字符串考的简单了就只有一点，考的很难也可以用基础知识拿一点暴力分。在字符串题上不要消耗太多时间，免得影响其他题目的进度。还有一点就是要注意题目中的各种字符都要分清楚，不要看漏数字的字符。 ## 图论 图论的东西我还有好多没学过，就将一些基础的吧。 ### 最短路 顾名思义：求的是一个点到其他所需要经过的最短距离，在其中还可以加入其它复杂的机制，比如说可以瞬移之类的。目前有三种最通用的办法： #### $SPFA

关于 SPFA， 他死了，虽然在一般图里不推荐用，但是跑负权图的时候还是很快的，实在不行可以用 Bellman Ford。

dij

#### $Floyd #### 例题：[P1462 通往奥格瑞玛的道路](https://www.luogu.com.cn/problem/P1462)，[P5905 【模板】全源最短路（Johnson）](https://www.luogu.com.cn/problem/P5905)，[P2661 [NOIP 2015 提高组] 信息传递](https://www.luogu.com.cn/problem/P2661)。 ### 最小生成树 求图上维持所有点联通所需要的最小边权和。 #### $Prim$ 算法 考虑和 $dij$ 一样的松弛思路，维护一个点到所有点的最小距离，最后全加起来即可。 #### $Kruscal

考虑最小的边肯定要被选上，这是我们依次添加最小的边，若添加到的边是树变成了一个环，就跳过这条边。这个样子可以保存下来生成的最小生成树，从而对生成树进行操作。

例题：P14362 [CSP-S 2025] 道路修复，P1967 [NOIP 2013 提高组] 货车运输，P1265 公路修建。

拓扑排序

这是一种最简单的判断环方法，而且也是很多题目必须的一步转换，这个东西的 trick 有很多，比如说最长路，最小完成时间，图上 dp，之类的东西。

例题：P1038 [NOIP 2003 提高组] 神经网络，P1983 [NOIP 2013 普及组] 车站分级，P4316 绿豆蛙的归宿。

树上问题

树的直径

这个一般起辅助作用，只需知道模板怎么写即可。

LCA

这个在树上运用非常广泛，求他的主要方法有四种。

差分约束

其实这个是典型的图论建模题目，把大小关系的条件转化成最短路的式子，然后就能求出来不等式组的一组解。

例题：P5960 【模板】差分约束，P7624 [AHOI2021初中组] 地铁。

分层图

这种问题一般是图上问题但是你有一些操作可以修改边权来找最短路，我们可以对于每个点对于新修改的边权再建一条边，每层图的与上一层图都是边权转化的关系，就是怎么操作的就怎么连边，最后再在建出来的新图上跑一边最短路即可。

例题：P4822 [BJWC2012] 冻结，P4568 [JLOI2011] 飞行路线，P9370 [APIO2023] 赛博乐园 / cyberland。

其他

边双，点双，强连通分量，缩点啥的我也不会，只能期望他不考了。

总结

图论最难的就是图论建模，如果他要是考一般图论那到还好，其他的把图论问题建模建出来就行了。

数学

数学还是太难了，根本不会。。。

位运算

这个东西一般结合着状压 dp，单考位运算的很少，但也不是没有。位运算一般就是把单独一位拆出来或者是把一对数一起修改。当然，用在 bitset 里也是很好用的。

例题：P7076 [CSP-S 2020] 动物园，P5657 [CSP-S 2019] 格雷码。

概率与期望（期望 dp）

期望就是概率乘上权值，虽然这句话很简单但是实际上是很难的。

期望 dp，大部分都是设计当前事件点的期望是什么然后根据上一个点的期望值累加或者相乘得到的答案，重点还是要把转移式子推出来。

例题：P1850 [NOIP 2016 提高组] 换教室，P2473 [SCOI2008] 奖励关，P4206 [NOI2005] 聪聪与可可。

组合数学

这个一般搭配乘法原理和加法原理在计数题上使用，但是一般我只会暴力。

例题：P2822 [NOIP 2016 提高组] 组合数问题（其他的计数题一般都在模拟里考过了，故不放太多）。

其他

其他的太难了，基本上都是省选才考了，就不总结了。注意快速幂求逆元等基本操作要熟练。

总结

数论在 NOIP 考的一般都比较简单，但是也不可轻视，考的难了也要写暴力。

考场策略

总之，只要正常发挥，成绩就一定不会差到哪里去，祝 NOIP RP++！！！