NOIP 赛前总结
Robbyprogramming
·
·
个人记录
NOIP 赛前总结
by Robbyprogramming
作为一个水平不高的 OIER ，赛前做做总结吧。
知识总结
学到了什么
| 内容 |
日期 |
c++ 语言基础 |
6/25~7/1 |
| Sort / std::sort |
7/2 |
| Binary\ Search |
7/8 |
| 栈和队列 |
7/9 |
| 递归 |
7/14 |
| 搜索 DFS & BFS |
7/16 |
| Merge\ Sort |
7/18 |
| Heap / std::priority\_queue |
7/22 |
| 单调栈，单调队列 |
8/12 |
| Sparse\ Table |
8/16 |
| 分块 |
8/16 |
| 线性 Dynamic\ Programming |
8/18 |
| 序列 DP，区间 DP |
8/19 |
| 背包 DP |
8/21 |
| Binary\ Indexed\ Tree |
8/21 |
| Segment\ tree |
8/26 |
| Kruskal，Prim |
8/27 |
| Dijkstra |
8/27 |
| Topo\ Sort |
9/23 |
| Lowest\ Common\ Ancestor |
10/3 |
| 数学基础 |
10/9 |
| 字符串 Hash |
10/11 |
| KMP |
10/11 |
| Trie |
10/11 |
| 概率与期望 |
10/16 |
基本学完 NOIP 的重要考点，并通过一系列题目得以落实。
训练的其余时间进行了大量模拟赛，练习时间还算可以。抓的很紧。
赛时策略
比赛的策略很重要。这里以 CSP-S\ 2025 的惨痛教训制定以下策略：
1.仍然先写暴力做法，但花在每一题暴力做法上的时间不可超过 30 分钟。
2.写完暴力再写部分分，不追求正解，但简单题（有时的第一题贪心）可以尝试推出最优解。
3.剩下的时间拿来测试，检查，优化。
考试注意事项
1.分析与过程要再纸上进行推导，读完题目立刻拿笔抄写样例，将精力从屏幕上转移到纸面上，专注于分析本身。
2.写代码是想到就写，调试立马动手，多尝试比只看屏幕不敲代码的代价要低得多。
3.不要瞎探索电脑，出了问题会影响考试心态。
考前准备
1.考前一天晚上 10 点之前睡觉。
2.心无杂念，心平气和，安心，开心。
3.把之前的所有模板敲一遍，写一写 NOIP 以前题目的暴力做法。
4.自信！！！！！！！，NOIP 没有那么难得高分！
学术总结
基础算法
1.贪心
第一题经常就是贪心。这样的策略是很好的，可用于最优解或者假算法偏分。
对于贪心是期望拿到分的。看到简单题就往贪心上去想一想，多手玩，拿纸拿笔。
2.排序
对于和序列位置没有影响，或者可以通过记录序列位置变换问题的，sort 一下说不定有意想不到的结果。
通常和贪心思想一起用。
3.二分
二分搜索
对于有单调性的东西要在序列中查找，二分搜索是 O(n) 变 O(\log n) 的利器。
二分答案
和贪心一样很重要的一个好用的算法。
对于答案有单调性的问题，可以转换为二分搜索答案进行 check 答案可行性的问题。
通常来说，最小值最大和最大值最小都常用这样的方式求解。
4.搜索&枚举
写暴力啊！
见到题目就可以打搜索，或者暴力枚举，得部分分。
#### 5.快速幂
数学天天用，无论是数学题还是组合数求逆。
代码很简单，这怎么能不背下来呢。
### $DP
极为重要的算法和思想。不仅可以将问题转化为分步的最优子问题递推，还在各大更牛的算法有很多很多应用，如倍增，DAG最长路 等。
我的 DP 学的并不好，仅仅会最基础的状态设计和转移。
分很多种，不过总结来说都是那样。
题目可用 $DP$ 的条件：重叠子问题，最优子状态，无后效性。
步骤：设计状态，推出转移，初始化递推起点，求得答案。
$DP$ 的经验看个人积累，所以我就不说了，毕竟造诣不深。
### 数据结构
#### 并查集
很简单的数据结构，再很多算法中都有应用。比如 $Kruskal$。
就是一个用树结构维护的集合，可以做到 $O(\alpha(n))$ 的复杂度查询两个元素是否在同一集合内。非常优秀的算法。
```cpp
int find(int x){return dsu[x]==x?x:dsu[x]=find(dsu[x]);}
```
#### 树状数组
区间上的单点修改和区间查询操作可用其维护，也可扩展为区间修改与单点查询。巧妙地运用了 $lowbit$ 函数。
```cpp
int lowbit(int x){return x&(-x);}
```
#### 线段树
我最喜欢的数据结构。
应用及其广泛。可以对区间修改区间查询高效 $O(\log n)$ 维护。只需要满足结合律。
线段树是真的建了一棵树。节点上存储了需要记录的信息，理解起来其实不难。
#### $ST$ 表
特殊的，对于 $RMQ$ 问题，即区间最值问题（可推广到任何重叠区间不影响答案的问题），做到了 $O(1)$ 查询 $O(n\log n)$ 初始化。用了倍增及 $DP$ 思想。巧妙的利用了重叠区间不影响答案的性质。
```cpp
dp[i][k]=min(dp[i][k-1],dp[i+(1<<(k-1))][k-1]);
```
#### 分块
任意的带修区间性问题都可以用分块相对高效地解决。标记 $\sqrt n$ 一个 $\sqrt n$ 大小的 $tag$ ，每次查询时分别处理左边溢出的，中间 $tag$ 里的，和右边溢出的。复杂度 $O(n\sqrt n)$。
### 字符串
#### $KMP
字符串匹配经典算法。理解很爽，代码很短，细节很多。
next[i]表示前缀与后缀相同的最大长度。
令 n 为原串长度，m 为匹配串长度，可以 O(m) 构造 next 数组，
在 O(n) 的时间内完成匹配。
字符串哈希
大可以用 std::unordered\_map 代替。
图论
图论是算法竞赛中的重要部分。
最小生成树（Minimum\ Spanning\ Tree, MST）
用于在加权连通图中找到一棵生成树，使得所有边的权重之和最小。
Kruskal
基于贪心算法，将边按权重从小到大排序，依次选择边，若加入后不形成环（用并查集检查），则加入生成树。适用于稀疏图（边少）。用邻接矩阵。
##### $Prim
基于贪心算法，从任意顶点开始，维护一个已选集合，每次选择连接已选集和未选集的最小权重边。适用于稠密图（边多）。用邻接表。
使用优先队列（最小堆）时，O(E \log V)。一般不用堆优化。O(V^2)。
最短路（Shortest\ Path）
用于求图中两点间的最短路径权重。
堆优化 Dijsktra
贪心算法，适用于非负权图。使用优先队列不断扩展当前最短路径的顶点。不能处理负权。
##### $Floyd
动态规划，求所有点对的最短路径。通过中间点更新距离矩阵，可处理负权，但不能有负环。
$Kruskal$ 和 $Prim$ 选择取决于图密度，$Dijkstra$ 用于丹源非负权最短路，$Floyd$ 适合全源最短路径。
#### 拓扑排序（$Topological\ Sort$）
拓扑排序是针对有向无环图（$DAG$）的顶点进行线性排序，使得对于任何有向边 $u→v$，$u$ 在排序中都出现在 $v$ 之前。
基于 $BFS$（$Kahn$ 算法）或 $DFS$ 实现，本质是不断移除入度为 $0$ 的顶点。
**只能应用于有向无环图（$DAG$），有环图无法进行拓扑排序。**
$O(V + E)$。
可结合 $DP$ 实现求 $DAG$ 上最长路。
## 总结
> 蓦然回首，往事并不如烟。
NOIP RP++。