kkksc03
2018-12-02 00:13:57
系列文章分为六部分，本文为第三部分。欢迎关注作者了解相关资讯。
学习信息学竞赛的好处是什么？谁说出来就教他！上回我们说到了学习信息学竞赛的原因。但是很多不明真相的家长和老师看到选手一直坐在电脑前，于是认为“玩电脑”，这其实是因为不理解信息学竞赛的考察形式和内容造成的误解。这回作者让大家理解一下这样一个竞赛到底是考察什么东西。
信息学竞赛的考察形式分为笔试和上机两种形式。不仅是信息学竞赛，包括计算机考级、大学生程序设计比赛、信息技术高考等相关考试竞赛的形式也无外乎这两种。信息学竞赛以上机测试为主，但是笔试也是重要的组成部分。
信息学竞赛无论普及组还是提高组，初赛的形式是笔试，在固定的时间内完成一份试卷，原则上不允许使用计算器但是因考场而异（信息学竞赛比赛流程管理混乱不是一日两日的事情了）。批改是按照市级赛区统一批改然后统一划线决定复赛名单（当然也有城市是将参赛名额分到学校，学校校内进行批改决定名额，虽然这么做是违规的）。
信息学竞赛除了初赛是笔试以外，NOI全国决赛也有100分的笔试环节，全部都是选择题。不过这个题库是提前公布的，选手可以记忆题目通过笔试，所以如果不是因为个别选手手滑太严重，这一部分并不会有什么区分度。
复赛、省选以及冬令营、APIO、CTSC等竞赛，以及NOI的主要比赛，都是上机测试，上机测试是信息学竞赛的重头戏，能直接决定你能获得什么奖。根据比赛的不同，每场上机测试限时3-5小时，需要完成3-4个题目。NOIP提高组、NOI和某些省选会分2天进行两次上机测试。
上机测试的题型有多种形式，但是无论是什么形式，本质上都是要求你编写程序，可以将给定的输入数据按照题目要求处理成符合要求的输出。
最常见的试题形式叫做“传统题”。传统题是指给你一个题目描述、输入输出格式、输入输出样例（有时会给你样例解释帮助你更好的理解题意）以及数据范围，你需要根据这些信息编写出一个程序，能够将给定的输入进行处理，然后输出答案。这边是一个例子（洛谷P1001 A+B problem）：
选手按照要求编写完程序后需要自己进行测试、保证程序符合题目要求。赛后统一提交并进行评测。出题人会生成构造多组测试数据，向选手编写的程序编译后的可执行文件输入，得到的选手输出和标准输出进行比对；如果选手输出和标准输出一致（或者通过特殊判断认为选手输出是合法的）就能够获得这部分的分数。如果输出了错误的答案或者运行时间过久、运行时错误等问题则不能得分。
在省选或者更高级别的竞赛中还会有“提交答案题”。依然会给你一个题目描述，并且给你所有的输入文件。你可以根据不同的输入文件特性来编写相应的程序来处理，甚至不编写程序通过人工方式进行处理（仅限输入规模不大的情况，俗称“手玩”），反正只要你给出一个处理后的答案并且提交就行了。一般来说提交的答案是不唯一的，而且答案可能有优劣之分，优秀的答案会获得高分。这种题目每次比赛最多也就出现一次，而且可能还不一定出。
前几年的NOI还会出现一种叫做“交互题”的题型。交互题是给你一个库，要求你编写程序调用这些库，根据库返回的信息进行处理，然后再给这些库返回结果。这种题型现在已经很久没有在国内大赛出现过了。
各种比赛的评测方法也会有一些区别。NOIP、NOI和多数省选是离线测试，选手需要编写程序，等待比赛结束后统一收取程序，然后统一评测给出结果。而APIO和IOI是在线评测，也就是说选手写完程序后就可以立刻提交评测并且获得结果。
在信息学竞赛中，出题人往往会在每个题目中分配子任务。通俗来说，对于一道题目，选手可以比较容易的写出一种“比较差的方法”，而水平更高的选手可以写出“比较好的算法”而获得更高分数。区分“算法好坏”的标准就是是否能够通过更多的子任务，这就保证了竞赛难度有一定的区分度。国内的比赛多按测试点给分，但是APIO和很多国外的信息学竞赛会进行捆绑测试，也就是说一个子任务中的一组测试点全部正确才能获得这个子任务的分数。但是据说现行的比赛的形式也有这个方向发展的趋势。
一言以蔽之，选手需要根据题目要求完成程序，这些程序有优劣之分，根据通过的测试点分数来区分程序的质量，从而区分出选手的水平。
说到编程，很多人就会想出Java、C++、Python、PHP等常见的工程语言（下图给出了工程中排名靠前的语言）。但是实际上在信息学竞赛中，并不能使用所有的语言。现在（2018年）国内的信息学竞赛只能使用C语言、C++和Pascal。早期的信息学竞赛还能使用BASIC。但是因为一些原因，从2022年开始NOIP将不再允许使用Pascal和C语言。
而在国外以及IOI可能还能使用Java等语言，至于国内是否能够解禁新的语言现在不知道。所以说想用Python来参加信息学竞赛的话可能就会让你失望啦。因此如果想问需要学习什么语言，那么唯一的标准答案就是：C++。
但是，语言之间并不是互斥的。很多选手能够掌握两门甚至更多种类的语言；实际上只要学好其中一门语言，在学习新的语言就会容易很多。即使初期可能会有一些混淆的习惯但是并不用太担心，写多了后自然就能信手拈来。
说到底，在信息学竞赛中，语言本身只是为了解决算法问题而使用的工具，即使是我们钦点的C++，实际上我们能用到的语言特性也只是C++中的一部分（我们经常笑称我们学的实际上是C with STL）。所以我们需要学习C++语言，但是我们并不需要精通它（实际上也做不到）。因此学习算法竞赛的错误入门姿势是阅读砖头厚的《C++ Primer Plus》等大而全的书籍，因为我们只需要学习最基础的一些语言特性就足以使用了。
除了语言，我们会稍微涉猎计算机构造原理的知识。我们需要知道数据在计算机中是怎么表示、储存、运算、演示的。这不仅是信息学竞赛初赛的考点，也会让你更加了解计算机的结构，并且优化算法。
至于写游戏写网站这种应用程序倒不是信息学竞赛涉及的内容（虽然初赛的确考过HTML语言，但是非常久了）。只不过了解语言和计算机原理本身的话，对于学习编写“实用”程序，了解软件工程，还是有好处的（见本系列上一篇文章）
信息学竞赛的核心就是数据结构和算法了。通俗的来讲就是通过编写程序，将输入数据进行自动化处理的方式，可以解决一类确定的问题。
数据结构和算法知识相当广泛，也有难易之分。一些算法和数据结构是前辈（可能是数学家、计算科学家、甚至是算法竞赛的选手）创造和优化的。我们会合理利用这些算法知识来编写程序解决问题，甚至自己创造一些算法。学习这些算法是训练竞赛的最重要的部分，需要耗费大量的时间和精力。
对于初中普及组来说，需要掌握排序、简单图论、简单贪心、简单动态规划等算法。而对于提高组选手来说不仅需要掌握普及组的要求，而且从深度和广度还要更深，必须需要学习更多种类的动态规划，了解更多的数据结构（线段树、二叉堆等），对思维的要求也更高。至于省选级别的，需要掌握的知识也就更多了。
很多选手关心竞赛官方是否存在“考纲”。那我在这边把最新的考纲放出来（source： http://www.noi.cn/newsview.html?id=1&hash=3071E8）：
该考纲于2003年制定，2005年修订。此后的十几年间官方再也没有在官网上公布新的考纲，但是考察的算法却有了天翻地覆的变化，考题也不再局限于这个大纲之内。就现在的形式而言，这个考纲说了相当于没说。至于要学习什么算法呢？同学可以参考一下洛谷的试炼场，我们已经整理好需要学习的内容了。
实际上我们研究的算法算是离散数学，虽然我们并不一定感受得到。解决这些问题经常需要使用一些数学工具（数论、多项式理论、计算几何、组合数学和概率论等等），越是高层次的比赛对数学思维能力要求也是越高。虽然信息学并不能和数学划等号，但是良好的数学能力可以帮助选手更好的解决这些问题。
最后，我们不修电脑，不修投影仪，也不做PPT。
路漫漫其修远兮，吾将上下而求索。竞赛竞争激烈，但是也可以很有收获。本系列文章将继续更新。预计在猴年马月前更新完毕。
信息学竞赛全攻略（一）：竞赛基本概况（报名与赛程）
信息学竞赛全攻略（二）：为什么要参加竞赛与自主招生政策
信息学竞赛全攻略（三）：信息学竞赛考什么
信息学竞赛全攻略（四）：什么样的同学适合参加竞赛
信息学竞赛全攻略（五）：零基础学生如何入门
信息学竞赛全攻略（六）：如何进一步提升算法能力