历年复赛提高组题目分析

本文由用户“zhuque020”分享发布 更新时间:2021-10-18 11:30:00 举报文档

以下为《历年复赛提高组题目分析》的无排版文字预览,完整格式请下载

下载前请仔细阅读文字预览以及下方图片预览。图片预览是什么样的,下载的文档就是什么样的。

历年题目的分析(2017年之前)

【动态规划】共15题

此项为历届NOIP考察次数最多的知识点。主要有 1.区间模型 2.子序列模型 3.资源分配模型(多) 以及一些简单的多维状态设计技巧(多)等。NOIP的动态规划,一般不需要多少优化,所以只需要能在题目中找到动态规划的思路即可。

【模拟】共14题

平均每届NOIP都会出现1个模拟题。这种题一般算法很简单,需要选手细心理解题目意思,注意细节,考察选手的代码实现能力。

【数学】共7题

需要掌握质数及其性质,基础的实数操作,加法原理和乘法原理。此类题需要选手对数学规律的灵感。

【图论】共4题

历届考察点基本上都是1.最短路问题 和 2.特殊图的性质 。特殊图包括树,拓扑图,二分图等。历届NOIP在图论上的考察并不是很多。很少有考到像网络流这样难度的图论。

【搜索】共5题

2012之后的几年,大搜索题频繁出。历届搜索题一般都比较难,搜索算法本身简单,但是要跑对所有数据也是相当难的。搜索算法中,最重要的是剪枝,这些需要在辅导时强调。另外,当自己没有最优的剪枝想法时,写一些较弱的剪枝也是可以的。搜索题尽量拿分。

【构造】共3题

构造类题目一般没有明确的算法,需要选手仔细分析题目的实质,并得出解法,这个解法通常不是唯一的。有时一个好的贪心可以得相当多的分。有时搜索剪枝可以很大的提高效率。同样以多得分为目标。

【贪心】共4题

此类题需要选手对算法的直觉,贪心正确性一旦被证明,通常题目就简单了。有些贪心不太容易相处,一些弱一点的贪心算法也可以为自己争取一些分。

【枚举】共4题

此类题主要是二分枚举,一般以二分答案。实际上就是先枚举答案再判断可行性来做。当然首先要保证答案具有单调性。

noip2013~noip2015(最近几年分析)

实际上这几年还是搜索和分析题目性质贪心思维出现的比较频繁。总之近几年有1:水题。2:脑洞思维题。3:大搜索代码能力的题。所以针对一下练的话1:考场策略,怎么做题之类。2:模拟题贪心练习。3:专项练习大搜索 内容过长,仅展示头部和尾部部分文字预览,全文请查看图片预览。 4.动态规划

动态规划、贪心都是和子问题相关的,动态规划的基本思想是将一个大的问题划分成子问题,接着分别求解,而且能够将一些重复的计算记忆化,大大提高效率。

5.搜索与枚举

搜索和枚举在本质上都是相同的,一般来说用在数据范围较小的题目中,而且比较容易写。当然在能够观察到有着非常多的重复计算时可以使用记忆化搜索,不过使用了记忆化之后DP方程通常也不难求出,但是记忆化搜索比较好写,和搜索很像,考虑到NOIP的弱数据,和动规也都差不多。

6.二分答案

二分答案在实质上是一种枚举的优化,一般采用迭代的写法,但是有的时候也用递归,因为要递归的层数一般很少。二分答案一般适用于当所要求的答案递增时可用,时间复杂度一般来说都是O(log2n)。

7.计数

计数这一技巧可以在数据的规模较小,而对时间复杂度的要求很低时可用,基于计数排序或者哈希表的原理,这个技巧可以在近似O(1)的时间内找到数据。

8.数论

NOIP并不考太过难的题目,比如欧拉函数φ(n)之类的东西,一般来说只会考与质数相关的基本数论,并不会太难,就算是指数筛选也鲜有用O(n)算法的,质数判定之类的问题更是一个O(sqrt(n))的算法就能搞定,一般都出在第一到二题,或者说也就是一些非主要考点罢了。

9.树与图

树与图其实是一个很难的概念,在省赛里几乎是家常便饭,但是NOIP之前并没有考多少,一般来说记住SPFA和Floyed就足够了,还有最小生成树(好像最小树形图都不考),拓扑排序和强联通分量之类的东西,一般来说连像并查某某这样的东西都没有考到,更何况像动态树、平衡树、线段树这样的东西?

10.字符串相关操作

字符串的操作有的时候还是比较烦的,一般来说都是用到一些字符串的基本函数,还有可能会用到的O(m+n)的哈希和KMP之类的算法。

11.数据结构

数据结构一类,无非就是队列、栈、邻接矩阵之类的东西,高级一点也无非是单调队列、哈希表、并查某某,树状数组和线段树就绝对不会考了。其实还是挺简单的,只要细心一点观察题目,不难解决。

[文章尾部最后300字内容到此结束,中间部分内容请查看底下的图片预览]请点击下方选择您需要的文档下载。

  1. 数据结构课程设计报告模板-排序算法的实现 (1)
  2. 实验12最小生成树***实验报告纸
  3. 信息检索与分析技术-题目大全
  4. 魔方比赛主持词
  5. 同学政审评语
  6. 遗传算法函数优化实验
  7. 十几减九说课稿
  8. 1_口算练习11.13

以上为《历年复赛提高组题目分析》的无排版文字预览,完整格式请下载

下载前请仔细阅读上面文字预览以及下方图片预览。图片预览是什么样的,下载的文档就是什么样的。

图片预览