信息学竞赛考什么
信息学竞赛的考试以上机测试为主。以前普及组和提高组的初赛是笔试,从今年开始初赛都改为上机测试。在NOⅠ全国赛有一场笔试(100分),全部都是选择题,不过这个题库是提前公布的,这一部分并不会有什么区分度,大部分选手能拿满分。
信息学竞赛的题目以考查选手对算法和编程能力的掌握为主,本质上都是要求你编写程序,可以将给定的输入数据,按照题目要求,处理成符合要求的输出。题目类型有三种:
1、非交互式程序题(传统题)
非交互式程序题要求选手提交答案程序的源文件。该程序从一个正文件中读入数据,并向指定的输出文件中写入计算结果。
题目内容
求解问题的描述
输入文件名和输出文件名(可以是标准输入/输出)
输入数据格式,输出数据格式及输入数据范围
对程序使用计算资源的限制以及其他可能限制
选手按照要求编写程序后,需要自己进行测试,保证符合题目要求。赛后统一提交并进行评测。出题人会生成构造多组测试数据,向选手编写的程序编译后的可执行文件输入,得到选手输出,和标准输出进行对比,如果选手输出和标准输出一致(或通过特殊判断认为选手输出合法)就能得到这部分的分数。如果输出错误或运行时间过久,运行时错误等问题,则不能得分。
2、交互式程序题
交互式程序题要求选手提交答案程序的源文件。该程序通过调用所提供的库函数,实现数据的输入和输出。
题目内容
求解问题的描述
库函数的功能,函数的原型以及获取和链接方式
输入数据格式,输出数据格式以及输入数据范围
对程序使用计算资源的限制以及其他可能限制
对于非交互式程序题和交互式程序题,对选手使用内存大小的限制,包括运行代码、程序运行时所需的栈和堆在内的所有工作内存的总和。当题面中沒有给出对使用内存的限制时,以选手用机的实际使用限制为准。对选手程序运行时间的限制,一般均大于标准答案程序所需最长运行时间的5O%以上,以避免测试的超时判断误差。
3、答案提交型题
答案提交型题,不要求选手提交程序的源文件,选手需按题目要求,根据给定的输入数据文件生成一组输出数据文件,该组数据文件既可以是由选手的程序输出的,也可以是由选手手工构造的,当选手使用自己自行设计的程序生成题目答案时,只要你给出一个处理后的答案并且提交就行,其所使用的程序不用提交。
题目内容
求解问题的描述
输入数据格式,输出数据格式
输入数据文件的获取方法
一般提交的答案不是唯一的,而且答案有优劣之分,优秀的答案获得高分。
各种比赛的评测都是黑盒评测,评测方式会有一些区别,N0IP、NOl及多数省选是离线测试,选手需要编写程序,等待比赛结束后统一收取程序,然后统一评测给出结果。而APlO和lOl是在线评测,就是选手写完程序后就可以立刻提交评测,并且获得结果,成绩以最后提交结果为准。
在信息学竞赛中,出题人往往会在题目中分配子任务,通俗来说,对于一道题目,选手可以比较容易写出一种比较差的方法,(俗称打暴力),解决部分子任务。而水平高的选手可以写出比较好的算法而获得高分。区分算法好坏的标准就是是否能够通过更多子任务。国内比赛多按测试点给分,但APlO和很多国外的信息学竞赛进行捆绑测试,也就是一个子任务中一组测试点全部正确才能给这个子任务的分。据说现在的比赛形式有向这个方向发展的超势。
信息学竞赛的语言
在信息学竞赛中,并不能使用所有语言,现在国内的信息学竞赛只能使用C语言、C++和Pascal。规定从2022年开始NOIP只能使用C++。在信息学竞赛中,语言本身只是为了解决算法问题的工具,我们能用到的语言特性也只是C++中的一部分(CwithSTL)。所以我们学习C++语言,并不需要精通它,只需要学习最基础的一些语言特性就够了。
竞赛的核心
信息学竞赛的核心就是数据结构和算法。就是通过编写程序,将数据进行自动化处理的方式,解决确定的问题。数据结构和算法知识相当广泛,也有难易之分。一些算法和数据结构是前辈创造和优化的,近几年不断出现新的算法和数据结构。选手甚至可以自己创造一些算法。学习这些算法并能灵活运用是信息学竞赛的最重要工作。
对于普及组来说,需要掌握排序,枚举,递推,递归、搜索、贪心、高精度和简单动态规划等基础算法,掌握队列、栈、链表、简单图论等数据结构。
对于提高组来说,不仅要掌握普及组的要求,而且从深度和广度还要更深,必须学习更多种类的动态规划,了解更多的数据结构(树,图,堆等)。学习一些数学工具(数论,多项式理论,计算几何,组合数学,概率论,矩阵,函数等)。越是高层次的比赛对思维能力的要求越高,对数学的要求越高,虽然信息学不能和数学划等号,但良好的数学能力可以帮助选手更好的解决问题。
对于省选和国赛选手来说则需要掌握更多的知识和更高的思维能力,需要不断地关注国内外信竞高手的动态,学习往年信竞大神的题解和论文。
NOlP竞赛大纲
1、初赛内容与要求
2、复赛内容与要求
在初赛内容的基础上增加以下内容:
CCF在2003年组织制定,2005年修订。这十多年来官方再也没有公布新的考纲。但是考试的算法日新月异,有了翻天覆地的变化,考题早就不再局限于这个这纲了。更何况现在出题都是往届国家队或集训队已进大学的大学生出题,验题。他们很多人不知道考纲的存在,也不会考虑考纲的问题。所以现在的形式可以说没有考纲。
联系客服