跳转至

非传统题

导语

我们知道,通过提交程序、由评测机输入数据并判断输出数据的题目叫传统题。而 OI 发展迅速,普通的传统题已经不能满足我们的所有需求,所以在近几年,有几种非传统题慢慢进入大家的视野。

提交答案题

提交答案题,顾名思义,就是直接提交答案的题目。该种题目一般会给你输入文件,然后要求提交包含有 XXX1.out、XXX2.out、XXX3.out......XXXn.out 的压缩包、文件夹或纯文件。评测机做的事情就很简单了:比较答案文件与标准答案即可。

做这种题目一般有两种方法:

  1. 手玩。这种方法简单粗暴,但是遇到较大的数据就没辙了。
  2. 编写一个程序来获得答案文件。

交互题

在交互题中,选手程序需要通过与测评程序交互来完成任务。一类常见的情形是,选手程序向测评程序发出询问,并得到其反馈。测评程序可能对选手的询问作出限制,或调整应答策略来尽可能增加询问次数,这也给题目带来了更多变化。

交互方式主要有如下两种。虽然技术上有不小的差异,但在考察算法的本质上它们并没有实际区别。

STDIO 交互

STDIO 交互(标准 I/O 交互)是 Codeforces、AtCoder 等在线平台的交互手段,也是 ICPC 系列赛事中的标准。 LOJ #559.「LibreOJ Round #9」ZQC 的迷宫 是一道典型的 STDIO 交互题。 这里 是 Codeforces 的一个更加简要的说明。

对于这类题目,选手只需像往常一样将询问写到标准输出, 刷新输出缓冲 后从标准输入读取结果。选手程序刷新输出缓冲后,通过管道连接它的测评程序(称为交互器)才能立刻接收到这些数据。在 C/C++ 中, fflush(stdout)std::cout << std::flush 可以实现这个操作;Pascal 则是 flush(output)

Grader 交互

Grader 交互方式常见于 IOI、APIO 等国际 OI 赛事(特别是 CMS 平台的竞赛)。 UOJ #206.【APIO2016】Gap 是一道典型的 grader 交互题。

对于这类题目,选手只需编写一个特定的函数完成某项任务,它通过调用给定的若干辅助函数来进行交互。为了便于选手在本地测试,题目会下发一个头文件与一个参考测评程序 grader.cpp (对于 Pascal 语言是一个库 graderlib ),选手将自己的程序与 grader.cpp 一同编译方可得到可执行文件。

1
2
g++ grader.cpp my_solution.cpp -o my_solution -Wall -O2
./my_solution   # 执行程序

编译得到的程序表现与传统题程序类似。它会打开固定的文件,以固定的格式读取数据,调用选手编写的函数,并将结果和若干信息(例如询问的次数、答案正确性)显示在标准输出上。

实际测评时,选手的程序会与一个不同的 grader.cpp 编译。这个 grader.cpp 将以类似的方式调用选手编写的函数,并记录其得分。一般来说,这个版本的 grader.cpp 所有全局符号都会设为 static ,也即不能通过冲突命名的方式破解它,但是任何尝试突破 grader 限制的行为都是会导致 disqualification 的哦。

差别

STDIO 交互的一个明显优势在于它可以支持任何编程语言,但是输入输出的耗时容易成为问题设计的瓶颈,导致有时无法区分程序的时间效率差别。而 grader 交互则恰好相反,由于函数调用的开销不大,常常可以允许 10^6 数量级的询问次数,但是语言的限制是其短板。

如果自己设计题目或举办比赛,就要记得权衡这些啦。

通信题

在通信题中,选手需要编写 两个 程序,合作完成某项任务。第一个程序接收问题的输入,并产生某些输出;第二个程序的输入会与第一个的输出相关(有时是原封不动地作为一个参数,有时会由评测端处理得到),它需要产生问题的解。 UOJ #178. 新年的贺电#454.【UER #8】打雪仗 都是典型的通信题。

本地测试的方法由于题目设定的不同而多种多样,常用的如:

  • 手工输入
  • 编写一个辅助程序,转换第一个程序的输出到第二个程序的输入
  • 用双向管道将两个程序的标准输入/输出连接起来

由于评测平台对于通信题的支持有限,因而目前为止通信题只常见于 IOI 系列赛和 UOJ 等少数在线平台举办的比赛,仍是一个有待探索的领域。期待着在未来,通信题能带来更多全新的挑战和新鲜的 idea。

函数补全题

函数补全题,当然就是补全函数啦!这种题通常有一下几种情况:

  • 会给你一个程序,并告知你的函数将被嵌入在哪里。
  • 不给出程序,而将输入信息作为你的函数的参数。

其实你可以理解为一道交互题中,你变成了编写前面讲到的辅助函数,而选手代码就是给出的程序。

这种题在 LeetCodePTA - 拼题 A 上比较多见,没见过的可以去看一看。

其他类型

比如说 Quine ,这道题要求的是编写一个程序使得你的程序能够输出它本身(要求程序包含可见字符)。

这是一道经典题,但是在绝大多数 OJ 上都很难实现。


评论