Non-Trad Problems
通过提交程序、由评测机输入数据并判断输出数据的题目被称为传统题。而 OI 发展迅速，普通的传统题已经不能满足选手及出题人的所有需求，所以在近几年，有几种非传统题慢慢进入大家的视野。
提交答案题¶
提交答案题 是直接提交答案的题目。该种题目一般会给出输入文件，要求提交包含有 XXX1.out 、 XXX2.out 、 XXX3.out … XXXn.out 的压缩包、文件夹或纯文件。提交答案后，评测机会比较答案文件与标准答案并给出结果。
做这种题目一般有两种方法：
- 手玩。这种方法简单粗暴，但是遇到较大的数据就没辙了。
- 编写一个程序来获得答案文件。
交互题¶
交互题 是需要选手程序与测评程序交互来完成任务的题目。一类常见的情形是，选手程序向测评程序发出询问，并得到其反馈。测评程序可能对选手的询问作出限制，或调整应答策略来尽可能增加询问次数，这也给题目带来了更多变化。
更详细的交互题讲解可以看 交互题 。
交互方式主要有如下两种。虽然技术上有不小的差异，但在考察算法的本质上它们并没有实际区别。
STDIO 交互¶
STDIO 交互（标准 I/O 交互）是 Codeforces、AtCoder 等在线平台的交互手段，也是 ICPC 系列赛事中的标准。Codeforces 提供了一个更加简要的 说明（英文） 。
ZQC 的迷宫
LOJ #559.「LibreOJ Round #9」ZQC 的迷宫
请注意最下方添加内容。
本题是一道交互题。
位于 个方格组成的黑暗迷宫的你，需要走到这个迷宫的终点，以完成迷宫挑战。
最开始，你位于迷宫的起点即 处，且面向右侧，终点位于 处。迷宫中任意两个方格之间均连通，且仅有唯一的一条路径，两个相邻（即上、下、左、右四连通）方格间长度为一个单位长度。两个相邻方格之间可能会有墙壁，墙壁厚度相对于方格而言非常小，粗略不计。迷宫的边界均有墙壁，且每一堵墙壁均与边界连通。迷宫是完全黑暗的，这意味着，你无法得到除 以外的任何信息。
为了在黑暗条件下尽量不迷路，每次前进时你只能从当前格子出发，沿着左侧或右侧墙壁，左手或右手扶着墙壁前进，并且使扶着墙壁的手移动距离恰好为一个单位长度。需要注意的是，若左侧或右侧墙壁不存在，则沿该侧方向无法前进。
在黑暗中过久的你会感到恐惧，因此你需要在你尽早走出迷宫。如果你没有在限定步数内走出迷宫，挑战将会失败。
对于这类题目，选手只需像往常一样将询问写到标准输出， 刷新输出缓冲 后从标准输入读取结果。选手程序刷新输出缓冲后，通过管道连接它的测评程序（称为交互器）才能立刻接收到这些数据。在 C/C++ 中， fflush(stdout) 和 std::cout << std::flush 可以实现这个操作（使用 std::cout << std::endl 换行时也会自动刷新缓冲区，但是 std::cout << '\n' 不会）；Pascal 则是 flush(output) 。
Grader 交互¶
Grader 交互方式常见于 IOI、APIO 等国际 OI 赛事（特别是 CMS 平台的竞赛）。
Gap
有 N 个严格递增的非负整数 a1,a2,…，aN（0≤a1<a2<⋯<aN≤1018）。你需要找出 ai+1−ai（0≤i≤N−1）里的最大的值。
你的程序不能直接读入这个整数序列，但是你可以通过给定的函数来查询该序列的信息。关于查询函数的细节，请根据你所使用的语言，参考下面的实现细节部分。
你需要实现一个函数，该函数返回 ai+1−ai（0≤i≤N−1）中的最大值。
对于这类题目，选手只需编写一个特定的函数完成某项任务，它通过调用给定的若干辅助函数来进行交互。为了便于选手在本地测试，题目会下发一个头文件与一个参考测评程序 grader.cpp （对于 Pascal 语言是一个库 graderlib ），选手将自己的程序与 grader.cpp 一同编译方可得到可执行文件。
g++ grader.cpp my_solution.cpp -o my_solution -Wall -O2
./my_solution # 执行程序编译得到的程序表现与传统题程序类似。它会打开固定的文件，以固定的格式读取数据，调用选手编写的函数，并将结果和若干信息（例如询问的次数、答案正确性）显示在标准输出上。
实际测评时，选手的程序会与一个不同的 grader.cpp 编译。这个 grader.cpp 将以类似的方式调用选手编写的函数，并记录其得分。一般来说，这个版本的 grader.cpp 所有全局符号都会设为 static ，也即不能通过冲突命名的方式破解它，但是任何尝试突破 grader 限制的行为都会被判失格 (disqualification)。
差别¶
STDIO 交互的一个明显优势在于它可以支持任何编程语言，但是输入输出的耗时容易成为问题设计的瓶颈，导致有时无法区分程序的时间效率差别；Grader 交互则恰好相反，由于函数调用的开销不大，常常可以允许 数量级的询问次数，但是语言的限制是其短板。
如果自己设计题目或举办比赛，需要对二者认真权衡和比较。
通信题¶
通信题 是需要两个选手程序进行通信，合作完成某项任务的题目。第一个程序接收问题的输入，并产生某些输出；第二个程序的输入会与第一个的输出相关（有时是原封不动地作为一个参数，有时会由评测端处理得到），它需要产生问题的解。
本地测试的方法由于题目设定的不同而多种多样，常用的形式如：
- 手工输入
- 编写一个辅助程序，转换第一个程序的输出到第二个程序的输入
- 用双向管道将两个程序的标准输入/输出连接起来
由于评测平台对于通信题的支持有限，因而目前为止，通信题只常见于 IOI 系列赛和 UOJ 等少数在线平台举办的比赛。它仍是一个有待探索的领域。
函数补全题¶
函数补全题 是需要选手补全程序的题目。可以理解为在一道交互题中，题目给定了选手代码，要求编写辅助函数。
通常有以下几种形式：
- 给定一个程序，并告知要求补全的代码块将被嵌入在哪里。
- 不给出程序，而将输入信息作为待提交函数的参数。
这种题在 LeetCode 和 PTA - 拼题 A 上比较多见。
其他类型¶
题目很经典，但是在绝大多数 OJ 上都很难实现。
buildLast update and/or translate time of this article，Check the history
editFound smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github
peopleContributor of this article Ir1d, hsfzLZH1, CBW2007, Xeonacid, H-J-Granger, kawa-yoiko, NachtgeistW
translateTranslator of this article Visit the original article!
copyrightThe article is available under CC BY-SA 4.0 & SATA ; additional terms may apply.