NOIP知识点梳理

梦想不抛弃苦心追求的人,只要不停止追求,你们会沐浴在梦想的光辉之中。再美好的梦想与目标,再完美的计划和方案,如果不能尽快在行动中落实,最终只能是纸上谈兵,空想一番。只要瞄准了大方向,坚持不懈地做下去,才能够扫除挡在梦想前面的障碍,实现美好的人生蓝图。NOIP知识点梳理,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com,来源:原文

NOIP知识点梳理
建议用sublime或者其他编辑器打开。
备注:
	*开头的是NOI选手必会的,
	**开头的可以在NOIP之后再学,
	★开头的是重要的内容,★越多越重要
复习建议:
	顺着每个知识点依次回顾,所有模板都保证自己都在考场上一遍打对,每个知识点都去网上搜搜别人的总结,仔细看别人做过的经典题目。
	除此之外,之前NOIP2010~2017的所有题目都应完成,暑假training的chapter1~7都应完成。

基础算法
		枚举				考察概率100%,经常考在两天T1
			枚举方式		经常见到的考察方式,按正常思路枚举TLE,换个枚举角度AC,注意挖掘枚举内容里面可以直接推出来的信息
			★二进制枚举		没什么好说的

		贪心				也经常考对吧,没什么好说的,记得不确定正确性的贪心一定要写个暴力代码跑随机数据验证一下  
			★★按位贪心
			构造

		★★二分				最常见的容易让人丢分的知识点,跳石头这个题当年让无数人挂掉啊。
			二分+贪心
			二分+枚举
			二分+***		各种二分+***的考察方式屡见不鲜,遇到题目的时候一定考虑一下是否具有单调性,有单调性的时候可能用得着

			0/1分数规划		常见的二分考法,一定记着复习一下
		*三分				NOI选手必会,其他人选择性学习。

		排序
			★冒泡、选择、插入排序
							太常见的超简单排序,但是经常有出题人利用其性质来出题,尤其是冒泡排序,所以一定得熟悉冒泡排序,而且可以深挖。插入排序需要记得一个细节:如果一个有序的序列里面插入一个元素,插入排序的复杂度是O(N)的,其他排序反而没有插入排序快,切记。(当然splay或者treap更快,前提条件是你会)
			★归并排序		分治的典型应用,好多题目的思路其实和归并排序本质上是一样的,一定要对归并排序特别特别理解才行。
			快速排序		虽然现在大家都有STL了,但是快速排序还是得明白原理的。
			统计排序		桶排很简单,但是往往很有用,有一个小技巧分享给大家,如果你要用统计排序来统计一些数字,但是每次统计的数字量很小(比如只有100个),但是数字范围并不那么小(比如数字范围在1~10^5),而你却需要做这个事情很多次,那么如果暴力去做,每次都要清空这个数组,然后再做,memset复杂度也是很高的(顺便提一句,memset需要string.h这个头文件,每年都有好多人因为这个丢100分),你可以直接开一个int类型的数组,第一次用是不是1来判断这个数字在不在里面,第二次用是不是2来判断...,而不是每次都清空他。

		★分治				作为一个简单的知识点,却经常会作为解决一个难题的第一步,建议想得到400以上的同学多去做一些分治的好题。

数据结构
		前缀和				不用我说也知道的东西
		队列、栈			队列的内容下面会细说,栈的话牢记一点,先进后出,很多和栈有关的题都跟这个性质有关。
			★双指针			这个东西记得复习一下,别这种简单题都挂了
			★双端队列
				单调队列	NOIP常见简单,却得分率很低的知识点,一定复习,写熟
			单调栈			跟单调队列有点像的数据结构,只不过单调队列两边同时进出,单调栈只有一边。
			★优先队列
		★倍增				本质上是一种思想,但是放在数据结构板块把
			st表			处理离线区间极值的好工具
			LCA				其实就是树上的倍增了,考前记得复习模板
			DP+倍增			常见的一个考点,可以去做几个题复习,推荐LCA去年出的LOJ NOIP2017模拟赛D1T3
		分块
		★并查集				巧妙的考法太多了,经典例题数都数不完,以下例题必定要复习啊:《连续攻击游戏,食物链,银河英雄传说,双栈排序,关押罪犯,暑假模拟赛的那道》
		★树状数组			必须得会,记得单点修改,区间查询/区间修改,单点查询的两个用法
		*线段树				NOI选手必会,大知识点啊,以后肯定越考越多,推荐无论如何要把NOI2017D1T1做了。
			*线段树上二分	这个得会啊,别傻不拉几的跑两个log的算法
			*扫描线			基本技巧
			*树链剖分		别遇到题就一定去想树链剖分,NOIP考出来很多时候有更巧妙的做法,例如暑假模拟赛的那道并查集,之前NOIP的那些树上差分,实在想不到正解,时间充足再去打树剖。
			**二维线段树	这个可以NOIP之后再搞
		*可持久化			懒得说NOI选手必会了,就是神思想,不多说,但是NOIP遇到了记得考虑,是否离线去做更简单,而非在线+可持久化。
			可持久化线段树
			可持久化并查集
			可持久化字典树
		*整体二分			NOI选手必会,多么巧妙的一种思路啊。
		*cdq分治			NOI选手必会,多做几个题就能很好的理解它的思想了。
		★虚树				我有一种感觉,今年可能要考一个离线建虚树然后树上差分的题。所有人必学。
		树上的知识点
			dfs,bfs序的应用
			★LCA
			树的直径
			★树上差分
			*点分治
		*Splay/Treap		D2T3如果是数据结构题,很可能有暴力Splay 70分的做法,需要打的非常熟练啊。
			**LCT			这个可以NOIP之后再搞
		**KD-Tree			这个可以NOIP之后再搞
		*替罪羊树			之前一直没讲的知识点,需要学习。

★搜索						别的先不说,代码能力很重要
		深度优先搜索		搜索这个东西就像买挤海绵,你每努力挤一点都能多出一点水,别的不说,去年CKY NOIPD2T2,硬是搜了70+,比任何一种部分分做法分数都高。
			剪枝
			记忆化
			IDA*
			随机化
		广度优先搜索
			A*
			HASH	

字符串
		★Manacher算法		这个之前真没讲,O(N)处理最长/所有回文子串的算法,不得不说真的神,必须学习然后去做计蒜客Skr这个题。
		★字符串HASH			好东西不多说,谁不会谁吃亏
		Trie树				考前打熟练,超过10分钟的都回去重新练
		huffman编码			这个属于不考不要紧,一考挂一片的类型,其实就是个超简单的贪心
		KMP/扩展KMP			NOIP选手必会KMP,NOI选手必都会。
		**后缀数组			NOIP之后再搞
		**后缀自动机		NOIP之后再搞
		*AC自动机			虽然NOIP不会考,但是这么简单的玩意还是别放在NOIP之后了。

数学
		整数相关
			★质因子分解
			LCM,GCD
			★★ext-gcd,逆元
			★中国剩余定理
			进制转换
			欧拉函数
			坐标系旋转
			**FFT
		★★★组合数学
			排列组合,二项式定理		
							去看数学竞赛书吧
			康托展开
			容斥原理
							这个太重要了!!!
			*lucas定理
			**生成函数		NOIP之后再搞
			卡特兰数,斯特林数
							这个必会
		*线性规划			NOI选手必会
		★★★概率/期望		NOIP2016前一个月,我给参赛选手找数学竞赛教练补了概率,期望,结果一道超简单期望DP,全陕西只有西工大的学生都会做,咱学校只有一个刚学了3个月的精英班学生会。
		**群论
			置换
			polya定理
		线性代数
			★矩阵乘法、快速幂
							我总觉得今年会考一个矩阵快速幂,而且是作为T1或者T2。
			*高斯消元		NOI选手必会
			*线性基
		几何				基本的解析几何总得会吧?别连题目几何的预处理部分都搞不定。
			凸包
			**其他部分不做总结

图论
		图的遍历			常见D2T1考法
		拓扑排序
		最短路
			floyd
				floyd倍增
				floyd求最小环
				floyd的DP意义
			★spfa
				spfa的两个优化
			★dijkstra
				dijkstra的堆优化
		生成树
		*强连通分量
		二分图
			★二分图判定		这一类的题目非常多,一定去仔细看看
			稳定婚姻匹配	简单贪心,自己去看
			★最大匹配		好题很多,经典模型很多,建议去多看几个PPT
				二分图匹配
				最小点覆盖
				最大独立集
			**最优匹配
		**网络流
			最大流、最小割
			费用流

★★★动态规划/DP
		背包
		环形dp				链上的dp放到环上,很容易挂哦,多看几个
		区间dp				多复习这个,否则你考场上肯定容易挂
		状压dp				连考三年了,今年会不会是第四年呢?
			**插头dp
		树形dp				我真的觉得今年有可能来个树上状压
			**基环树dp
		数位dp				这个一般题不难,但是写的不熟费时间
		*博弈dp
		dp的优化
			优化状态
			矩阵加速转移
			*斜率优化/单调队列优化
			*四边形不等式
			*cdq分治
			*利用单调性加速求解


版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由极客之家整理,本文链接:https://www.bmabk.com/index.php/post/151000.html

(0)
飞熊的头像飞熊bm

相关推荐

发表回复

登录后才能评论
极客之家——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!