企业官网建设流程全解析

OI-wiki 算法竞赛题型全解析：传统题、提交答案题与交互题的评测机制与实战要点

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

算法竞赛中的题目并非只有"读入数据、输出答案"一种形态。本指南以 OI-wiki 竞赛板块的题型介绍为骨架，系统梳理传统题（黑盒评测）、提交答案题、交互题、通信题、函数补全题等主流题型的定义、评测流程、计分规则与常见坑点，并结合仓库内 交互题专项指南、I/O 优化实现 与 Special Judge 编写规范 等源码级资料进行纵深补充。读完本文，你将能够准确理解 OJ 上每种状态的成因，掌握 STDIO 交互与 Grader 交互的编程范式，并具备应对非传统题型的基本能力。

传统题：黑盒评测的完整流程

传统题是目前算法竞赛中较为常见的题型，也是理解其他所有题型的基础。

选手需要提交源代码，评测系统会使用事先准备好的输入数据和相应的输出数据作为测试点，将选手提交的源代码编译后，让选手程序读入输入数据，通过将选手输出与事先准备好的输出比较，来判断选手程序是否正确。这种评测方式被称之为黑盒评测。由于技术上和资源上的限制，一道题目的测试点大多数情况下不能覆盖满足数据范围的全部数据；对于 Python 这样的解释性语言，评测系统会直接由解释器解释运行程序，而不是先编译。

时间限制与空间限制

对于一个测试点，往往还会设置时间限制和空间限制：

• 时间限制：指程序运行时间的限制。准确来说，一般是程序的用户态时间。选手程序在一个测试点上的运行时间不能超过给定的时间限制。
• 空间限制：指程序使用的内存量的限制。选手程序在运行时占用的最大空间不能超过给定的空间限制。

事实上评测系统的实现远比黑盒描述复杂，这里只是概括介绍了评测系统的评测过程。评测系统在判定时通常还会进行输出比对：在程序正常运行结束后，选手的输出会和测试点输出进行比对。这种比对一般采用过滤文末换行和行末空格之后，进行全文比对的方式。对于某些特殊的题目，会使用 Special Judge 来进行比对——例如当题目存在多组解、或要求答案与标准答案误差小于某阈值（如1e-3）时。

评测结果状态全表

评测过程结束后，评测系统会根据程序的运行状态给出不同的评测结果：

这些评测结果大多也适用于其他类型的题目，比如交互题中"询问次数过多"或"未及时刷新输出缓冲"往往会以 WA 或 TLE 类状态呈现（详见下文交互题部分）。

ICPC 与 OI 的计分差异

• 在ICPC 赛事中，你的程序需要在一道题目的所有测试点上都取得 AC 状态，才能视为通过相应的题目，即"全对才得分"。
• 在OI 赛事中，在一个测试点中取得 AC 状态，即可拿到该测试点的分数，即"按测试点给分"；一些测试点还可能有部分分，选手在完成一个测试点的部分任务，或者选手的输出正确但不够优的情况下，可以获得一定比例的分数。

这一差异直接影响做题策略：OI 赛制下即使无法完整 AC，也应力争通过数据较小的子任务测试点。

提交答案题：直接提交答案文件的题型

提交答案题是直接提交答案的题目。该种题目一般会给出输入文件，要求提交包含有XXX1.out、XXX2.out、XXX3.out…XXXn.out的压缩包、文件夹或纯文件。

提交答案后，评测系统会比较答案文件与标准答案，根据选手答案的优劣情况和任务完成度给予一定的分数。由于提交答案题不需要运行源程序，故提交答案题不存在时间和空间限制——这是它与传统题最本质的区别。

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

• 手玩：简单粗暴，但遇到较大的数据就没辙了；
• 编写一个程序来获得答案文件：即用代码"生成答案"，是处理大数据规模的唯一可行路径。

仓库中docs/basic等多个目录下examples/中的.in/.ans文件对（如 docs/contest/examples/io/io_1.in 与 io_1.ans），本质上就是"输入文件 + 标准答案文件"的组织形式，可以帮助理解这类题目的数据形态。

交互题：选手程序与测评程序的对话

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

关于交互题的更深入讲解，可以参考仓库内的交互题专项文档。该文档指出：交互题没有很高的前置算法要求，一般也没有严格的时间限制，程序的优秀程度往往仅取决于交互次数限制；2019 年 NOI 系列比赛中连续出现《P5208[WC2019] I 君的商店》《P5473[NOI2019] I 君的探险》两道交互题，代表着交互题已回归 NOI 系列比赛。

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

STDIO 交互：标准 I/O 对话

STDIO 交互（标准 I/O 交互）是 Codeforces、AtCoder 等在线平台的交互手段，也是 ICPC 系列赛事中的标准。

典型例题如「LOJ #559.『LibreOJ Round #9』ZQC 的迷宫」：位于 $n \times m$ 个方格组成的黑暗迷宫中的你，需要走到终点，迷宫中任意两个方格之间均连通且仅有唯一的一条路径，且迷宫完全黑暗，你无法得到除终点以外的任何信息。每次前进时只能从当前格子出发，沿着左侧或右侧墙壁、左手或右手扶着墙壁前进一个单位长度；若该侧墙壁不存在则无法前进，若未在限定步数内走出迷宫则挑战失败。

对于这类题目，选手只需像往常一样将询问写到标准输出，刷新输出缓冲后从标准输入读取结果。选手程序刷新输出缓冲后，通过管道连接它的测评程序（称为交互器）才能立刻接收到这些数据。在 C/C++ 中，fflush(stdout)和std::cout << std::flush可以实现这个操作（使用std::cout << std::endl换行时也会自动刷新缓冲区，但是std::cout << '\n'不会）；Pascal 则是flush(output)。

仓库 交互题专项文档 还补充了交互题的特殊错误：

• 选手每一次输出后都需要刷新缓冲区，否则会引起Idleness limit exceeded（ILE）错误。另外，如果题目含多组数据并且程序可以在未读入所有数据前就知道答案，也仍然要读入所有数据，否则同样会因为读入混乱引起 ILE（可以一次提出多次询问、一次接收所有询问的回答），同时尽量不要使用快读。
• 如果程序查询次数过多，则在 Codeforces 上会给出 Wrong Answer 的评测结果（评测系统会说明 WA 的原因），而 UVa 会给出 Protocol Limit Exceeded（PLE）的评测结果。
• 如果程序交互格式错误，UVa 会给出 Protocol Violation（PV）的评测结果。

由于交互题输入输出较为繁琐，建议分别封装输入和输出函数。比赛时如果出题人给出了 grader 头文件（用于 grader 交互题的调试）或者 checker 程序（用于 stdio 交互题的调试），则交互题的调试会比较简单；没有 testlib.h 的情况下，交互细节较多的 stdio 交互库一般有约 3k 代码量，再加上约 3k 长度的对拍器，至少需要一小时实现。无论是否有调试程序，调试交互题都往往需要选手模拟与程序的交互过程，因此交互题对"一次写对"和静态查错能力的要求很高。

下面给出 STDIO 交互的完整参考代码（来自 交互题专项文档，CF679A Bear and Prime 100）：筛出 50 以内的质数，并把 2、3、5、7 的平方也放进去以避免质数平方无法判定，共 19 个数字，符合 20 次询问限制：

#include <cstdio> constexpr int prime[] = {2, 3, 4, 5, 7, 9, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 49}; int cnt = 0; char res[5]; int main() { for (int i : prime) { printf("%d\n", i); fflush(stdout); scanf("%s", res); if (res[0] == 'y' && ++cnt == 2) return printf("composite"), 0; } printf("prime"); return 0; }

另一个典型例子是 CF843B Interactive LowerBound：链表最多有 $5 \times 10^4$ 个元素，但只能询问 1999 次。对于 $n < 2000$ 的情况直接枚举；$n \ge 2000$ 时随机撒 1000 个点，从小于 $x$ 的最大值开始向后遍历。注意由于 Codeforces 具有 hack 机制，很多人会刻意卡掉没有初始化随机种子的代码，所以在random_shuffle()前需要srand((size_t)new char)。

Grader 交互：函数调用的交互

Grader 交互方式常见于 IOI、APIO 等国际 OI 赛事（特别是 CMS 平台的竞赛）。

典型例题如「UOJ #206.【APIO2016】Gap」：有 $N$ 个严格递增的非负整数，需要找出相邻差的最大值，但程序不能直接读入整数序列，只能通过给定的函数MinMax查询序列信息，选手需要实现一个返回最大差值的函数。

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

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

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

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

两种交互方式的差别与选型

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

如果自己设计题目或举办比赛，需要对二者认真权衡和比较。

通信题：两个程序的协作解题

通信题是需要两个选手程序进行通信、合作完成某项任务的题目。第一个程序接收问题的输入，并产生某些输出；第二个程序的输入会与第一个的输出相关（有时是原封不动地作为一个参数，有时会由评测端处理得到），它需要产生问题的解。

本地测试的方法由于题目设定的不同而多种多样，常用的形式如：

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

由于评测平台对于通信题的支持有限，因而目前为止，通信题只常见于 IOI 系列赛和 UOJ 等少数在线平台举办的比赛。它仍是一个有待探索的领域。

函数补全题：补全而非完整提交

函数补全题是需要选手补全程序的题目。可以理解为在一道交互题中，题目给定了选手代码，要求编写辅助函数。通常有以下几种形式：

• 给定一个程序，并告知要求补全的代码块将被嵌入在哪里；
• 不给出程序，而将输入信息作为待提交函数的参数。

这种题在 LeetCode 和 PTA - 拼题 A 等平台上比较多见。它与 Grader 交互题的核心差异在于：交互题中选手编写的函数是"主角"，而函数补全题中选手需要嵌入的是被给定的程序框架中缺失的一部分。

其他类型：输出自身源代码的 Quine

除了上述主流题型，还有一些趣味性极强的特殊题目。经典代表是Quine：写一个程序，使其能输出自己的源代码，且代码中必须至少包含十个可见字符。题目很经典，但是在绝大多数 OJ 上都很难实现。

仓库 problems.md 给出的参考实现如下（注意：源代码不包含下方第一行的// clang-format off注释）：

// clang-format off #include<cstdio> char *s={"#include<cstdio>%cchar *s={%c%s%c};%cint main(){printf(s,10,34,s,34,10);return 0;}"}; int main(){printf(s,10,34,s,34,10);return 0;}

其原理是利用 C 语言的%s与转义字符：将源程序自身的骨架存入字符串s，%c依次填入换行符（ASCII 10）和双引号（ASCII 34），从而在运行时把自身完整地打印出来。

题型背后的通用工程基础：I/O 与 Special Judge

理解题型之后，还需要掌握支撑这些题型的两项工程能力：高性能 I/O 与自定义判定器。仓库提供了可直接运行的参考实现。

基于流的 I/O 优化与快读快写

在数据量极大的传统题（以及部分交互题）中，I/O 效率往往决定成败。仓库 I/O 优化文档 介绍了三个层次的方案，其参考代码分别位于 io_1.cpp（getchar/putchar）、io_2.cpp（fread/fwrite）与 io_3.cpp（mmap）。

基于流的 I/O（std::cin/std::cout）最常用的优化为关闭与 C 流的同步与解除输入输出流的关联：

std::ios::sync_with_stdio(false); std::cin.tie(nullptr);

注意：std::cin.tie(nullptr)的参数不可省略（省略会返回关联流而非解除关联），也无需对std::cout调用tie(nullptr)。同时进行上述两个操作后，程序中必须手动flush才能确保std::cout的内容在std::cin前出现。

fread/fwrite方案通过整段读写获得更高吞吐，其核心gc()宏实现为（见 io_2.cpp 中的结构体IO）：

char buf[1 << 20], *p1, *p2; #define gc() \ (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) \ ? EOF \ : *p1++)

mmap方案可将文件一次性映射到内存，但不能在 Windows 环境下使用（例如 Codeforces 与 HDU 的评测机系统），也不建议在正式赛场上使用；实际上使用fread已经足够快。此外，整数转换统一采用秦九韶算法从左向右累加，输出时借助 C 语言负整数除法向零取整的性质规避整型溢出问题。

Special Judge：判定"多解"与容差输出

当一道题有多组解，或要求浮点误差判断时，普通全文比对不再适用，需要Special Judge（spj / checker）来判定答案合法性。仓库 Special Judge 编写指南 给出了 Testlib、Lemon、Cena、CCR、Arbiter、HUSTOJ、QDUOJ、HDOJ、SYZOJ 2、牛客网、DOMJudge 等评测平台的具体 spj 写法。

以要求"标准答案与选手答案差值小于 1e-3、单个测试点满分为 10 分"为例，Testlib 版本如下：

#include "testlib.h" // #include <cmath> int main(int argc, char *argv[]) { /* * inf：输入 * ouf：选手输出 * ans：标准输出 */ registerTestlibCmd(argc, argv); double pans = ouf.readDouble(), jans = ans.readDouble(); if (abs(pans - jans) < 1e-3) quitf(_ok, "Good job\n"); else quitf(_wa, "Too big or too small, expected %f, found %f\n", jans, pans); }

编写 spj 时还应注意：应判断文件尾是否有多余内容及输出格式是否正确（目前只有 Testlib 可以方便地做到前者）；判断浮点数时应注意 NaN，不合理的判断方式会导致输出 NaN 即可 AC 的情况；读入选手文件时应检查是否正确读入所需内容，防止 spj 自身运行错误。

总结

算法竞赛题型并非单一形态：传统题以黑盒评测为核心，围绕时间/空间限制与 AC/CE/WA/PE/RE/TLE/MLE/OLE 状态体系展开；提交答案题绕开程序运行、直接比拼答案文件；交互题以 STDIO 与 Grader 两种方式实现"对话式"求解；通信题与函数补全题进一步拓展了选手与评测系统协作的边界；Quine 等特殊题型则考验对语言机制本身的把握。理解每种题型的评测机制与计分规则，是制定正确解题策略的第一步——而高性能 I/O 与 Special Judge 的编写能力，则是驾驭这些题型的通用工程底座。如需继续深入，可进一步阅读 交互题专项文档、I/O 优化文档 与 Special Judge 编写指南。

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki