中学生程序设计十级（2013APOI会议纪要）

CCF中学生计算机程序设计水平评价体系（初稿）

CCF中学生计算机程序设计水平评价体系初稿

（2013年5月11日）

目 录

一级……………………………………………………………………2 二级……………………………………………………………………5 三级……………………………………………………………………7 四级……………………………………………………………………12 五级……………………………………………………………………15 六级……………………………………………………………………20 七级……………………………………………………………………22 八级……………………………………………………………………24 九级……………………………………………………………………27 十级……………………………………………………………………31

1

CCF中学生计算机程序设计水平评价体系（初稿）

一、二、三级评价描述 福建省福州第一中学 陈颖 东北育才中学 邱桂香

CCF中学生计算机程序设计水平评价体系建设目标

建立一个规范的、科学的学习和评价机制，让更多的青少年了解计算思维，培养青少年对计算机科学的兴趣，促进兴趣计算机科学的青少年健康发展。

评价机制

中学生计算机程序设计水平分十个级别，一、二、三级采用笔试形式，评价学生对计算机解决问题过程的理解程度；四、五、六、七级采用上机编程的形式，评价学生灵活运用基础算法解决问题的能力；八、九、十采用上机编程的形式，评价学生综合应用数据结构和算法高效解决问题的能力。

评价描述

一 级

1、 定义

初步具备程序设计思想，理解利用计算机解决问题的基本过程。 2、 知识要求 （1） 数制。 （2） 逻辑运算。

（3） 运用顺序结构、分支结构、循环结构描述解决简单问题。

（4） 掌握一种计算机语言[1]，运用输入、输出、赋值、分支、循环语句编

写解决简单问题的程序。

（5） 理解整型、实型、字符型、布尔型和一维数组的应用。 3、 能力要求

看懂简单问题的分析过程，读懂简单程序。 4、 考核办法

（1）纸质笔试。

（2）题型：单选题、问题求解、阅读程序、完善算法或程序。

2

CCF中学生计算机程序设计水平评价体系（初稿）

（3）接轨信息学奥赛普及组[2]初赛。

（4）成绩要求：参加普及组初赛考核成绩达60分以上者，即一级水平试题占普及组初赛试卷60%。 5、 对应题例[3] （一）单选题

（1）数制类题

如：下列无符号数中，最小的数是（ ）。

A．（11011001）2 B．（75）10 C．（37）8 D．（2A）16 （2）程序设计基础知识类题 如：算法是指（ ）。

A．为解决问题而编制的计算机程序 B．为解决问题而采取的方法与步骤

C．为解决问题而需要采用的计算机语言 D．为解决问题而采用的计算方法

（3）逻辑运算类题

如：假设A=true，B=false，C=true，D=true，逻辑运算表达式A∧B∨C∧D的值是( )。

A．true B.false C.0 D.1 （二）问题解答

求解给定的与程序设计思维有关的问题。

如：任给自然数n，k， 1≤K≤9 ，按如下计算步骤求序列XJXJ-1……X0的步骤：

（1） j=0

（2） 如果N>=K 则转第3步，否则转第7步

（3） Xj = N MOD K {div表示整数除法，结果取

整数；

（4） N =N DIV K mod表示整除取余数} （5） j=j+1 （6） 回第2步

3

CCF中学生计算机程序设计水平评价体系（初稿）

（7） Xj = N （8） 结束

试求当： N=1998， K=3时，XJXJ-1……X0 之值。

（三）阅读程序写结果

只有一个主程序，含顺序结构、分支结构和循环结构，最多涉及一维数组。 （四）完善程序

完善简单问题的程序，问题用一个主程序，使用输入、输出、赋值、分支、循环语句，最多涉及一维数组即可解决。填空的选择重点考查学生对程序设计语言语句的正确表达。

如：判断质数问题 题目描述:

给出一个正整数，判断这个数是否是质数。 输入:

一个正整数n(1 ≤ n ≤ 10000)。 输出:

如果n是质数，输出”YES”；否则，输出”NO”。 输入样例: 10 输出样例: NO 程序填空： #include int main() { int ① ;

scanf(\if (n == 2) puts( ② );

else if ( ③ || n % 2 == 0) puts(\else { i = 3;

4

CCF中学生计算机程序设计水平评价体系（初稿）

while (i * i <= n) { if ( ④ ) {

puts(\} i = i + 2; }

puts(\} return 0; }

二 级

1、 定义

系统掌握一种程序设计语言，理解程序设计过程中算法设计的重要性。 2、 知识要求

（1） 理解多维数组的应用。

（2） 理解过程、函数在程序设计中的作用。 （3） 理解递归思想及程序实现过程。

（4） 理解枚举、模拟、贪心、递推、顺序查找、折半查找、选择排序、冒

泡排序、插入排序算法的简单应用。 （5） 理解运用数学知识对算法效率的影响。 3、 能力要求

看懂问题分析和程序描述中用到的简单算法。读懂包含过程函数的程序。 4、 考核办法

（1）纸质笔试。

（2）题型：单选题、问题求解、阅读程序、完善算法或程序。 （3）接轨信息学奥赛普及组和提高组[4] 初赛。

（4）成绩要求：参加普及组考核成绩达80分以上者。参加提高组考核成绩达60分以上者。

5

CCF中学生计算机程序设计水平评价体系（初稿）

（5）提高组试题中60%来自普及组试题，即一级、二级水平试题占提高组初赛试卷60%。 5、 对应题例 （一）单选题

增加对算法的理解问题。

如：某数列有1000个各不相同的单元，由低至高按序排列；现要对该数列进行二分法检索(binary search)，在最坏的情況下，需检视( )个单元。 A．1000 B. 10 C. 100 D. 500 （二）问题解答

求解给定的问题，侧重问题分析过程中数学知识的应用。

如：现在市场上有一款汽车A很热销，售价是2万美元。汽车A每加仑汽油可以行驶20英里。普通汽车每年大约行驶12000英里。油价是每加仑1美元。不久我公司就要推出新款节油汽车B，汽车B每加仑汽油可以行驶30英里。现在我们要为B制定价格(它的价格略高于A)：我们预计如果用户能够在两年内通过节省油钱把B高出A的价钱弥补回来，则他们就会购买B，否则就不会购买B。那么B的最高价格应为 万美元。 （三）阅读程序写结果

含多维数组、递归函数的程序。 （四）完善算法、完善程序

理解问题分析和程序设计中的用到的算法思想。填空的选择重点考查学生对解决问题算法的理解。

如：已知：A1，A2，……，A81 共有81个数，其中只有一个数比其它数大，要用最少的比较运算次数，把这个值大的数找出来（假设两个数比较一次能决定出大于、小于或等于这三种情况）请将以下算法补充完整：

第一步： S1 = A1 + A2 + …… + A27 S2 = A28 + A29 +……+ A54 第一次比较（S1，S2） ： S1 > S2 取 K=0 S1 < S2 取 K=27

6

CCF中学生计算机程序设计水平评价体系（初稿）

S1 = S2 取 K=54 第二步： S1 = AK+1 + AK+2 + …… + AK+9

S2 = AK+10 + AK+11 +……+ AK+18 第二次比较（S1，S2） ： S1 > S2 取 K= S1 < S2 取 K= S1 = S2 取 K= 第三步： S1 = AK+1 + AK+2 + AK+3

S2 = AK+4 + AK+5 + AK+6 第三次比较（S1，S2） ： S1 > S2 取 K= S1 < S2 取 K= S1 = S2 取 K= 第四步： S1 = AK+1

S2 = AK+2

第四次比较（S1，S2） ：

S1 > S2 为最大数 S1 < S2 为最大数， S1 = S2 为最大数。

三 级

1、 定义

具备一定的数据结构、组合数学知识，理解数据结构在程序设计中的作用。 2、 知识要求

（1） 理解栈、队列的思想及其简单应用。 （2） 了解树、图的基本概念。

（3） 理解深度优先搜索、广度优先搜索思想及简单应用。 （4） 理解筛法思想及简单应用。 （5） 理解指针的作用及简单应用。

7

CCF中学生计算机程序设计水平评价体系（初稿）

（6） 运用高中数学中的排列、组合知识分析求解问题。 3、 能力要求

看懂问题分析和程序描述中的算法思想，读懂包含数据结构简单应用的程序。 4、 考核办法 （1）纸质笔试。

（2）题型：单选题、问题求解、阅读程序、完善算法或程序。 （3）接轨信息学奥赛提高组初赛。

（4）成绩要求：参加提高组初赛成绩达80分以上者。 （5）三级水平占提高组初赛试卷40%。 5、 对应题例 （一） 单选题

增加数据结构知识题。

如：设循环队列中数组的下标范围是1–n，其头尾指针分别为f和r，则其元素个数为（ ）．

A．r- f B．r- f +1 C.（r- f ） MOD n+1 D．（r- f + n） MOD n （二）问题解答

求解给定的问题，侧重数据结构、组合数学知识的应用。

如：如下图,有一个无穷大的的栈S,在栈的右边排列着1,2,3,4,5共五个车厢。其中每个车厢可以向左行走,也可以进入栈S让后面的车厢通过。现已知第一个到达出口的是3号车厢，请写出所有可能的到达出口的车厢排列总数(不必给出每种排列)。

出口←

（三）阅读程序写结果 含算法思想的程序。 （四）完善程序

← S↓

1 2 3 4 5

8

CCF中学生计算机程序设计水平评价体系（初稿）

理解数据结构、深度优先搜索、广度优先搜索的应用。填空的选择重点考查学生正确表达解决问题算法的能力。

如： (国王放置) 在n*m的棋盘上放置k个国王，要求k个国王互相不攻击，有多少种不同的放置方法。假设国王放置在第(x,y)格，国王的攻击的区域是:(x-1,y-1), (x-1,y),(x-1,y+1),(x,y-1),(x,y+1),(x+1,y-1),(x+1,y),(x+1,y+1)。读入三个数n,m,k，输出答案。题目利用回溯法求解。棋盘行标号为0~n-1，列标号为0~m-1。 程序填空： #include #include int n,m,k,ans; int hash[5][5];

void work(int x,int y,int tot){ int i,j; if (tot==k){ ans++; return;

} do{ while (hash[x][y]){ y++; if (y==m){ x++;

y= ① ; } if (x==n)

return; }

for (i=x-1;i<=x+1;i++)

if (i>=0&&i

9

CCF中学生计算机程序设计水平评价体系（初稿）

}

for (j=y-1;j<=y+1;j++)

if (j>=0&&j

② ;

③ ; for (i=x-1;i<=x+1;i++)

if (i>=0&&i

for (j=y-1;j<=y+1;j++)

if (j>=0&&j

④ ;

y++; if (y==m){ } if (x==n)

return; x++; y=0;

while (1); } int main(){

scanf(\ ans=0;

memset(hash,0,sizeof(hash)); ⑤ ; printf(\ return 0; }

注：

10

CCF中学生计算机程序设计水平评价体系（初稿）

[1]讨论不同级别对计算机语言的选择。对于语言要求是否可以不用一刀切。如：1、2、3级可以使用c++\\c\\pascal\\vb，4、5、6、7可以使用c++\\c\\pascal，8、9、10级使用c++\\c。

[2]1、2、3级描述中对应题例样例均选自历届NOIP初赛试卷。 [3]普及组主要参加对象为在校的初中生，接受小学生参加。 [4]提高组主要参加对象为在校的高中生，接受初中学生参加。

11

CCF中学生计算机程序设计水平评价体系（初稿）

四、五级评价描述 绍兴一中 陈合力 绍兴县柯桥中学 吴建峰

四 级

一、等级定义

1. 对应于CCF举办的NOIP普及组复赛，等级水平高于“三级”。在没有特殊说明情况下，“四级”包含“三级”所要求的所有知识和能力。

2. 熟练掌握一种计算机程序设计语言，能运用各种常用算法编程并解决实际问题。

二、知识要求

1. 熟练掌握操作系统中文件及文件夹的操作（如，“新建文件和文件夹”、“文件和文件夹重命名”和“文件和文件夹的复制粘贴”等）。

2. 熟练掌握在计算机程序中实现文本文件的信息输入和输出操作。 3. 能灵活运用顺序、分支、循环结构编写程序解决实际问题。 4. 能理解并在计算机程序中应用一维及多维数组。

5. 掌握常见的基本数据类型（整型、长整型、64位整型、实型、布尔型、字符串）及其应用。

6. 掌握下列算法的本质并能用程序代码实现 （1）穷举法 （2）贪心法 （3）递推 （4）简单的递归 （5）冒泡、选择排序算法 （6）顺序查找算法 （7）回溯法

（8）深度优先搜索法和宽度优先搜索法 （9）分治法

12

CCF中学生计算机程序设计水平评价体系（初稿）

（10）模拟法

（11）简单的字符串处理 三、能力要求

1. 能根据实际问题特点设计解决问题所需的算法与数据结构。

2. 能将解决问题所需的算法与数据结构用程序代码（PASCAL、C或者C++）实现。

3. 能独立设计简单的测试数据，测试自己程序的正确性。

4. 能根据程序运行时出现的错误信息提示，针对性地修改调试程序。 四、考核方案

1. 申请四级等级证书的选手必须在当年参加CCF组织的NOIP普及组初赛全国统一考试并取得当年NOIP普及组复赛资格。

2. 由CCF根据当年全国复赛总体情况划定全国统一的“四级”分数线，在普及组复赛中分数达到分数线者即可获得“四级证书”。

3. 获得“四级证书”相应的比赛（NOIP普及组复赛）形式：采用上机编程形式，试卷共包含4个问题，选手在3.5小时内完成比赛。 五、对应例题

例1：不高兴的津津(unhappy.pas/c/cpp) 【问题描述】

津津上初中了。妈妈认为津津应该更加用功学习，所以津津除了上学之外，还要参加妈妈为她报名的各科复习班。另外每周妈妈还会送她去学习朗诵、舞蹈和钢琴。但是津津如果一天上课超过八个小时就会不高兴，而且上得越久就会越不高兴。假设津津不会因为其它事不高兴，并且她的不高兴不会持续到第二天。请你帮忙检查一下津津下周的日程安排，看看下周她会不会不高兴；如果会的话，哪天最不高兴。 【输入文件】

输入文件unhappy.in包括七行数据，分别表示周一到周日的日程安排。每行包括两个小于10的非负整数，用空格隔开，分别表示津津在学校上课的时间和妈妈安排她上课的时间。 【输出文件】

13

CCF中学生计算机程序设计水平评价体系（初稿）

输出文件unhappy.out包括一行，这一行只包含一个数字。如果不会不高兴则输出0，如果会则输出最不高兴的是周几（用1, 2, 3, 4, 5, 6, 7分别表示周一，周二，周三，周四，周五，周六，周日）。如果有两天或两天以上不高兴的程度相当，则输出时间最靠前的一天。 【样例输入】 5 3 6 2 7 2 5 3 5 4 0 4 0 6

【样例输出】 3

例2：校门外的树(tree.pas/c/cpp) 【问题描述】

某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。

由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。 【输入文件】

输入文件tree.in的第一行有两个整数L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。

14

CCF中学生计算机程序设计水平评价体系（初稿）

【输出文件】

输出文件tree.out包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。 【样例输入】 500 3 150 300 100 200 470 471 【样例输出】 298

【数据规模】

对于20%的数据，区域之间没有重合的部分； 对于其它的数据，区域之间有重合的情况。

五 级

一、等级定义

1. 对应于CCF举办的NOIP普及组复赛，等级水平高于“四级”。在没有特殊说明情况下，“五级”包含“四级”所要求的所有知识和能力。

2. 在掌握运用各种算法并熟练编程的基础上，初步具备复杂问题的建模能力、算法时空效率的分析意识和优化能力。 二、知识要求

1. 掌握构造类数据类型（如，记录数组）的原理，并能在实际应用中编程实现。

2. 掌握滚动数组的原理，并能在实际应用中编程实现。

3. 掌握动态数据结构（指针类型）的原理与方法，并能在实际应用中编程实现。

4. 掌握队列和堆栈的数据结构原理和存储方法，并能在实际应用中编程实现队列和堆栈的维护操作。

5. 掌握二叉树、多叉树、森林的存储和遍历原理，并能用代码实现二叉树存储与遍历。

15

CCF中学生计算机程序设计水平评价体系（初稿）

五、对应题例 1． 证明）

题目大意：N个数对(xi, yi)，将它们按一定顺序排列，使得 max { Pi{xk, k = 0..i-1} / yi } 尽量小（N <= 1000, 0 < xi, yi < 10000）

2．关押罪犯 （NOIP 2010 提高组，考察点：二分答案，二分图判定，排序，并查集）

题目大意：将N个罪犯分在两个监狱里。M对罪犯之间存在仇恨值。要求同一个监狱中的任意两个罪犯之间的仇恨值的最大值尽量小（N <= 20000, M <= 100000, 仇恨值不超过10^9）。

3． Hankson的趣味题 （NOIP 2009 提高组，考察点：数论，筛法求素数，算数基本定理，组合数学，乘法原理）

题目大意：

N次询问，每次查询与a0的最大公约数是a1且与b0的最

国王的游戏 （NOIP 2012 提高组，考察点: 贪心，高精度，猜想与

小公倍数是b1的正整数的个数（N <= 2000, 1 <= a0, a1, b0, b1 <= 2*10^9）。

4．侦探推理 （NOIP 2003 提高组，考察点：枚举，字符串处理） 题目大意：

M个人提供了P个证词。每个有效证词的形式为：今天是星

期几；我/XX是/不是凶手。已知N个人始终说谎，其他人始终说真话，且凶手只有一个。求凶手是谁。

21

CCF中学生计算机程序设计水平评价体系（初稿）

七 级

一、标准描述

熟悉图论的经典算法，掌握搜索的剪枝技巧，拥有动态规划的思想，并具备优化算法的能力。

二、知识要求

1. 掌握搜索算法的剪枝和优化，熟悉深度优先搜索、广度优先搜索，知道启发式搜索、双向搜索、迭代加深搜索等不同的搜索方法。

2. 了解动态规划的一般思想，知道在序列、树等不同数据结构中设计动态规划算法的一般方法，能使用数据结构等技巧优化动态规划算法的时间和空间复杂度，如前缀和、滚动数组、单调队列等。知道多进程动态规划，树形动态规划，状态压缩动态规划等较复杂的动态规划方法。

3. 熟悉图论的经典算法，如最小生成树问题的Prim和Kruskal算法，最短路问题的Floyd，Bellman_Ford和Dijkstra算法，二分图最大匹配问题的匈牙利算法，有向图的拓扑排序算法等。

4. 了解一些较复杂的数据结构，如散列表、并查集、字母树、二叉堆、线段树、倍增算法等，熟悉这些数据结构的性质和用途，能应用它们优化算法的时间效率。

5. 了解相关的数学知识。知道组合数学中的鸽巢原理、容斥原理。知道数论中的质数相关的欧拉定理和费马小定理，以及扩展欧几里得算法、（中国剩余定理）等重要知识。知道图论中无向图的割点、桥、点和边的双连通分量，有向图的强连通分量、拓扑排序等知识。对概率论、博弈论、线性代数等有一定的了解。

6. 初步了解算法复杂度，P和NP，NPC问题等概念。对计算机科学领域有大致的整体的认识。

三、能力要求

1. 灵活地确定搜索策略并能确定恰当的优化策略； 2. 熟练应用动态规划策略解决问题； 3. 能恰当选用图论算法并高效解决问题；

4．具有较强的观察、猜测、联想、类比、推导等思维能力，能迅速地从复杂的问题中提炼有效信息，建立数学模型；

22

CCF中学生计算机程序设计水平评价体系（初稿）

四、考核办法 1．形式：上机编程 2．题型：程序设计

3．目标：信息学分区联赛提高组一等奖 4．成绩要求：获取80%以上分数

五、对应题例

1． 疫情控制 （NOIP 2012 提高组，考察点：贪心，二分答案，数据结构） 题目大意：一个N个点的有根树，点1为根。有M支军队，已知分别驻扎在哪个点。要求将这M支军队重新调动，使得根到任意一个叶子节点的路径上至少经过一个驻扎军队的点。但是根节点不能驻扎军队。在此基础上，要求移动距离最远的军队的移动距离尽量小（N, M <= 50000. w < 10^9）。

2． 2^k进制数 （NOIP 2006 提高组，考察点：递推优化，高精度） 题目大意：求2^k进制数中，至少是两位数、且从高位向低位的数字递增、且化成2进制以后不超过w位的数的数目（1 <= k <= 9, k < w <= 30000）。

3．Mayan游戏 （NOIP 2011 提高组，考察点：搜索，剪枝） 题目大意：

宽度为5，高度为7的棋盘。堆放着一些方块。每列的每个

方块（除最底层外）下方必须有方块。方块有颜色。一次操作可以将任意一个方块向左或向右拖动一格。如果目标位置有方块则交换，否则方块会下落，原来上方的方块也会下落。任一时刻，若一行或一列上有连续的不少于3个相同颜色方块，就会同时消掉。消掉以后，可能会引起方块下落，还可能产生新的消除。给出一个局面和限定操作次数n，求一组字典序最小的解。

4．引水入城 （NOIP 2010 提高组，考察点：猜想与证明，深度和广度优先遍历，贪心，动态规划）

题目大意：N*M的矩阵。每个格子有高度。第一行可以建蓄水厂。如果一个格子四周有比它高的格子修建了水利设施，那么可以在这个格子建输水站。要求在第一行选择尽量少的点修建蓄水厂，使得第N行的每个格子都能修建输水站。如果无合法方案，求第N行最少有几个格子不可能修建输水站（N, M <= 500）。

23

CCF中学生计算机程序设计水平评价体系（初稿）

八、九、十级评价描述 杭州学军中学 徐先友 雅礼中学 朱全民 常州高级中学 曹文

八 级

对应信息学竞赛的难度：NOI铜牌 一、标准描述

熟练掌握高级数据结构、各种常见的算法，具有较强的数学建模能力，能解决比较复杂的问题。

二、知识要求

1、数学知识：

（1）基本函数：幂函数、指数函数、对函数、三角函数、母函数；

（2）数论：倍数和因数、素数与合数，整除，集合论，关系，素数，费马定理，进位制及

转换，辗转相除，扩展的辗转相除，欧拉筛法求素数、快速幂、同余运算，解线性同

余方程，中国剩余定理，离散对数 （3）数学归纳法

（4）几何：平面几何，解析几何；

（5）概率论：普通概率，条件概率，Bayes定理，期望计算； （6）离散数学；

（6）数学分析：基础微积分 （7）线性代数；

（8）组合数学：排列与组合，鸽笼原理，容斥原理，递推； 2、算法：

（1）高精度：+，-，*，/ （2）分治算法：二分，三分

（3）动态规划:树形动态规划，状态压缩动态规划，动态规划优化（包括决策单调 性，单调队列，四边形不等式，凸完全单调性） （4）搜索及搜索的优化 （5）博弈论，SG函数

（6）图论：连通性问题：求强连通分量，求割点和桥，欧拉回路，拓扑排序，AOV 问题，AOE问题，2-SAT问题判定和求解， 最小生成树（Kruskal,Prim）

最短路（Dijkstra，Bellman-Ford，SPFA，Floyd，标号法）

验证二分图，Konig定理，匈牙利算法，二分图最大权匹配(KM算法) （7）网络流算法：建模，最大流最小割（EK，Dinic，SAP），分数规划

24

CCF中学生计算机程序设计水平评价体系（初稿）

（8）简单计算几何算法：平面解几及其应用，向量，点积及其应用，叉积及其应用求点集的凸包，最近点对问题，离散化与扫描 （9）字符串的最小表示

（10）矩阵表示线性变换，行列式求值 3、数据结构：

（1）基本数据结构：队列，栈，二叉查找树

（2）指针：链表，邻接表，二叉树的表示，多叉树的表示

（3）字符串处理：字典树，KMP，AC自动机，Huffman编码，字符串hash（RabinKarp) （4）二叉堆 （5）并查集 （6） .线段树 （7）树状数组

三、能力要求

1、程序调试能力 2、测试数据设计能力 3、问题抽象能力 4、数学建模能力

5、算法和数据结构设计能力

四、考核办法 1、形式

采用集中竞赛的方式，对给出3—6个试题，采用上机编写程序的方法，在一定的时限内完成，用测试数据的方法进行检测。 2、目标要求

累计250分的选手。

五、题例

直线和点

平面的n条直线将平面分割成了若干区域，给出m个点，求每个点所在区域的面积。 为了防止出现面积无穷大的情况，有额外的四条直线框定了平面区域的大小，分别是x=L y=L x=-L y=-L。其中L是给定的正实数，所有的点都在这个框定的区域内。 另外为了防止精度问题，任意一个点到任意一条直线的距离>10^-7。

25

CCF中学生计算机程序设计水平评价体系（初稿）

输入格式

第一行两个正整数和一个正实数，n,m,L，意义如上所述。

第2~n-1行每行三个实数A,B,C表示直线的方程为Ax+By+C=0。 第n+2~n+m+1行每行两个实数x,y表示点的坐标。

输出格式

按输入的顺序输出每个点所在的区域面积，每个一行，保留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。

26

CCF中学生计算机程序设计水平评价体系（初稿）

对于100%的数据，输入数据的绝对值<=10^7且最多保留2位小数。

解题报告

首先我们要确定每个点所在的区域位置，我们使用扫描线的方法去处理这个问题。先求出所有直线两两之间的交点，按它们的x轴坐标排序。用一条平行于y轴的扫描线从左向右扫描，维护所有直线与这条扫描线交点的有序序列。如何维护呢？只要当扫面线扫到某两条直线的交点时，交换这两条直线的位置即可。维护了所有直线的有序序列之后，我们就可以使用二分来比较轻松地计算出每个点所在的区域了。那如何计算面积呢？

我们将区域从上往下编号。我们发现，当扫描线经过上面两条直线的交点时，有3个区域发生的变化，分别是一号区域，二号区域和三号区域。一号区域的下边界“转弯”了，三号区域的上边界“转弯”了，对于这两个区域，只要用叉积把这条边的面积计入这个区域的总面积就好了。而我们发现，二号区域在经过这个交点后结束了，然后又出现了一个新的二号区域。所以我们要将原来的二号区域面积计算出来，然后更新那些在二号区域内的点的答案。

程序（略）

九 级

对应信息学竞赛的难度：NOI银牌

一、标准描述

熟练掌握并能灵活运用高级数据结构、各种常见的算法，有很强的数学建模能力，具备比较强的构造算法的能力，能解决复杂的问题。 二、知识要求

27

CCF中学生计算机程序设计水平评价体系（初稿）

6. 数学知识：

（1）基本函数：幂函数、指数函数、对函数、三角函数、母函数；

（2）数论：倍数和因数、素数与合数，整除，集合论，关系，素数，费马定理，进位制及

转换，辗转相除，扩展的辗转相除，欧拉筛法求素数、快速幂、同余运算，解线性同

余方程，中国剩余定理，离散对数 （3）数学归纳法

（4）几何：平面几何，解析几何，斜影几何；

（5）概率论：普通概率，条件概率，Bayes定理，期望计算； （6）离散数学；

（7）数学分析：基础微积分 （8）线性代数；

（9）组合数学：排列与组合，鸽笼原理，容斥原理，递推，差分序列，生成函数， 置换，Burnside引理，Polya原理，组合游戏SG定理 （10）群论；

2、算法：

（1）高精度：+，-，*，/及压位技巧 （2）分治算法：二分，三分

（3）动态规划:树形动态规划，状态压缩动态规划，动态规划优化（包括决策单调性，单调队列，四边形不等式，凸完全单调性） （4）搜索及搜索的优化 （5）博弈论，SG函数

（6）图论：连通性问题：求强连通分量，求割点和桥，欧拉回路，拓扑排序，AOV 问题，AOE问题，2-SAT问题判定和求解，

最小生成树（Kruskal,Prim）

最短路（Dijkstra，Bellman-Ford，SPFA，Floyd，标号法）

差分约束系统 验证二分图，Konig定理，匈牙利算法，二分图最大权匹配(KM算法)

（7）网络流算法：建模，最大流最小割（EK，Dinic，SAP），费用流，分数规划， 有上下界的网络流

（8）计算几何算法：平面解几及其应用，向量，点积及其应用，叉积及其应用，求 点集的凸包，最近点对问题，离散化与扫描，凸多边形的交，半平面相交，高 维凸包，圆并 （9）字符串的最小表示

（10）矩阵表示线性变换，行列式求值，矩阵求逆，矩阵乘法的优化 （11）基础随机化算法

数据结构：

28

CCF中学生计算机程序设计水平评价体系（初稿）

（1）基本数据结构：队列，栈，二叉查找树

（2）指针：链表，邻接表，二叉树的表示，多叉树的表示

（3）字符串处理：字典树，KMP，AC自动机，Huffman编码，字符串hash（RabinKarp) 有限状态自动机，后缀树组，后缀树 （4）二叉堆及启发式合并 （5）并查集（tarjan算法） （6）树状数组，线段树

（7）平衡树（Treap，AVL，SBT，Splay）

（8）树分治算法：点剖分，边剖分，树链剖分，轻重边权划分

三、能力要求

1、程序调试能力 2、测试数据设计能力 3、问题抽象能力 4、数学建模能力

5、算法和数据结构设计能力 6、算法优化能力

四、考核办法 1、形式

采用集中竞赛的方式，对给出3—6个试题，采用上机编写程序的方法，在一定的时限内完成，用测试数据的方法进行检测。 2、目标要求

累计500分的选手。

五、题例 防守战线

【题目描述】

战线可以看作一个长度为n 的序列，现在需要在这个序列上建塔来防守敌 兵，在序列第i 号位置上建一座塔有Ci 的花费，且一个位置可以建任意多的塔， 费用累加计算。有m 个区间[L1, R1], [L2, R2], …, [Lm, Rm]，在第i 个区间 的范围内要建至少Di 座塔。求最少花费。 【输入格式】

输入文件defend.in 中，第一行为两个数n, m。 接下来一行，有n 个数，描述C 数组。

接下来m 行，每行三个数Li,Ri,Di，描述一个区间。 【输出格式】

输出文件defend.out 中，仅包含一行，一个数，为最少花费。 【输入样例】 5 3

1 5 6 3 4 2 3 1 1 5 4 3 5 2

29

CCF中学生计算机程序设计水平评价体系（初稿）

【输出样例】 11

【样例说明】

位置1 建2 个塔，位置3 建一个塔，位置4 建一个塔。花费1*2+6+3=11。 【数据规模】

对于20%的数据，n≤20，m≤20。

对于50%的数据（包括上部分的数据），Di 全部为1。 对于100%的数据,n≤100，m≤1000。

解题报告

对于样例我们可以列出如下的线性规划式子 x2 + x3 >= 1

x1 + x2 + x3 + x4 + x5 >= 4 x3 + x4 + x5 >= 2

1x1 +5x2 +6x3 +3x4 +4x5 最小化

我们使用极大-极小定理 转换为其对偶型

x2 <= 1 x1 + x2 <= 5 x1 + x2 + x3 <= 6 x2 + x3 <= 3 x2 + x3 <= 4

1x1 +4x2 +2x3 最大化

观察一下这些不等式 和NOI2008 employee非常相似！

我们考虑其现实意义：给定M种志愿者，第i种工作区间是[Li, Ri]，雇佣一次Ci块。现在要保证第j天最多雇佣Dj个人，求最大总费用。

这个问题还是很困难，但是我们有经典做法！费用流！（详见employee题解）

我们仅给出一些变形后的不等式 其含义见employee的题解

x2+y1=1

x1+x2+x3+y2=5 x1+x2+x3+y3=6 x2+x3+y4=3 x2+x3+y5=4

30

CCF中学生计算机程序设计水平评价体系（初稿）

//设置松弛变量

x2+y1=1

x1+x3+y2-y1=4 y3-y2=1

-x1+y4-y3=-3 y5-y4=1 -x2-x3-y5=-4

但是考虑到这里需要求最大费用流，有没有可能需要考虑负圈的问题？ 不需要！

这里和原题的区别在于 原题的约束是>=这里是<=

所以设置的松弛变量的符号的恰好反过来 变成先正再负

也即所有变量的连边都是从编号小的不等式流向编号大的不等式 那么初始图是一张拓扑图 这样就可以很轻松求 得最大费用流了。

程序（略）

十 级

对应信息学竞赛的难度：NOI金牌

一、标准描述 能综合灵活运用高级数据结构、各种常见的算法，具备设计新型数据结构，灵活构造算法的能力，有提出并解决难题的能力。

二、知识要求

1、数学知识

（1）基本数论 （2）集合论知识 （3）图论知识

（4）代数系统基本知识 （5）组合数学知识

（6）高等数学关于矩阵知识 （7）计算方法

（8）线性规划和整数规划

（9）向量知识、叉积和点积的应用

2、 算法

（1）基础算法 （2）图论算法 （3）动态程序设计 （4）搜索和博弈算法

（5）游戏策略和计算几何

31

CCF中学生计算机程序设计水平评价体系（初稿）

3、 数据结构

（1）分块、块状链表 （2）集合

（3）复杂树结构

（4）有向图和无向图、二分图和层次图 （5）dfa和nfa

4、 编程语言

C++

三、能力要求

1、程序调试能力 2、测试数据设计能力 3、问题抽象能力 4、数学建模能力

5、算法和数据结构设计能力 6、算法优化能力

7、提出并研究问题的能力 8、创新算法的能力

四、考核办法 1、形式

采用集中竞赛的方式，对给出3—6个试题，采用上机编写程序的方法，在一定的时限内完成，用测试数据的方法进行检测。 2、目标要求

NOI金牌选手或积分累计1000分的选手。

五、题例

问题描述：

有N个点（编号1到N）组成的无向图，已经为你连了M条边。请你再连K条边，使得所有的点的度数都是偶数。求有多少种连的方法，由于方法很多，我们只关心结果模10007的余数。

要求你连的K条边中不能有重边，但和已经连好的边可以重。不允许自环的存在。

考察知识点：

动态规划、组合计数

程序（略）

32

本文来源：https://www.bwwdw.com/article/quvr.html