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