在算法竞赛中,有多种多样的问题类型。
传统题传统题 是目前算法竞赛中较为常见的题型。
选手需要提交源代码,评测系统会使用事先准备好一些输入数据和相应的输出数据作为测试点1,将选手提交的源代码编译后2,让选手程序读入输入数据,通过将选手输出与事先准备好的输出比较,来判断选手程序是否正确。这种评测方式被称之为 黑盒评测3。
对于一个测试点,往往还会设置时间限制和空间限制。
时间限制,指的是程序运行时间的限制4。选手程序在一个测试点上的运行时间不能超过给定的时间限制。
空间限制,指的是程序使用的内存量的限制。选手程序在运行时占用的最大空间不能超过给定的空间限制。
在程序正常运行结束后,选手的输出会和测试点输出进行比对。这种比对一般采用过滤文末换行和行末空格之后,进行全文比对的方式。对于某些特殊的题目,会使用 Special Judge 来进行比对。
这一过程结束后,评测系统会根据程序的运行状态,给出不同的 评测结果5:
Accepted(AC):选手程序被接受。Compile Error(CE):选手程序无法正常编译。Wrong Answer(WA):选手程序正常结束,但是选手程序的输出与测试点输出不符。Presentation Error(PE):选手程序正常结束,但是格式不符合要求6。Runtime Error(RE):选手程序非正常结束(选手程序结束时的返回值不为零)。Time Limit Exceeded(TLE):选手程序运行的时间超过了给定的时间限制。Memory Limit Exceeded(MLE):选手程序占用的最大空间超过了给定的空间限制。Output Limit Exceeded(OLE):选手程序输出的内容的量超过了最大限制。在 ICPC 赛事中,你的程序需要在一道题目的所有测试点上都取得 AC 状态,才能视为通过相应的题目。在 OI 赛事中,在一个测试点中取得 AC 状态,即可拿到该测试点的分数7。
提交答案题提交答案题 是直接提交答案的题目。该种题目一般会给出输入文件,要求提交包含有 XXX1.out、XXX2.out、XXX3.out…XXXn.out 的压缩包、文件夹或纯文件。
提交答案后,评测系统会比较答案文件与标准答案,根据选手答案的优劣情况和任务完成度,给予一定的分数。
因为提交答案题不需要运行源程序,故提交答案题不存在时间和空间限制。
做这种题目一般有两种方法:
手玩。这种方法简单粗暴,但是遇到较大的数据就没辙了。编写一个程序来获得答案文件。交互题交互题 是需要选手程序与测评程序交互来完成任务的题目。一类常见的情形是,选手程序向测评程序发出询问,并得到其反馈。测评程序可能对选手的询问作出限制,或调整应答策略来尽可能增加询问次数,这也给题目带来了