专栏文章

NOIP 赛前总结

RRobbyprogramming
个人记录参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mimzy9w0
此快照首次捕获于
2025/12/01 18:18
3 个月前
此快照最后确认于
2025/12/01 18:18
3 个月前
查看原文

NOIPNOIP 赛前总结

by Robbyprogramming
作为一个水平不高的 OIEROIER ，赛前做做总结吧。

知识总结

学到了什么

内容日期
c++ 语言基础6/25~7/1
SortSort / std::sortstd::sort7/2
Binary SearchBinary\ Search7/8
栈和队列7/9
递归7/14
搜索 DFSDFS & BFSBFS7/16
Merge SortMerge\ Sort7/18
HeapHeap / std::priority_queuestd::priority\_queue7/22
单调栈，单调队列8/12
Sparse TableSparse\ Table8/16
分块8/16
线性 Dynamic ProgrammingDynamic\ Programming8/18
序列 DPDP，区间 DPDP8/19
背包 DPDP8/21
Binary Indexed TreeBinary\ Indexed\ Tree8/21
Segment treeSegment\ tree8/26
KruskalKruskal，PrimPrim8/27
DijkstraDijkstra8/27
Topo SortTopo\ Sort9/23
Lowest Common AncestorLowest\ Common\ Ancestor10/3
数学基础10/9
字符串 HashHash10/11
KMPKMP10/11
TrieTrie10/11
概率与期望10/16
基本学完 NOIPNOIP 的重要考点，并通过一系列题目得以落实。
训练的其余时间进行了大量模拟赛，练习时间还算可以。抓的很紧。

赛时策略

比赛的策略很重要。这里以 CSP−S 2025CSP-S\ 2025 的惨痛教训制定以下策略：
1.仍然先写暴力做法，但花在每一题暴力做法上的时间不可超过 3030 分钟。
2.写完暴力再写部分分，不追求正解，但简单题（有时的第一题贪心）可以尝试推出最优解。
3.剩下的时间拿来测试，检查，优化。

考试注意事项

1.分析与过程要再纸上进行推导，读完题目立刻拿笔抄写样例，将精力从屏幕上转移到纸面上，专注于分析本身。
2.写代码是想到就写，调试立马动手，多尝试比只看屏幕不敲代码的代价要低得多。
3.不要瞎探索电脑，出了问题会影响考试心态。

考前准备

1.考前一天晚上 1010 点之前睡觉。
2.心无杂念，心平气和，安心，开心。
3.把之前的所有模板敲一遍，写一写 NOIPNOIP 以前题目的暴力做法。
4.自信！！！！！！！，NOIPNOIP 没有那么难得高分！

学术总结

基础算法

1.贪心

第一题经常就是贪心。这样的策略是很好的，可用于最优解或者假算法偏分。
对于贪心是期望拿到分的。看到简单题就往贪心上去想一想，多手玩，拿纸拿笔。

2.排序

对于和序列位置没有影响，或者可以通过记录序列位置变换问题的，sortsort 一下说不定有意想不到的结果。
通常和贪心思想一起用。

3.二分

二分搜索
对于有单调性的东西要在序列中查找，二分搜索是 O(n)O(n) 变 O(log⁡n)O(\log n) 的利器。
二分答案
和贪心一样很重要的一个好用的算法。
对于答案有单调性的问题，可以转换为二分搜索答案进行 checkcheck 答案可行性的问题。
通常来说，最小值最大和最大值最小都常用这样的方式求解。

4.搜索&枚举

写暴力啊！
DFSDFS，BFSBFS，多重循环多重循环。暴力出奇迹。
见到题目就可以打搜索，或者暴力枚举，得部分分。

5.快速幂

数学天天用，无论是数学题还是组合数求逆。
代码很简单，这怎么能不背下来呢。

DPDP

极为重要的算法和思想。不仅可以将问题转化为分步的最优子问题递推，还在各大更牛的算法有很多很多应用，如倍增倍增，DAG最长路DAG最长路 等。
我的 DPDP 学的并不好，仅仅会最基础的状态设计和转移。
DPDP 需要大量的练习，大量的做题，揣摩状态的设计与转移。
分很多种，不过总结来说都是那样。
题目可用 DPDP 的条件：重叠子问题，最优子状态，无后效性。
步骤：设计状态，推出转移，初始化递推起点，求得答案。
DPDP 的经验看个人积累，所以我就不说了，毕竟造诣不深。

数据结构

并查集

很简单的数据结构，再很多算法中都有应用。比如 KruskalKruskal。
就是一个用树结构维护的集合，可以做到 O(α(n))O(\alpha(n)) 的复杂度查询两个元素是否在同一集合内。非常优秀的算法。
CPP
int find(int x){return dsu[x]==x?x:dsu[x]=find(dsu[x]);}

树状数组

区间上的单点修改和区间查询操作可用其维护，也可扩展为区间修改与单点查询。巧妙地运用了 lowbitlowbit 函数。
CPP
int lowbit(int x){return x&(-x);}

线段树

我最喜欢的数据结构。
应用及其广泛。可以对区间修改区间查询高效 O(log⁡n)O(\log n) 维护。只需要满足结合律。
线段树是真的建了一棵树。节点上存储了需要记录的信息，理解起来其实不难。

STST 表

特殊的，对于 RMQRMQ 问题，即区间最值问题（可推广到任何重叠区间不影响答案的问题），做到了 O(1)O(1) 查询 O(nlog⁡n)O(n\log n) 初始化。用了倍增及 DPDP 思想。巧妙的利用了重叠区间不影响答案的性质。
CPP
dp[i][k]=min(dp[i][k-1],dp[i+(1<<(k-1))][k-1]);

分块

任意的带修区间性问题都可以用分块相对高效地解决。标记 n\sqrt n 一个 n\sqrt n 大小的 tagtag ，每次查询时分别处理左边溢出的，中间 tagtag 里的，和右边溢出的。复杂度 O(nn)O(n\sqrt n)。

字符串

KMPKMP

字符串匹配经典算法。理解很爽，代码很短，细节很多。
next[i]表示前缀与后缀相同的最大长度。
令 nn 为原串长度，mm 为匹配串长度，可以 O(m)O(m) 构造 nextnext 数组， 在 O(n)O(n) 的时间内完成匹配。

字符串哈希

大可以用 std::unordered_mapstd::unordered\_map 代替。

图论

图论是算法竞赛中的重要部分。

最小生成树（Minimum Spanning TreeMinimum\ Spanning\ Tree, MSTMST）

用于在加权连通图中找到一棵生成树，使得所有边的权重之和最小。
KruskalKruskal
基于贪心算法，将边按权重从小到大排序，依次选择边，若加入后不形成环（用并查集检查），则加入生成树。适用于稀疏图（边少）。用邻接矩阵。
O(Elog⁡E)O(E \log E) 或 O(Elog⁡V)O(E \log V)，主要开销在排序。
PrimPrim
基于贪心算法，从任意顶点开始，维护一个已选集合，每次选择连接已选集和未选集的最小权重边。适用于稠密图（边多）。用邻接表。
使用优先队列（最小堆）时，O(Elog⁡V)O(E \log V)。一般不用堆优化。O(V2)O(V^2)。

最短路（Shortest PathShortest\ Path）

用于求图中两点间的最短路径权重。
堆优化 DijsktraDijsktra
贪心算法，适用于非负权图。使用优先队列不断扩展当前最短路径的顶点。不能处理负权。
O((V+E)log⁡V)O((V + E) \log V)。
FloydFloyd
动态规划，求所有点对的最短路径。通过中间点更新距离矩阵，可处理负权，但不能有负环。
O(V3)O(V^3)，适合小规模图。
KruskalKruskal 和 PrimPrim 选择取决于图密度，DijkstraDijkstra 用于丹源非负权最短路，FloydFloyd 适合全源最短路径。

拓扑排序（Topological SortTopological\ Sort）

拓扑排序是针对有向无环图（DAGDAG）的顶点进行线性排序，使得对于任何有向边 u→vu→v，uu 在排序中都出现在 vv 之前。
基于 BFSBFS（KahnKahn 算法）或 DFSDFS 实现，本质是不断移除入度为 00 的顶点。
只能应用于有向无环图（DAGDAG），有环图无法进行拓扑排序。
O(V+E)O(V + E)。
可结合 DPDP 实现求 DAGDAG 上最长路。

总结

蓦然回首，往事并不如烟。
NOIP RP++。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...