专栏文章
noip基础知识总结
算法·理论参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性，并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @min0gdtb
- 此快照首次捕获于
- 2025/12/01 18:32 3 个月前
- 此快照最后确认于
- 2025/12/01 18:32 3 个月前
NOIP 知识总结
（以下都是我学习 以来学过的知识，搭配标题快速找到你需要的一部分）
基础算法
贪心
这个没什么好说的，在很多题里面都要用到。
核心思想 ： 是通过当前每一步的最优策略来得到全局的最优策略。
：
- 能贪心的题一般都需要证明贪心策略正确，一般在考场上能猜到结论感性理解正确即可，不需要浪费太多时间。 （ 考的贪心一般是第一题或第二题，结论较为明显）
- 有些题可能不能贪心，但是似乎贪心算法非常对，这时候就可以用反悔贪心（后面讲）去解决。
- 多个约束条件加在一起的贪心大部分都是用排序解决的，这时候就要考虑相邻两个数的排序条件是什么，然后就贪心取最优解即可。
- 贪心的实现一般与基本数据结构结合，比如说双端队列，优先队列，栈之类的，基本数据结构的掌握要熟练。
例题：P14361 [CSP-S 2025] 社团招新 , P7078 [CSP-S 2020] 贪吃蛇,P2827 [NOIP 2016 提高组] 蚯蚓 。
P14361 [CSP-S 2025] 社团招新二分
前提：序列有单调性。
二分主要分两种：二分查找和二分答案。
二分查找
二分查找就是利用单调性在 时间内找到序列里一个数，应用比较广泛。
在联赛中一般为了省时间我们就用 函数里的 和 函数，一个是找大于等于的，另一个是找严格大于的，在使用的时候注意边界问题即可。
有特殊的手写二分也不是不行。
二分答案
前提：需要答案或你要求的东西有单调性
这个一般作为配合的考点使出，大部分都是贪心，，图论等。当答案不好直接确定或者
复杂度特别高的时候，就可以使用这种做法。
例题：P1314 [NOIP 2011 提高组] 聪明的质监员，P1462 通往奥格瑞玛的道路，P3957 [NOIP 2017 普及组] 跳房子。
模拟
这种题出现概率比较小，但是出出来就会有很多人骂的题
这种题要注意的就是处理细节，考虑方方面面，大家都会这种题，就看谁更细节了。
例题：P7075 [CSP-S 2020] 儒略日，P9754 [CSP-S 2023] 结构体，P3952 [NOIP 2017 提高组] 时间复杂度。
搜索
其实就是暴力，把每一种可能包含的情况都枚举出来计算答案，这个就不用讲了，主要讲一下优化暴力的几种方法：
- 剪枝。比如说在最小值问题中，如果当前计算的答案已经比之前计算出来的答案要大，就可以直接返回。所以，我们可以在保证正确的前提下，把一定没有正确答案的分支去掉，可以省去大把时间。
- 标记。这个就是说你要把你搜过的状态记下来，在第二次搜到的之后就可以直接返回。这个可以进一步优化为记忆化搜索，基本上就是多项式复杂度了。
例题。
这个就不放例题了，随便找一道紫题黑题把部分分写出来就可以了，这个是重要的，毕竟 有很多部分分的。我也就只能拿这个分了。
分治
就是将原本一个大区间的问题转化为一个个小区间，然后将每个小区间的在合并回去，学会了归并排序大概就会这个了。一般是二分，可能某些题目需要更为优秀的分治方法。
例题：（本人刷题太少）。
总结
基础算法是其他算法的前提，这些要落实好，把联赛中的基础分都要拿好。
数据结构
并查集
按秩合并 + 路径压缩还是太快了，用于快速查询两个点是否在一个连通块内，有时候需要带权，就在路径压缩时注意一下就行了，还可以维护类似“敌人的敌人是朋友”，这个叫拓展域并查集。
例题：P1525 [NOIP 2010 提高组] 关押罪犯，P2024 [NOI2001] 食物链，P9869 [NOIP2023] 三值逻辑。
表
这个东西一般就是为了静态 ，小常数快速求解，但是线段树能仅在多一点好常数的情况下完成，故不作讲解。
树状数组
树状数组本质上是要利用数的二进制特征实现的一种支持 修改和查询的数据结构，他常数小，
好写，但是有一个致命的问题就是只能维护可逆的操作比如区间和区间异或和之类的。
权值树状数组
这个可能听名字比较生疏，但是其实他是实现逆序对的一种常见方式，后面 也需要用到。
主要思想就是以值域为树状数组下标，就能快速维护出有多少个数小于他，便于维护逆序对之类问题。
例题 P1908 逆序对，P10814 【模板】离线二维数点，P3368 【模板】树状数组 2。
线段树
这个东西太经典了，最万能的数据结构，原理就不讲了，介绍几点注意事项。
注意事项：
- 注意线段树的四倍常数在一般情况下可能没有什么不好的，但是如果遇见时间卡的比较紧的题， 如果能用比较快一点的比如说上面介绍的这几个东西见小常熟也是挺好的。
- 注意线段树能维护的信息虽然很多，但是他只能维护满足结合律的信息，即满足 （ 代表一种运算）的东西才能用线段树维护。 如果不满足结合律的话就可以考虑分块或者是转换操作使其变成满足结合律的。
- 在线段树操作的时候，注意宏定义函数尽量少用在递归上，要不然复杂度会退化为 。（本人天天爱打卡因为这个虚空调试两小时）
- 数组开四倍空间，初始化一定要对！！！
例题：SP1043 GSS - Can you answer these queries 系列，P7453 [THUSC 2017] 大魔法师。
分块
其实就是暴力，只是把暴力分成了几个块如果跨越块就可以 加上，所以复杂度就是 的。
莫队
把询问分块，每次尽量只拓展相近的点。可以调块长，来优化复杂度。（带修，回滚认为不会考 考了我也不会啊）
例题：P4477 [BJWC2018] 基础匹配算法练习题，神秘小题目，P4137 Rmq Problem / mex。
树链剖分
重链剖分
每次取子树最大的的儿子，然后连成很多条链，再标个号就可以用处理区间的方式来处理树上问题。
注意：
- 当权值在边上的时候，要注意最后在路径上 是要根据你把边权挂在边的上面一个点还是下面的，要不然会将一条边的权加两遍。
- 如果要处理子树问题，假设一个点的编号为 ，他在重剖之后的编号设为 ，而他子树内的点的最大编号是 ，因为根据遍历顺序，
你在一个点的子树内，编号一定在排序后是连续的（
我在说什么）。所以就可以直接改这个区间内的。 - 考虑树上异或和，可以先把每个顶点到根的异或和，每次异或的时候就是把两个异或和异或一下，因为异或之后值不变，可以用此优化复杂度。
长链剖分
没有学，但是听说在某些问题上比重剖快，其核心思想是每次选取该节点的所有儿子中子树最深的儿子剖。
例题 P2486 [SDOI2011] 染色，P2680 [NOIP 2015 提高组] 运输计划，P3384 【模板】重链剖分 / 树链剖分。
珂朵莉树
这个就是利用了区间推平的技巧，将相同的地方缩成一个点，这样就可以高效的完成修改操作，但是容易被卡，就搞很多长度为一但是相邻颜色不同
的区间就能使复杂度退化，修改就分区间即可。
例题：P5350 序列。
平衡树
就是让我们在 时间内完成查询前驱后继排名等操作。
最普通的平衡树，通过左旋加上随机化完成操作。
通过分裂和合并操作替代了普通 的旋转操作，不同的是它支持可持久化（ 的可持久化新建节点过多了）。
没学不知道，只知道核心是 操作，而且 次数越多时间越快。
没学不知道，以后再补充。
例题
平衡树没写过多少题，但是感觉大部分都是作为一个辅助数据结构用来查前驱和后继的，而且就算是看出来了我也不一定能在考场上
一遍就写出来 ，所以例题不给了。
主席树
其实就是可持久化权值线段树，用来维护区间 大，还有一些其他的操作，但我不会，只写了模板。
例题
同平衡树。
其他
其他的复杂数据结构比如说什么树套树，可持久化数据结构， 什么的考了我也不会，所以就不讲了。
总结
题考的主要就是你对数据的处理和对题目的转化，把题目真正想让你干什么搞出来就行了。
动态规划
动态规划是最重要的是状态设计和转移方程，但是基础的还是分几个板块，每种 的侧重点和技巧都不一样，考场上要注意设计 时注意后效性的问题，一般要把后效性的转为无后效性的 或者使用其他方法解决。根据lyb大佬的说法只要不知道的就当作状态去转移即可
背包
背包
这个算是最基础的一款 ，设计状态为容量还剩 的时候所获得的最大价值，一般就是酱紫：
复杂度 。
分组背包/多重背包/完全背包
其实这些都是 背包的变种，将物品转化为一个一个的物品即可。
完全背包：将 背包枚举 的循环的过来即可。
分组背包：每组物品里只能选一个，我们对每一组进行背包即可。
多重背包：分解常用技巧为二进制拆分，把物品按照二的次方分成 个物品，这样子就能组成他所能取到所有物品的形式，之后就按照 背包去解决即可。
树上背包
这个在树形 时在讲。
例题：P1782 旅行商的背包，P1941 [NOIP 2014 提高组] 飞扬的小鸟，P2015 二叉苹果树。
区间
这个东西最大程度上利用了 的子问题的解合并成为大问题的解。这种问题的典型就是要你 的区间一定不会大，因为区间 的时间复杂度至少是 的。一个区间的答案可以独立求出而且两个区间合并是在复杂度可以接受的单位内。
例题：P1005 [NOIP 2007 提高组] 矩阵取数游戏，P1063 [NOIP 2006 提高组] 能量项链，P4170 [CQOI2007] 涂色。
树形
树形 状态一般都为当前节点的最优解。先 遍历子树的所有最优解，然后向上传递给子树的父节点来转移，最终根节点的值即为所求的最优解.
树上背包
这样子的东西一般是存在依赖关系的物品，比如说只有选了这个东西才能选下一个东西。我们在每一个子树进行背包即可。
换根
这种东西一般需要求出来以每个点为树根所求出的什么答案，在这个时候我们就可以用换根 ，考虑每次从父亲遍历到儿子，父亲的其他儿子和儿子的儿子所做的贡献或者说造成的影响是不变的，所以我们就可以在利用一些其他的信息把在父亲节点上的答案转移到儿子节点上，但是这种题一般非常难。
例题：P3478 [POI 2008] STA-Station，P2015 二叉苹果树，P1272 重建道路。
状压
这种题一般数据非常小，但是需要枚举的情况一般是 或者组合数级别的，这个时候就可以用状压 ，把每个数是否选取或者是什么其他的状态，类似搜索中标记数组。这样子就可以很快的解决这个问题。
例题：P2150 [NOI2015] 寿司晚宴，P2704 [NOI2001] 炮兵阵地，P1896 [SCOI2005] 互不侵犯。
一般
这种 没有什么特别版的套路，有的只是你对 状态设计的准确和转移的细节，这种题只需要看出来他是一个 ，然后随便设计几个看起来比较对的状态然后随便猜一下转移式子，猜几个基本上就猜出来了。
例题：P4158 [SCOI2009] 粉刷匠，P1541 [NOIP 2010 提高组] 乌龟棋，P1115 最大子段和。
优化
有时候因为其特殊的性质可以被某些数据结构优化，比如说单调队列，线段树等等，这种题一般部分分给的很多，最后的优化一般很难想，而且有些复杂的比如说什么倍增，斜率优化等等我也没学，可能是我太菜了吧。所以还是要打好暴力哟。
例题：P9871 [NOIP2023] 天天爱打卡，P1776 宝物筛选，P5665 [CSP-S 2019] 划分。
期望
放在数学里讲，要不然数学没其他东西我会的了。
总结
还是太好用了，上可代码极短切掉一题，下可复杂题目简单暴力，所以 还是要好好练一下的，可惜我连的还不够。
字符串
以为不考了，结果 爆零了，吓哭了赶紧恶补。
字符串哈希
你如果比较厉害就手写几个 函数比较，实在不行就用 算了。
例题：这个没啥好写的。。。我也没做过几个这种题。。。。
函数
这个东西不考 ，考的其实是他的本质就是他的 数组，即前缀函数。这个东西在学习后比较简单，但是考法多种多样，要多刷题积累经验。
例题：P3435 [POI 2006] OKR-Periods of Words，P4391 [BalticOI 2009] Radio Transmission 无线传输。
字典树还是比较好用的，可以很快地查询前缀信息和前缀的出现次数之类的东西，而且可以用 实现一些二进制上的操作比如异或，代码实现也比较简单。
例题：P4551 最长异或路径，P10470 前缀统计。
其他
， 自动机啥的我也没学，只学了基础算法，等寒假集训再来补吧。
总结
字符串考的简单了就只有一点，考的很难也可以用基础知识拿一点暴力分。在字符串题上不要消耗太多时间，免得影响其他题目的进度。还有一点就是要注意题目中的各种字符都要分清楚，不要看漏数字的字符。
图论
图论的东西我还有好多没学过，就将一些基础的吧。
最短路
顾名思义：求的是一个点到其他所需要经过的最短距离，在其中还可以加入其它复杂的机制，比如说可以瞬移之类的。目前有三种最通用的办法：
关于 ， 他死了，虽然在一般图里不推荐用，但是跑负权图的时候还是很快的，实在不行可以用 。
，是目前用的最多了的了，除了不能有负权边，其他的都很高效。
唯一的缺点就是复杂度过高，但是他能处理多元最短路，在点数较小的时候还是可以用的
例题：P1462 通往奥格瑞玛的道路，P5905 【模板】全源最短路（Johnson），P2661 [NOIP 2015 提高组] 信息传递。
最小生成树
求图上维持所有点联通所需要的最小边权和。
算法
考虑和 一样的松弛思路，维护一个点到所有点的最小距离，最后全加起来即可。
考虑最小的边肯定要被选上，这是我们依次添加最小的边，若添加到的边是树变成了一个环，就跳过这条边。这个样子可以保存下来生成的最小生成树，从而对生成树进行操作。
例题：P14362 [CSP-S 2025] 道路修复，P1967 [NOIP 2013 提高组] 货车运输，P1265 公路修建。
拓扑排序
这是一种最简单的判断环方法，而且也是很多题目必须的一步转换，这个东西的 有很多，比如说最长路，最小完成时间，图上 ，之类的东西。
例题：P1038 [NOIP 2003 提高组] 神经网络，P1983 [NOIP 2013 普及组] 车站分级，P4316 绿豆蛙的归宿。
树上问题
树的直径
这个一般起辅助作用，只需知道模板怎么写即可。
这个在树上运用非常广泛，求他的主要方法有四种。
- 倍增：好写好理解，常数比较大。
- 树剖：常数小，比较快。
- Tarjan：特别快，但是是离线的。
- 各种遍历顺序： 序，欧拉序，等等
- 其他的什么算法。 没啥好讲的，一般作为树上操作的快速跳节点使用。
例题：P3379 【模板】最近公共祖先（LCA），P1099 [NOIP 2007 提高组] 树网的核，P11364 [NOIP2024] 树上查询。
差分约束
其实这个是典型的图论建模题目，把大小关系的条件转化成最短路的式子，然后就能求出来不等式组的一组解。
例题：P5960 【模板】差分约束，P7624 [AHOI2021初中组] 地铁。
分层图
这种问题一般是图上问题但是你有一些操作可以修改边权来找最短路，我们可以对于每个点对于新修改的边权再建一条边，每层图的与上一层图都是边权转化的关系，就是怎么操作的就怎么连边，最后再在建出来的新图上跑一边最短路即可。
例题：P4822 [BJWC2012] 冻结，P4568 [JLOI2011] 飞行路线，P9370 [APIO2023] 赛博乐园 / cyberland。
其他
边双，点双，强连通分量，缩点啥的我也不会，只能期望他不考了。
总结
图论最难的就是图论建模，如果他要是考一般图论那到还好，其他的把图论问题建模建出来就行了。
数学
数学还是太难了，根本不会。。。
位运算
这个东西一般结合着状压 ，单考位运算的很少，但也不是没有。位运算一般就是把单独一位拆出来或者是把一对数一起修改。当然，用在 里也是很好用的。
例题：P7076 [CSP-S 2020] 动物园，P5657 [CSP-S 2019] 格雷码。
概率与期望（期望 ）
期望就是概率乘上权值，虽然这句话很简单但是实际上是很难的。
期望 ，大部分都是设计当前事件点的期望是什么然后根据上一个点的期望值累加或者相乘得到的答案，重点还是要把转移式子推出来。
例题：P1850 [NOIP 2016 提高组] 换教室，P2473 [SCOI2008] 奖励关，P4206 [NOI2005] 聪聪与可可。
组合数学
这个一般搭配乘法原理和加法原理在计数题上使用，但是一般我只会暴力。
例题：P2822 [NOIP 2016 提高组] 组合数问题（其他的计数题一般都在模拟里考过了，故不放太多）。
其他
其他的太难了，基本上都是省选才考了，就不总结了。注意快速幂求逆元等基本操作要熟练。
总结
数论在 考的一般都比较简单，但是也不可轻视，考的难了也要写暴力。
考场策略
- 能写就写，写不出就写暴力。
- 心态要好，做不出第一题就先写暴力，所有题目先写暴力。
- 想不出就去上个厕所，做不出可以吃块巧克力。
- 写出来题了了不要骄傲，多检查一下，冷静下来写其他题。
总之，只要正常发挥，成绩就一定不会差到哪里去，祝 RP++！！！
相关推荐
评论
共 0 条评论，欢迎与作者交流。
正在加载评论...