#AB03. 算法竞赛常见题型

算法竞赛常见题型

当前没有测试数据。

传统题

传统题是最常见的题型。
出题人会准备一系列的测试点,每个测试点都会有输入文件参考输出(即正确答案)两个文件,并且会有时间限制与空间限制。
评测时会运行选手程序,得到选手输出文件,通过比对“选手输出”与“参考输出”即可判定这个测试点的评测结果。评测结果有很多,常见的有下面几种:

  • AC:即通过(Accepted),完美通过了这个测试点。
  • WA:即答案错误(Wrong Answer),选手输出是错误的。
  • CE:即编译错误(Compile Error),选手程序在编译时就发生了错误。
  • TLE:即时间超限(Time Limit Exceeded),选手程序运行的时间超过了题目的时间限制。
  • MLE:即空间超限(Memory Limit Exceeded),选手程序运行消耗的内存超过了题目的空间限制。
  • RE:即 运行时错误(Runtime Error),选手程序运行的过程中发生了错误,常见的有访问了没申请的内存(数组超限)或者非法的数学运算。有的时候无限递归造成的 MLE 之类的错误也会报成 RE

此外还有像格式错误、系统错误、输出超限等非常规的错误。

Special Judge

大部分时候的评测是直接对比选手输出参考输出,如果一致即通过。在 NOI 系列赛事中和绝大多数 OJ 都会忽略行末空格和文末换行。
但有的时候传统题的答案不唯一,而是满足要求即可,此时就会进行特殊评测。比较常见的是精度控制以及一些“符合题意即可”的构造题。
此时出题人会写一个 checker 程序来评判选手输出

文件IO

NOI 系列赛事中通常会要求文件的形式输入输出,需要选手从某个指定文件名的文件中得到输入,并输出到另一个指定文件名的文件中。
通常情况下如果题目的英文名是 apple,那么输入文件名与输出文件名会是 apple.inapple.out
简单来说,此时只需要在代码开头(或读取任何标准输入前)加入下面两行代码即可。

freopen("apple.in", "r", stdin);
freopen("apple.out", "w", stdout);

这会把输入文件和输出文件分别重定向到标准输入输出。

提交答案题

不要求提交程序,而是要求提交一系列答案文件的压缩包的题目。
一般情况下会有多个问题,每个问题对应一个答案文件。此时题目就没有时间限制与空间限制的限制,只要在比赛期间能在本地手算或者用一个程序算出来答案即可。

交互题

比如猜数字的算法,不会是固定的输入,而是需要评测程序根据选手程序猜的数字反馈“大了”还是“小了”。
最常见的交互是 STDIO 交互,选手输入与输出会分别通过管线对接到交互器的输出与输入。每次选手输出后,都可以通过输入来得到交互器的输出。这类题需要注意刷新输出缓冲区。
在 IOI 和 APIO 等国际 OI 赛事中,更常见的交互方式是 Grader 交互。这类题目选手只需要实现一个特定的函数,可以通过调用给定的辅助函数来进行交互。

通信题

一般需要选手完成两个程序。最常见的就是加密通信的需求,33OJ 的 “D0015” 题目就是一个简单的例子:
【题目描述】
输入一个只包含小写英文字母的字符串 。 你需要编写两份代码:a.cppb.cpp,并将它们以 zip 格式添加到一个压缩包(不用放在额外文件夹里;压缩包名称随意,如 ans.zip),然后通过提交文件的形式提交压缩包。

程序的评测按照以下步骤进行:

    1. 解压得到两个代码,编译后得到两个程序:ab
    1. 以 作为输入运行程序 a,记得到的输出为 。
    1. 以 作为输入运行程序 b,记得到的输出为 。
    1. 如果 且 即视为正确,否则视为错误。

注意:正式比赛中一般裁判会看一下每个程序来规避作弊的问题。