NOIP复赛知识点简述

全国青少年信息学奥林匹克联赛（National Olympiad in Informatics in Provinces，简称NOIP）

转眼已到了下半年，马上将迎来一场重要的比赛——NOIP。

考前赶紧来总结一下一些必要的知识点。

普及组必学

1、模拟算法（暴力枚举），按照题目的要求，题目怎么说就怎么做，保证时间和正确性即可。

2、搜索与回溯，主要的是DFS（深度优先搜索）和BFS（宽度优先搜索），基本没有直接的暴力搜索。一般是记忆化搜索加剪枝，普及组第三题难度。

3、简单操作：如筛法、前缀和、快速幂、高精度、辗转相除法等，掌握全面即可应对大部分处理数据上的问题。

4、队列（单调队列）、栈、堆、链表等基础数据结构。

5、简单二分和分治（快速排序，归并排序）。

6、贪心，要保证贪心的正确性，如果无法证明也可以用来骗分。

7、数学知识、公式计算，要点在于公式的化简与变形，经过反复操作后也许就能得出重要结论。

8、简单的动态规划，容易推出状态转移方程，要注意初值与计算边界条件。

9、字符串基本操作，插入、删除、查找等。

10、经典例题变形加深：八皇后、马的走法、背包问题等。

提高组必学

0、普及组的10条。

1、较难的动态规划，多维的状态，转移方式较多。

2、简单数论，如扩展GCD，欧拉函数等。

3、进阶算法：倍增，并查集，差分约束、拓扑排序，排列组合数，逆元，哈希。

4、最短路问题，需要掌握弗洛伊德算法、SPFA算法、dijkstra算法，以及它们对应的优化，再根据题目实际要求进行变形，用同样模板达到各种不一样的效果。

5、最小生成树问题，主要的两种算法为Prim和Kruskal，同样要加上对应的优化，再根据题目进行变形，以满足题目的实际要求。

6、二分图染色、二分图匹配，一般题目都隐藏得很深，需要找到题目的本质，才能发现正确的解法。

7、强连通分量Tarjan，最近公共祖先LCA。

8、数据结构：线段树、字典树、主席树、树状数组等。

9、树的更多操作：树链剖分、树的直径、树的重心等。

10、字符串操作：KMP等。

更多拓展

大部分是省赛内容，如果想NOIP取得好成绩的话，挑一些简单的学习一下吧！

搜索：

启发式搜索（A*）

迭代加深

IDA*

随机化搜索

图论：

网络流

仙人掌算法

树：

平衡树

树套树

圆方树

线段树合并

数学：

容斥原理

莫比乌斯反演

中国剩余定理

欧拉定理

矩阵乘法

FFT

博弈论相关

计算几何

字符串：

字符串哈希

AC自动机

后缀数组

后缀自动机

回文自动机

manacher

面对这些算法与数据结构，你是不是已经手足无措了呢？那就赶紧来学习吧！

相互学习，相互进步，加油！

定期推送帐号信息学新闻，竞赛自主招生，信息学专业知识，信息学疑难解答，信息学训练营信息等诸多优质内容的wx公众平台noipnoi