ag旗舰厅官方网站首页_
资讯中心 Info
当前位置:酷叮猫 > 资讯中心 >
NOIP复赛知识点简述
发布日期:2018-06-18 阅读次数:0

全国青少年信息学奥林匹克联赛(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、最小生成树问题,主要的两种算法为PrimKruskal,同样要加上对应的优化,再根据题目进行变形,以满足题目的实际要求。

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

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

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

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

10、字符串操作:KMP等。

 

更多拓展

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

搜索启发式搜索(A*迭代加深IDA*随机化搜索

图论网络流仙人掌算法

平衡树树套树圆方树线段树合并

数学容斥原理莫比乌斯反演中国剩余定理欧拉定理矩阵乘法FFT博弈论相关计算几何

字符串字符串哈希AC自动机后缀数组后缀自动机回文自动机manacher

 

希望这些信息可以帮助到更多热爱NOIP的学子们!

ag旗舰厅官方网站首页_ www.errands4you.com www.mariaradgoli.com 首页-亚美国际平台-亚美am8客户端 亚美am8客户中心