试题分析
（初中部分）
1排序：（有些排序因涉及贪心,所以我放在贪心那一节里了）
历届试题：NOIP 分数线划定 奖学金 明明的随机数 排序法使用：选择排序 。快速排序 。桶排序。 分析：
1． 分数线划定：
（1） 这是一道具有代表性的排序题，可使用选择或快排，使用选择排序
整体难度较小，但因此题数据量较大，选择排序不可过全部数据。
（2） 使用快速排序是解决本题的最好方法，但不可直接套用，因为有几
个排序条件，排序内最好添加几个辅助变量。
2． 奖学金：
（1） 这道题和上题大体相同，但其测试数据较小，可使用选择排序得全
分。
3． 明明的随机数：
（1） 本题可用选择或快排，但代码设计较难，使用桶排序解绝此题是较
为理想的选择。
2 模拟：
分为三类：
〈1〉 普通模拟（完全模拟的较少，大多为结合贪心 。排序的，贪心 。 排序
的不单独讨论）
历届试题：NOIP多项式输出数列
1． NOIP 多项式输出.：
（1） 多项式输出:这道题想要拿分很容易，但要注意一下模拟过程，此题
实际上需有4个判段过程，其中有一个是极易遗漏的。
（2） 数列:这道题竟是第4题,很简单的模拟题,还可用转成2进制的方式
直接算.
〈2〉 字符模拟
历届试题：NOIP ISBN号码 Jam记数法 立体图
（1）
ISBN号码: 总体难度不大，这道题如果是使用C语言的话，可以用 每个字符都减去字符0 的方式，直接把它们从字符转为数字,再进行处理。
Jam记数法:很绝对的模拟,一开始我还认为是数学知识模拟题,就是从后往前推.
（2）
（3） 立体图:很难的很考细心的一道模拟题,没说的,就是上机不断的调程序.
〈3〉 数学知识模拟
历届试题：NOIP 细胞分裂
（1） 初中组目前唯一一道数学知识模拟题，掌握了相关的知识就应该
不难，这道题要满分还是比较难的，需要高精度运算（用LONG LONG 型不知道可不可以）,还有一定要注意时间问题,这道题极易
超时.
3 贪心：
历届试题：NOIP 排座椅 纪念品分组 守望者的逃离. 注意：任何贪心之前都必需排序。
（1） 排座椅:这道题初看不像一道贪心,但实际上只要细细的看,就可
以发现了,跟实际生活联系很紧密的一道题。
（2） 纪念品分组:很典型的一道贪心题，看起来挺难，但实际上先排
序再贪心，一点问题都没有。
（3） 守望者的逃离:这道题是一道动规题，但实际上也可贪心解决+
模拟，这样的话还是挺难的.
4 动态规化：
历届试题:开心的金明,道路游戏,守望者的逃离,传球游戏. 注意：这是普及组最难的题目类型。
（1） :开心的金明:这是一道非常典型的背包问题,学了动态化化了此题就应该
不会太难.
（2） 道路游戏:目前普及组最难的DP题了,DP做为第4 题就是不一样,费
了九牛二虎之力我才把它完成,没一定DP基础这题肯定是别想作了,我作的程序可过所有数据,不过时间复杂度为
O(m*n*p)大数据估计是别想过了,努力优化中…….(貌似可用单调队列)
(3) 守望者的逃离:这道题本来我已经将其放在了前面,为什么现在又把它拿
出来呢?
因为这题用模拟的方式自我感觉很难,但用DP就方便多了,不过还是要 注意下,DP本题拿不到全分.
(4) 传球游戏:DP代码最少的一道题,应该还可以用搜索做吧,不过DP起来似
乎是简单些.
5 递归:
历届试题：NOIP Hanoi 双塔问题.
(1) Hanoi 双塔问题:这题初看很简单,就是把程序书上讲递归的例题改了一下,
但细看下就难了,不仅仅是高精度,并且用递归时间复杂度为O(2^N)多达200的N,不超时就不正常了,想正常过得用栈加高精度,绝对的超难,不过想解绝它还是有办法的,因为本题有后门.
6 图论:(目前我还没在普及组找到相关题型)
7搜索:(有很多题都可用搜索来做,但用别的方法会更好一些,不但独讨论)
.
总结分析:
出题趋势分析: 明年的题目陶陶估计是不会再来摘苹果了,明年的第一和第二题估记和往年的差不多,一道排序相关,一道模拟相关.第三题要不动规,要不很复杂模拟,第4题就比较难猜了 动规? 递归? 图论? 模拟? 其它?
难度分析:难度应不会出现太大变化,1 2 两题应该保证,第 3 题时间够拿分就没问题,第4 题就不知道了.
难点分析: 动规和图论吧,可能还有那种难的吓人的模拟.
送分问题分析:近两年年年普及组都有送分的测试点(看来现在NOIP正在进入一个全民有奖时代,这对大多数初学这来说是个好消息,有分不会拿的除外” 我就是其中之一”)
具体分析:送分有两种方式,(出题者不可能把某个测试点的答案写再试题旁边,
除非他相对于我们来说不太正常)
1. 真假问题,送分题一般都这个,例: 如果问题有解就输出真+某某,
如果问题无解就输出假. 这个只要稍想下,就可以看出我们不管别的,无论怎样程序永远向外吐假就OK了.
2. 样例问题:实际上很多时后出题人偷懒,把样例也用做了一组测试
数据,我们的程序只要不断吐样例的结果就有分了.
因篇幅问题不能全部显示，请点此查看更多更全内容