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时。评测结果状态全表评测过程结束后评测系统会根据程序的运行状态给出不同的评测结果状态含义关键判定特征AcceptedAC选手程序被接受输出比对通过Compile ErrorCE选手程序无法正常编译编译阶段失败Wrong AnswerWA选手程序正常结束但输出与测试点输出不符输出比对不通过Presentation ErrorPE选手程序正常结束但格式不符合要求大多数评测系统会将 PE 归到 WA 中Runtime ErrorRE选手程序非正常结束程序结束时的返回值不为零Time Limit ExceededTLE程序运行时间超过给定时间限制运行超时Memory Limit ExceededMLE程序占用最大空间超过给定空间限制内存超限Output Limit ExceededOLE程序输出内容量超过最大限制输出量超限这些评测结果大多也适用于其他类型的题目比如交互题中询问次数过多或未及时刷新输出缓冲往往会以 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 exceededILE错误。另外如果题目含多组数据并且程序可以在未读入所有数据前就知道答案也仍然要读入所有数据否则同样会因为读入混乱引起 ILE可以一次提出多次询问、一次接收所有询问的回答同时尽量不要使用快读。如果程序查询次数过多则在 Codeforces 上会给出 Wrong Answer 的评测结果评测系统会说明 WA 的原因而 UVa 会给出 Protocol Limit ExceededPLE的评测结果。如果程序交互格式错误UVa 会给出 Protocol ViolationPV的评测结果。由于交互题输入输出较为繁琐建议分别封装输入和输出函数。比赛时如果出题人给出了 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 #includecstdio char *s{#includecstdio%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.cppgetchar/putchar、io_2.cppfread/fwrite与 io_3.cppmmap。基于流的 I/Ostd::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 中的结构体IOchar 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 Judgespj / 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 OI-wiki 算法竞赛题型全解析：传统题、提交答案题与交互题的评测机制与实战要点
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时。评测结果状态全表评测过程结束后评测系统会根据程序的运行状态给出不同的评测结果状态含义关键判定特征AcceptedAC选手程序被接受输出比对通过Compile ErrorCE选手程序无法正常编译编译阶段失败Wrong AnswerWA选手程序正常结束但输出与测试点输出不符输出比对不通过Presentation ErrorPE选手程序正常结束但格式不符合要求大多数评测系统会将 PE 归到 WA 中Runtime ErrorRE选手程序非正常结束程序结束时的返回值不为零Time Limit ExceededTLE程序运行时间超过给定时间限制运行超时Memory Limit ExceededMLE程序占用最大空间超过给定空间限制内存超限Output Limit ExceededOLE程序输出内容量超过最大限制输出量超限这些评测结果大多也适用于其他类型的题目比如交互题中询问次数过多或未及时刷新输出缓冲往往会以 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 exceededILE错误。另外如果题目含多组数据并且程序可以在未读入所有数据前就知道答案也仍然要读入所有数据否则同样会因为读入混乱引起 ILE可以一次提出多次询问、一次接收所有询问的回答同时尽量不要使用快读。如果程序查询次数过多则在 Codeforces 上会给出 Wrong Answer 的评测结果评测系统会说明 WA 的原因而 UVa 会给出 Protocol Limit ExceededPLE的评测结果。如果程序交互格式错误UVa 会给出 Protocol ViolationPV的评测结果。由于交互题输入输出较为繁琐建议分别封装输入和输出函数。比赛时如果出题人给出了 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 #includecstdio char *s{#includecstdio%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.cppgetchar/putchar、io_2.cppfread/fwrite与 io_3.cppmmap。基于流的 I/Ostd::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 中的结构体IOchar 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 Judgespj / 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考