NOIP2017复赛备考攻略！

 定期推送账号信息学新闻，竞赛自主招生，信息学专业知识，信息学疑难解答，等诸多优质内容的微信平台，欢迎分享文章给你的朋友或者朋友圈！

试题分析

今天将对复赛试题，复赛考点，复赛考试经验做一次分享。部分内容参考自网络！

先是对历年题目的分析（12年之前）

【动态规划】共15题
        此项为历届NOIP考察次数最多的知识点。主要有 1.区间模型 2.子序列模型 3.资源分配模型（多） 以及一些简单的多维状态设计技巧（多）等。NOIP的动态规划，一般不需要多少优化，所以只需要能在题目中找到动态规划的思路即可。
【模拟】共14题
        平均每届NOIP都会出现1个模拟题。这种题一般算法很简单，需要选手细心理解题目意思，注意细节，考察选手的代码实现能力。
【数学】共7题
        需要掌握质数及其性质，基础的实属操作，加法原理和乘法原理。此类题需要选手对数学规律的灵感。
【图论】共4题
        历届考察点基本上都是1.最短路问题 和 2.特殊图的性质 。特殊图包括树，拓扑图，二分图等。历届NOIP在图论上的考察并不是很多。很少有考到像网络流这样难度的图论。
【搜索】共5题
        2012之后的几年，大搜索题频繁出。也是我现在最需要练习的题。当然也不能忘了剪枝。
历届搜索题一般都比较难，搜索算法本身简单，但是要跑对所有数据也是相当难的。搜索算法中，最重要的是剪枝，这些需要在辅导时强调。另外，当自己没有最优的剪枝想法时，写一些较弱的剪枝也是可以的。搜索题尽量能拿多少分即可。
【构造】共3题
        构造类题目一般没有明确的算法，需要选手仔细分析题目的实质，并得出解法，这个解法通常不是唯一的。有时一个好的贪心可以得相当多的分。有时搜索剪枝可以很大的提高效率。同样以多得分为目标。
【贪心】共4题
        此类题需要选手对算法的直觉，贪心正确性一旦被证明，通常题目就简单了。 有些贪心不太容易相处，一些弱一点的贪心算法也可以为自己争取一些分。
【枚举】共4题
        此类题主要是二分枚举，一般以二分答案。实际上就是先枚举答案再判断可行性来做。当然首先要保证答案具有单调性。
noip2013~noip2015（最近几年分析，更多到Q群 476118259找学姐）
实际上这几年还是搜索和分析题目性质贪心思维出现的比较频繁。

 总之近几年有1：水题。2：脑洞思维题。3：大搜索代码能力的题。
所以针对一下练的话1：考场策略，怎么做题之类。2：模拟题贪心练习。3：专项练习大搜索。
        当然，noip绝对不会考多高难度的算法题，不过一些小知识点有可能（火柴排队，逆序对）。所以觉得题目比较怪，可能用到什么高级的算法，就不用想了，这时就应该另换一下思路了。

2012年以后试题命题趋势

        随着近几年比赛的不断进行，我们发现NOIP逐步淡化对算法的考察,更侧重考察思维.已经不是说学习的算法越多,成绩就会越好.最近2年考察的模板算法很少,只有LCA有背的价值,像二分,dfs原理都非常简单,理解即可.信息竞赛中最适合考察思维的莫过于动规与贪心,由于贪心要么太显然大家都看得出来,要么太难只有极少数人能发现,所以贪心的区分度较低,因此动态规划理所当然的成为了NOIP复赛的宠儿,基本每年都会有1道动态规划的题目,甚至一年2道.最近动规题目的考察也不再是最基本的背包问题,像16年与期望相结合与状态压缩相结合,都进一步加大了思考的难度.

稳中取胜是关键，能拿分的题一定不要粗心！

可能出现的考点

      

复赛题目的特点是： 

 

第一题：算法比较明显的，或者和数学关系比较大的题目。 

第二题：好上手，但程序量要大一点的题目，考虑全面也不容易。 

第三和四题：一般是搜索，或者算法不明显的题目。 算法方面，可能考到的是：穷举、搜索(回溯就可以了)、动态规划(几乎是必考)、贪心、递推(小心真的考到)，递归„„，数据结构反而考得不多，熟悉字符串的操作和排序算法就差不多了。

一些相对重要的算法要学会：

1.高精度

高精度是一个非常非常重要的算法！高精度一般来说会用在递推、动态规划求方案数，以及组合数学直接计算的方面。一定要熟悉高精度的加减乘，除法至少也要记住原理，求余就比较少见了。

2.模拟

这是非常基础的内容，但是有可能出很难的题目，比如08年的立体图，一定要注意审清题目，弄懂题意。

3.贪心

贪心是一种比较重要的算法，在关键时刻可以做出一些避免超时的决策，在比如说搜索、动规时也可以起到相对重要的作用，大大减少状态数，比如守望者的逃离一题，直接动规就会爆内存+超时，用贪心可以使状态数快速锐减。

4.动态规划

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

5.搜索与枚举

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

6.二分答案

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

7.计数

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

8.数论

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

9.树与图

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

10.字符串相关操作

字符串的操作有的时候还是比较烦的，比如说洛谷11月月赛的第一题，我用了半个小时才写出一个程序来。一般来说都是用到一些字符串的基本函数，还有可能会用到的O(m+n)的哈希和KMP之类的算法。

11.数据结构

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

注

意

事

项

复赛题目的特点是：  

第一题：肯定是水题，基本上不难想到解法，一般来说模拟即可

第二题：可能会用到一些基础算法，比如贪心，枚举，搜索之类，很入门

第三题：从第三道题开始就会难很多，会逐渐考到二分、动态规划之类的算法，应该会相对难不少

第四题：最后一道题绝对是压轴题，要么是剪枝的搜索，要么是动态规划，甚至还有状压DP、树形DP之类的，可能会考到树和图。

 1、知识体系回顾，多做经典题目。在算法方面可能考到的是：穷举、搜索(回溯就可以了)、动态规划(几乎必考)、贪心、递推(小心真的考到)、递归、 简单的图论算法（dijkstra等），熟悉字符串的操作（包括字符串的几个常用函数）和排序算法就差不多了。记住：信息学不是看会的，是练会的。一定要多看多想多练。

  

2、养成编码和调试习惯。复赛考查的算法并不困难，选手在实现上的问题往往还要大一些。因此建议：   

①充分利用草稿纸，不要对自己的“心算能力”太自信了。做信息学竞赛题的思维过程是丰富而曲折多变的，考虑问题必须全面。  

②编码采取自顶向下，逐步求精的方法，调试时采用输出中间结果的办法及时找出错误的地方。可以这么说，思路越清晰，对自己程序的算法和编码越了解，调试也会越顺利（一定不要忽视）。 

 ③多做套题，做单个题目和套题感觉并不一样。做套题要涉及到时间分配和做题顺序等，这些东西同样十分重要。

3、最大限度发挥水平。   

①认真审题。审题对于信息学竞赛来说尤其重要。同一个题目如果数据限制差异大的话可能难度差异也很不同。例如：输入A、B，输出A+B的值。如果题目说0<><><><=10^100则显然就要用到高精度数的处理了。从某种意义上说，数据限制也暗示了可能的算法，数据小，也许是搜索派上用场的时候，数据大了，可能只能考虑动态规划、数学方法等高效的算法了。>

②正确估计题目的难度和自己的水平。平时最熟悉和有把握的题，一定要做对。熟悉的题目要加强编程熟练度、准确度、测试和调试能力，把自己有能力拿到的分拿稳。

  

③重视测试。测试的数据既要考虑一般，也要考虑特殊情况，评分的唯一标准是测试数据。一道困难的题目如果无法下手，在时间允许的情况下一定要写一个能解一些特殊情况的程序。很多最优化题目，不要一个字都不写，根据“直觉”算法（如贪心），虽然得不了满分，也能得一定的分数。 

④编程过程中注意随时存盘。最好保留一些不同版本（如算法不同）的程序，便于选择修改。    比赛时首先设置好编程环境的工作路径：File-Change dir  保存文件的文件名以及程序中引用的输入输出文件名一定要按要求命名，包括文件名的大小写。程序中标识输入输出文件时，一定要用相对路径，绝不可用绝对路径。

复习的时候大家要注意：

多做题！会用基本函数（一些同学甚至连一些基本函数都没听说过，了解常用函数会让编程更加简洁并减少出错率.至少以下函数希望同学能了解会用: sort, min, max, swap, abs, fabs, memset, make_heap, pop_heap, push_heap, sort heap.）

了解STL容器，熟练掌握常用算法以及优化方法！！！注意细节！！

赛前注意事项:

比赛结束前注意：

复赛大纲：

长沙信息学竞赛