【信息奥赛专题】近20年信息学奥赛真题考点统计分析系列
信息学奥赛专题系列
准备先后发布近20年信息学奥赛复赛的真题考点。包含：
系列1:
2000~2009，10年普及组复赛真题考点统计
2000~2009，10年提高组复赛真题考点统计
系列2:
2010~2019，10年普及组复赛真题考点统计
2010~2019，10年提高组复赛真题考点统计
真题考点
今天发布系列1，2000~2009这10年间信息学奥赛（NOIP）普及组和提高组复赛真题的主要考点。
普及组
年份
题目
主要考点
2000年
计算器的改良
字符串
税收与补贴问题
数学、枚举
单词接龙
深搜
乘积最大
动态规划
2001年
求先序排列
树的遍历
数的计算
动态规划
装箱问题
背包、枚举
最大公约数
和最小公倍数
数学（辗转相除法）
2002年
级数求和
枚举
过河卒
动态规划
选数
深搜、素数判定
产生数
最短路（图论）
高精度
2003年
数字游戏
动态规划
麦森数
分治、高精度
栈
数学（卡特兰数）
乒乓球
字符串
2004年
FBI 树
二叉树的遍历
不高兴的津津
枚举
火星人
数学(排列)、stl
花生采摘
贪心
2005年
采药
0/1背包
循环
高精度、数论、
快速幂
淘淘摘苹果
枚举
校门外的树
枚举
2006年
开心的金明
0/1 背包
明明的随机数
桶排序、冒泡
Jam 计数法
数学、字符串
数列
数学（进制转换）
2007年
守望者的逃离
动态规划、枚举
奖学金
快速排序
Hanoi 双塔问题
数学、高精度
纪念品分组
贪心、排序算法
2008年
ISBN 号码
字符串
排座椅
贪心
传球游戏
递推
立体图
字符输出
2009年
分数线划定
快速排序
多项式输出
字符串
细胞分裂
数论
道路游戏
动态规划
提高组
年份
题目
主要考点
2000年
进制转换
数学、字符串
乘积最大
动态规划
单词接龙
深度优先搜索
方格取数
多维动态规划
2001年
一元三次方程求解
数学、枚举
数的划分
资源分配动规
统计单词个数
字符串
Car 的旅行路线
图论
2002年
均分纸牌
模拟、贪心
字串变换
字符串、BFS
自由落体
数学、模拟
矩形覆盖
动态规划、搜索剪枝
2003年
神经网络
递推、图论
侦探推理
枚举、模拟
加分二叉树
树、区间动归
传染病控制
贪心、搜索剪枝
2004年
津津的储蓄计划
模拟
合并果子
最优哈夫曼树、
排序、贪心
合唱队形
动态规划
虫食算
搜索剪枝、模拟
2005年
谁拿了最多奖学金
模拟
过河
动态规划
篝火晚会
贪心
等价表达式
抽样检测、字符串
2006年
能量项链
区间环动规
金明的预算方案
动态规划
作业调度方案
模拟
2^k 进制数
组合数学、高精度
2007年
统计数字
排序
字符串的展开
模拟
矩阵取数游戏
区间动规、高精度
树网的核
图论、树
2008年
笨小猴
质数、字符串
火柴棒等式
枚举
传纸条
多维状态动规
双栈排序
枚举、贪心
2009年
潜伏者
字符串、模拟
Hankson 的趣味题
数论、组合数学
最优贸易
图论
靶形数独
搜索
（PS：如需这些真题的源文件，可添加文章底部作者微信，发送给需要的朋友。）
题目特点归纳
第一题：
以基础为主，基本想到解法不会太难，算法比较明，一般用模拟，或者和数学关系较直接。
第二题：
程序量要大一点，可能会用到一些基础算法，比如贪心，枚举，搜索之类。学生在做的时候有时候会遗漏考虑点。
第三题：
难度加大，会涉及到二分、动态规划之类的算法，容易遗漏考虑点，不易得全分，考试的时候要注意全面性。
第四题：
一般是压轴题，算法不明显，剪枝的搜索、动态规划、状压 DP、树形 DP 、树、图等。
重点算法归纳
总结起来想取得好的成绩，这几个相对比较重要的算法一定要学好：
枚举
枚举算法是指，列举出所有可能的取值，从中找出最优解。
模拟
模拟算法是指，通过逐步进行操作、逐步判断来推断是否符合题目中所给出的情况。非常耗时，一般不可能得到最优解，但是可以得到部分分数。
高精度
高精度一般来说会用在递推、动态规划求方案数，以及组合数学直接计算的方面。一定要熟悉高精度的加减乘，除法和求余相对出现的较少。
字符串
主要是字符串的一些相关操作和技巧。
贪心
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。在关键时刻可以做出一些避免超时的决策，在比如说搜索、动规时也可以起到相对重要的作用，大大减少状态数。
动态规划
动态规划主要的思考规律：
定义函数（动态转移方程中转移量的定义）——>建立方程——>确定初值和边界。对思维的周密程度和逻辑要求非常高。可以用来训练思维，对于学习时间短的同学，动态规划可以帮助你迅速进入编程状态，也有助于帮你发现题目背后可能隐藏的更简便的算法。动态规划、贪心都是和子问题相关的，动态规划的基本思想是将一个大的问题划分成子问题，接着分别求解，而且能够将一些重复的计算记忆化，大大提高效率。
图论
最短路和最小生成树。最短路中需要学习Dijkstra算法和Floyd算法。近年来图论题目越来越难，至少掌握这两种。最小生成树需要掌握Prim算法和Kruskal算法。前者适用于稠密图，后者适用于疏密图。两者可以比较学习，比较它们的优点和不足。
常用的数据结构
最常用到的是堆（优先队列）、并查集以及树状数组堆。堆：只关注“直系亲属关系”，不关注“旁系”。常配合贪心使用。并查集：快速判断两个元素是否有关联，增加其他算法，还可判断元素间关系。树状数组堆：平衡查询和修改的操作复杂度的一种算法，常用于解决需要查询和修改的问题。
搜索
深度优先搜索和广度优先搜索。深度优先搜索：一条路走到底。广度优先搜索：每一步将下一步的可能性放入队列中，然后按照队列顺序来探测。比赛中往往会加入很多复杂的元素。
数学知识
快速幂、高精度、筛法选素数、辗转相除法。
总结：
学生参加竞赛的时候算法实现是一方面，在实际参加比赛的过程中除了算法本身的实现（特别是第三题和第四题），通过题意想到用什么算法去解决问题，这点也非常重要，当然这就需要学生题量的积累。
准备先后发布近20年信息学奥赛复赛的真题考点。包含：
系列1:
2000~2009，10年普及组复赛真题考点统计
2000~2009，10年提高组复赛真题考点统计
系列2:
2010~2019，10年普及组复赛真题考点统计
2010~2019，10年提高组复赛真题考点统计
真题考点
今天发布系列1，2000~2009这10年间信息学奥赛（NOIP）普及组和提高组复赛真题的主要考点。
普及组
年份
题目
主要考点
2000年
计算器的改良
字符串
税收与补贴问题
数学、枚举
单词接龙
深搜
乘积最大
动态规划
2001年
求先序排列
树的遍历
数的计算
动态规划
装箱问题
背包、枚举
最大公约数
和最小公倍数
数学（辗转相除法）
2002年
级数求和
枚举
过河卒
动态规划
选数
深搜、素数判定
产生数
最短路（图论）
高精度
2003年
数字游戏
动态规划
麦森数
分治、高精度
栈
数学（卡特兰数）
乒乓球
字符串
2004年
FBI 树
二叉树的遍历
不高兴的津津
枚举
火星人
数学(排列)、stl
花生采摘
贪心
2005年
采药
0/1背包
循环
高精度、数论、
快速幂
淘淘摘苹果
枚举
校门外的树
枚举
2006年
开心的金明
0/1 背包
明明的随机数
桶排序、冒泡
Jam 计数法
数学、字符串
数列
数学（进制转换）
2007年
守望者的逃离
动态规划、枚举
奖学金
快速排序
Hanoi 双塔问题
数学、高精度
纪念品分组
贪心、排序算法
2008年
ISBN 号码
字符串
排座椅
贪心
传球游戏
递推
立体图
字符输出
2009年
分数线划定
快速排序
多项式输出
字符串
细胞分裂
数论
道路游戏
动态规划
提高组
年份
题目
主要考点
2000年
进制转换
数学、字符串
乘积最大
动态规划
单词接龙
深度优先搜索
方格取数
多维动态规划
2001年
一元三次方程求解
数学、枚举
数的划分
资源分配动规
统计单词个数
字符串
Car 的旅行路线
图论
2002年
均分纸牌
模拟、贪心
字串变换
字符串、BFS
自由落体
数学、模拟
矩形覆盖
动态规划、搜索剪枝
2003年
神经网络
递推、图论
侦探推理
枚举、模拟
加分二叉树
树、区间动归
传染病控制
贪心、搜索剪枝
2004年
津津的储蓄计划
模拟
合并果子
最优哈夫曼树、
排序、贪心
合唱队形
动态规划
虫食算
搜索剪枝、模拟
2005年
谁拿了最多奖学金
模拟
过河
动态规划
篝火晚会
贪心
等价表达式
抽样检测、字符串
2006年
能量项链
区间环动规
金明的预算方案
动态规划
作业调度方案
模拟
2^k 进制数
组合数学、高精度
2007年
统计数字
排序
字符串的展开
模拟
矩阵取数游戏
区间动规、高精度
树网的核
图论、树
2008年
笨小猴
质数、字符串
火柴棒等式
枚举
传纸条
多维状态动规
双栈排序
枚举、贪心
2009年
潜伏者
字符串、模拟
Hankson 的趣味题
数论、组合数学
最优贸易
图论
靶形数独
搜索
（PS：如需这些真题的源文件，可添加文章底部作者微信，发送给需要的朋友。）
题目特点归纳
第一题：
以基础为主，基本想到解法不会太难，算法比较明，一般用模拟，或者和数学关系较直接。
第二题：
程序量要大一点，可能会用到一些基础算法，比如贪心，枚举，搜索之类。学生在做的时候有时候会遗漏考虑点。
第三题：
难度加大，会涉及到二分、动态规划之类的算法，容易遗漏考虑点，不易得全分，考试的时候要注意全面性。
第四题：
一般是压轴题，算法不明显，剪枝的搜索、动态规划、状压 DP、树形 DP 、树、图等。
重点算法归纳
总结起来想取得好的成绩，这几个相对比较重要的算法一定要学好：
枚举
枚举算法是指，列举出所有可能的取值，从中找出最优解。
模拟
模拟算法是指，通过逐步进行操作、逐步判断来推断是否符合题目中所给出的情况。非常耗时，一般不可能得到最优解，但是可以得到部分分数。
高精度
高精度一般来说会用在递推、动态规划求方案数，以及组合数学直接计算的方面。一定要熟悉高精度的加减乘，除法和求余相对出现的较少。
字符串
主要是字符串的一些相关操作和技巧。
贪心
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。在关键时刻可以做出一些避免超时的决策，在比如说搜索、动规时也可以起到相对重要的作用，大大减少状态数。
动态规划
动态规划主要的思考规律：
定义函数（动态转移方程中转移量的定义）——>建立方程——>确定初值和边界。对思维的周密程度和逻辑要求非常高。可以用来训练思维，对于学习时间短的同学，动态规划可以帮助你迅速进入编程状态，也有助于帮你发现题目背后可能隐藏的更简便的算法。动态规划、贪心都是和子问题相关的，动态规划的基本思想是将一个大的问题划分成子问题，接着分别求解，而且能够将一些重复的计算记忆化，大大提高效率。
图论
最短路和最小生成树。最短路中需要学习Dijkstra算法和Floyd算法。近年来图论题目越来越难，至少掌握这两种。最小生成树需要掌握Prim算法和Kruskal算法。前者适用于稠密图，后者适用于疏密图。两者可以比较学习，比较它们的优点和不足。
常用的数据结构
最常用到的是堆（优先队列）、并查集以及树状数组堆。堆：只关注“直系亲属关系”，不关注“旁系”。常配合贪心使用。并查集：快速判断两个元素是否有关联，增加其他算法，还可判断元素间关系。树状数组堆：平衡查询和修改的操作复杂度的一种算法，常用于解决需要查询和修改的问题。
搜索
深度优先搜索和广度优先搜索。深度优先搜索：一条路走到底。广度优先搜索：每一步将下一步的可能性放入队列中，然后按照队列顺序来探测。比赛中往往会加入很多复杂的元素。
数学知识
快速幂、高精度、筛法选素数、辗转相除法。
总结：
学生参加竞赛的时候算法实现是一方面，在实际参加比赛的过程中除了算法本身的实现（特别是第三题和第四题），通过题意想到用什么算法去解决问题，这点也非常重要，当然这就需要学生题量的积累。
