CCF青少年计算机程序设计评级标准
一级标准
1.1 定义
了解什么是计算机程序，能够编写计算机程序解决简单问题。
1.2 知识要求
1. 程序的基本结构
2. 标识符与关键字。
3. 常量和变量。
4. 算术表达式和关系表达式。
5. 整除，求余运算，常用数学函数。
6. 赋值语句，输入输入语句，复合语句，条件语句（不嵌套），循环语句（不嵌套）。
1.3 能力要求
1. 能用自然语言描述解决简单问题的方法和步骤。
2. 能用顺序、分支、循环语句实现A中的方法和步骤，编写完整的程序。
3. 初步理解算法的意义。
1.4 评价方法
1. 网络答题
2. 在指定考点考核，达到一级要求。
1.5 题例
试题名：求最小、最大数
试题描述：
给出N个数，请找出这N个数的最小数和最大数。
输入数据：
第1行，一个整数n，n<=1000。
接下来的一行，包含n个数两个数之间用一个空格分隔。
输出数据：
第1行，最小数。
第2行，最大数。
输入样例：
4
1 2 3 4
输出样例：
1
4
参考题解：
主要用两个变量min和max分别记录当前最小最大值，然后用循环边读数，边将该数与min和max比较，每次都更新最小最大值即可。
二级标准
2.1 定义
了解什么是算法，能够用程序设计语言实现简单算法，解决问题。
2.2 知识要求
1. 逻辑表达式。
2. 条件嵌套，循环嵌套，数组。
3. 枚举，简单排序，简单查找算法。
4. 素数与合数，最大公约数，最小公倍数，互质数。
2.3 能力要求
1. 能用简单枚举算法解决实际问题，能对数据进行简单排序和查找。
2. 具备独立编写和调试简短程序的能力。
2.4 评价方法
1. 网络答题。
2. 在指定考点考核，达到二级要求。
2.5 题例
试题名:求第k小数
试题描述：给出N个数，请找出第K小的数并输出该数值。
输入数据：
第1行，二个整数，n,k，n,k<=1000。
接下来的一行，包含n个数，两个数之间用1个空格分隔。
输出数据：
只有1行，为第k小数。
输入样例：
4 3
1 2 3 4
输出样例：
3
参考题解：
先对这k个数按从小到大顺序排序，则第k小的数就是数组中第k个位置的数，直接输出该数即可。
三级标准
1.1 定义
具有较强的程序实现能力，使用一种计算机程序设计语言编写程序，解决问题。
1.2 知识要求
1. 数制及其转化，信息编码，位运算。
2. 字符串类型。
3. 子程序。
4. 递归。
5. 逻辑运算，整数的质因数分解，随机函数。
6. 筛选法，欧几里德算法。
1.3 能力要求
1. 全面掌握一种计算机程序设计语言。
2. 具有运用简单数学知识编写程序解决问题的能力。
1.4 评价方法
1. 网络答题
2. 在指定考点考核，达到三级要求。
1.5 题例
试题名：分解质因数
试题描述：
给一个整数N，将N写成质因数的乘积。
输入数据：
一个整数n，n<=100000。
输出数据：
质因数的乘积表达式（请将质因数按从小到大顺序输出）。
输入样例：
12
输出样例：
12=2*2*3
参考题解：
本题可先求出N平方根范围内的素数放入数组，然后用循环将N逐个整除每个素数，若能整除，则输出该素数即可。
四级标准
1.1 定义
了解几种常用的算法，并运用这些算法编写程序，解决问题。
1.2 知识要求
1. 结构类型，文件操作。
2. 数据类型的内在含义。
3. 贪心法，递归，回溯法，模拟算法。
4. 简单的字符串处理。
5. 集合及集合的运算，加法原理与乘法原理，简单的排列和组合。
1.3 能力要求
1. 能根据实际问题选择合适的数据类型。
2. 能运用贪心、递归、回溯、模拟等算法解决实际问题。
3. 能独立设计简单的测试数据，测试自己程序的正确性。
1.4 评价方法
1. 与信息学奥林匹克全国联赛（NOIP）普及组复赛相衔接。采用上机编程考核方式，共4个试题，考试时间：3个小时。
2. 在NOIP普及组复赛中成绩列全国前70%。
1.5 题例
试题名：校门外的树
文件名：tree
试题描述：
某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0,1,2,…,L，都种有一棵树。
由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点出的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。
输入数据：
输入文件名：tree.in
第一行有两个整数L和M，L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。
输出数据：
输出文件名为tree.out。
一个整数，表示马路上剩余的树的数目。
输入输出样例：
Tree.in tree.out
500 3 298
150 300
100 200
470 471
数据规模：
1<=L<=10000，1<=M<=100
对于20%的数据，区域之间没有重合的部分；
对于其它的数据，区域之间有重合的情况。
参考题解：
本题可采用模拟法。
用一个一维数组来存放马路各位置点当前的状态；设1表示当前位置的状态为树，0来表示当前位置的状态为地铁，根据题目所给的地铁区域，可以将对应的状态区域设置0，当处理完所有的地铁区间后，再重新对整条公路的状态遍历一遍，用一个计数变量记录状态为1的个数，即为问题所求。
五级标准
1.1 定义
掌握简单数据结构知识，并结合已学算法和数学知识编写程序，解决问题。
1.2 知识要求
1. 指针类型。
2. 一般线性表，队列，堆栈，二叉树的存储和遍历。
3. 排列与组合，高精度数值处理。
4. 二分算法，快速排序，深度优先搜索，宽度优先搜索，简单动态规划。
5. 圆排列，可重集排列，鸽笼原理，素因数分解，幂函数，指数函数，对数函数，三角函数，模运算，不等式基础知识。
1.3 能力要求
1. 能运用常用算法和简单数据结构解决实际问题。
2. 能从算法本质出发，分析相关算法之间的本质联系。
3. 具备初步的数学建模能力。
1.4 评价方法
1. 与NOIP普及组复赛相衔接。采用上机编程考核方式，共4个试题，考核时间：3小时。
2. 在NOIP普及组复赛中成绩列全国前40%。
1.5 题例
试题名：摆花
文件名：flower
试题描述：
小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共m盆。通过调查顾客的喜好，小明列出了顾客最喜欢的n种花，从1到n标号。为了在门口展出更多种花，规定第i种花不能超过ai盆，摆花时同一种花放在一起，且不同种类的花需按标号从小到大的顺序依次摆列。
试编程计算，一共有多少种不同的摆花方案。
输入数据：
输入文件flower.in，共2行。
第一行包含两个正整数n和m，中间用一个空格隔开。
第二行有n个整数，每两个整数之间用一个空格隔开，依次表示a1、a2、…….an。
输出数据：
输出文件名为flower.out。
输出只有一行，一个整数，表示有多少种方案。注意：因为方案数可能很多，请输出方案数对1000007取模的结果。
输入输出样例：
flower.in flower.out
2 4 2
3 2
样例说明：有2种摆花的方案，分别是（1,1,1,2），（1,1,2,2）。括号里的1和2表示两种花，比如第一个方案是前三个位置摆第一种花，第四个位置摆第二种花。
数据范围：
对于20%数据，有0<n<=8，0<m<=8，0<ai<=8；
对于50%数据，有0<n<=20，0<m<=20，0<ai<=20；
对于100%数据，有0<n<=100，0<m<=100，0<ai<=100。
参考题解：
本题可采用简单动态规划。设f[i,j]表示前i种花放在前j个花盆里的最大方案数，那么：
f[i,j]=sum(f[i-1,j-x]) (0<=x<=min(a[i],j))
状态转移方程的含义为：前j个花盆里，第i种花最少放0个，最多放min{a[i],j}个。
其中min{a[i],j}表示第i种花的数目和花盆的数目中较少的那一个。
边界条件：f[1,j]=1 (i<=a[1])。
六级标准
1.1 定义
掌握基本的数据结构知识，能够根据实际需求设计算法编写程序，解决问题。
1.2 知识要求
1. 树、图的存储
2. 哈希表、集合数据结构
3. 图的最短路、生成树算法，有向图的拓扑排序算法。
4. 动态规划常见模型，分治策略，各种排序算法。
5. 可重集组合，二项式定理，数列与级数，归纳与递推，容斥原理，函数的连续性、函数的单调性和极值。
1.3 能力要求
1. 能对一些算法和数据结构估算时间复杂度和空间复杂度。
2. 能根据实际问题的模型选择合适的算法和数据结构来解决问题。
3. 具备知识收集和知识管理的能力。
1.4 评价方法
1. 与NOIP提高组复赛相衔接。采用上机编程考核方式，分两次测试，每次3个试题，考4个小时。共6道题，考8小时。
2. NOIP提高组复赛中成绩列全国前50%。
1.5 题例
试题名：最优贸易
文件名：trade
试题描述：
C国有n个大城市和m条道路，每条道路连接这n个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这m条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为1条。C国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。
商人阿龙来到C国旅游。当他得知同一种商品在不同城市的价格可能会不同这一消息之后，便决定在旅游得同时，利用商品在不同城市中的差价赚回一点旅费。设C国n个城市的标号1 ~n，阿龙决定从1号城市出发，并最终在n号城市结束自己的旅行。在旅游得过程中，任何城市可以重复经历多次，但不要求经过所有n歌城市。阿龙通过这些的贸易方式赚取旅费；他会选择一个经过的城市买入他最喜欢的商品——水晶球，并在之后经过的另一个城市卖出这个水晶球，用赚取得差价当做旅费。由于阿龙主要是来C过旅游，他决定这个贸易只进行最多一次，当然，在赚不到差价的情况下他就无需进行贸易。假设C国有5个大城市，城市的编号和道路连接情况如下图，单向箭头表示这条道路为单向通行，双向箭头表示这条道路为双向通行。
假设1~n号城市的水晶球价格分别为4，3，5，6，1。阿龙可以选择如下一条线路：1->2->3->5，并在2号城市以3的价格买入水晶球，在3号城市以5的价格卖出水晶球，赚取得旅费数为2。阿龙也可以选择如下一条线路：1->4->5->4->5，并在第1次到达5号城市时以1的价格买入水晶球，第2次到达4号城市时以6的价格卖出水晶球，赚取的旅费数为5。现在给出n个城市的水晶球价格，m条道路的信息（每条道路所连接的两个城市的编号以及该条道路的通行情况）。
请你告诉阿龙，他最多能赚取多少旅费。
输入数据：
输入文件为trade.in。
第一行包含2个正整数n和m，中间用一个空格隔开，分别表示城市的数目和道路的数目。第二行n个正整数，每两个整数之间用一个空格隔开，按标号顺序分别表示这n个城市的商品价格。接下来m行，每行有3个正整数，x，y，z，每两个整数之间用一个空格隔开。如果z=1，表示这条道路是城市x到城市y之间的单向道路；如果z=2，表示这条道路为城市x和城市y之间的双向道路。
输出数据：
输出文件trade.out。
共1行，包含1个整数，表示最多能赚取的旅费。如果没有进行贸易，则输出0。
输入输出样例：
trade.in trade.out
5 5 5
4 3 5 6 1
1 2 1
1 4 1
2 3 2
3 5 1
4 5 2
数据范围：
输入数据保证1号城市可以到达n号城市。
对于10%的数据，1<=n<=6。
对于30%的数据，1<=n<=100。
对于50%的数据，不存在一条旅游路线，可以从一个城市出发，再回到这个城市。
对于100%的数据，1<=n<=100000，1<=m=500000，1<=x，y<=n，1<=z<=2，1<=各城市水晶球价格 <=100。
参考题解：
此题方法有很多，下面介绍两种方法。
方法1：
将图中圈缩成点，变成一个有向无环图。
设f(i)表示i点的最低买入价，g(i)表示i点的最高卖出价。
从左至右做简单动态规划，f(i)=min{f[j],a[i]}，其中j到i有弧，意思是当前的最低买入价，要么是前面城市的最低买入价，要么就是当前城市的价格。
然后从右至左再进行简单动态规划。f(i)=max{f[j],a[i]}，其中i到j有弧，意思是当前的最高卖出价，要么是后面城市的最低卖出价，要么就是当前城市的价格。
答案就是对所有城市求出最大差价，即ans=max{g(i)-f(i)}。
方案2：
从起始城市开始，到目标城市结束，沿着正向弧用spfa求出每个城市的最大买入价。
从目标城市开始，到起始城市结束，沿着逆向弧用spfa求出每个城市的最大卖出价。
答案就是对所有城市求出最大差价，即ans=max{g(i)-f(i)}。
七级标准（NOIP提高组全国前20%）
定义：综合运用算法和数据结构编写程序，解决问题。
知识要求：
1、 并查集，线段树，哈弗曼树，二叉排序树，二叉堆。
2、 图的连通性算法，最短路，最小生成树的优化算法，二分图的构造、判定及匹配，搜索算法的优化，扩展欧几里得算法。
3、 中国剩余定理，剩余类，概率基础知识，解析几何基础知识。
能力要求：
1、 能根据时间和空间复杂度的要求灵活构造算法和数据结构解决实际问题。
2、 具备较强的程序代码实现能力。
3、 具备较强的归纳、总结和表达能力。
题例：
试题名：关押罪犯
详见NOIP2010提高组
八级标准（NOI铜牌）
定义：掌握高级数据结构知识，能运用恰当算法编写程序，解决较复杂问题。 知识要求：
1、 树状数组，字典树，优先队列，平衡树。
2、 网络流算法，复杂的分治思想，树形动态规划，状态压缩动态规划，二分图的匹配，启发式搜索。
3、 矩阵概念及其基本运算，线性方程组的解法，迭代法，费马小定理和欧拉定理，母函数。
能力要求：
1、 能针对复杂问题建立清晰的数学模型。
2、 能运用数学知识、高级数据结构和算法解决复杂的问题。
3、 能根据需要，开展基于写作的学习和研究。
题例：
试题名：能量采集
详见NOI2010
九级标准（NOI银牌）
定义：具有对问题进行抽象和数学建模能力，能选用合适的数据结构和算法编写程序，解决较难问题。
知识要求：
1、 块状链表，后缀数组，后缀树，复杂的线段树。
2、 动态规划优化，模拟退火算法。
3、 计算几何基础知识（点积、叉积、凸包、半平面等知识及应用），数学期望。
能力要求：
1、 能针对疑难问题建立清晰的数学模型。
2、 能灵活运用数学知识、高级数据结构和算法解决疑难问题。
3、 具备发现问题、解决问题的探索研究能力。
题例：
试题名：直线和点
文件名：line
试题描述：
平面的n条直线将平面分割成了若干区域，给出m个点，求每个点所在区域
的面积。
为了防止出现面积无穷大的情况，有额为的四条直线框定了平面区域的大小，
分别是x=L，y=L，x=-L，y=-L。其中L是给定的正实数，所有的点都在这个框定的区域内。
另外为了防止精度问题，任意一个点到任意一条直线的距离>10^-7。
输入数据：
输入文件名为line.in。
第一行两个正整数和一个正实数，n,m,L，意义如上所述。
第2~n-1行每行三个实数A，B，C表示直线的方程为Ax+By+C=0。 第n+2~n+m+1行每行两个实数x,y表示点的坐标。
输出数据：
输出文件名为line.out。
按输入的顺序输出每个点所在的区域面积，每个一行，保留2为小数。 输入样例：
2 4 3
1 1 -1
-1 1 -1
0 2
-2 1
2 1
0 0
输出样例：
4.00
8.50
8.50
15.00
数据范围：
对于20%的数据，n,m<=10。
对于40%的数据，n,m<=300。
对于100%的数据，n<=500,m<=100000。
对于100%的数据，输入数据的绝对值<=10^7且最多保留2位小数
十级标准（NOI金牌）
定义：具有一定的提出问题、解决问题的研究能力，能构造算法与数据结构，解决开放性问题。
知识要求：
1、 最小树形图，自动机，动态树，树套树，一般图的匹配。
2、 双重动态规划，基于连通性的动态规划，线性规划，极大极小搜索算法。
3、 三维计算几何，组合游戏中的NIM问题和SG函数，群的概念，置换群，Burnside引理，Polya原理，莫比乌斯反演定理，FFT。
能力要求
1、 具备创造性地运用数据结构和算法解决开放性问题的能力。
2、 具备很强的代码编写能力。
3、 具备提出问题、并开展相关研究的创新能力。
题例：
试题名：管道取珠
详见NOI2009