2026/9/11 0:04:55
FEATURED · 精选文章 
OI Wiki 交互题实战指南交互协议、常见评测错误与五道经典例题深度解析【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki交互题是算法竞赛中一种要求选手程序与评测程序实时通信的题型选手程序向评测程序发出询问并依据反馈逐步逼近答案。本文以 OI Wiki 的交互题专题文档docs/contest/interaction.md为骨架结合仓库中关于题型分类与输入输出优化的配套文档系统讲解交互题的两种交互方式、评测结果判定规则、缓冲区刷新的关键陷阱、调试手段并逐题剖析 Bear and Prime 100、Interactive LowerBound、APIO2016 Gap、New Year and Finding Roots、太空站之谜五道经典例题及其完整参考代码帮助读者从会写交互代码进阶到能在交互次数限制内稳定 AC。一、交互题背景、定位与学习建议交互题并非新题型——上个世纪的 IOI 就已涉及。虽然交互题在相当长一段时间内未出现在省选以下的比赛中但 2019 年 NOI 系列比赛中连续出现两道交互题《P5208[WC2019]I 君的商店》与《P5473[NOI2019]I 君的探险》这可能代表着交互题重新回到 NOI 系列比赛中。因此掌握交互题对参加 NOI 系列赛事的选手具有现实意义。交互题有着鲜明的特点前置算法要求不高交互题一般没有很高的前置算法门槛通常也没有严格的时间限制。核心约束是交互次数程序的优秀程度往往仅取决于交互次数限制而非运行速度或常数优化。适合锻炼算法思维如果只想学习算法本身交互题未必是最佳载体但若想有意识地锻炼算法思维完成交互题是很不错的方法。建议循序渐进虽然交互题对选手已掌握算法的要求通常较低但仍建议掌握一定提高和省选算法后再尝试做交互题因为此时算法思维水平和知识面已达到一定水准更容易体会到交互题的精妙之处。基础的交互题题型介绍可参见 OI Wiki 的 题型介绍 - 交互题。二、两种交互方式STDIO 交互与 Grader 交互根据 docs/contest/problems.md 的说明交互题在技术实现上主要分为两种方式。虽然技术上有不小的差异但在考察算法的本质上二者没有实际区别。STDIO 交互标准 I/O 交互STDIO 交互是 Codeforces、AtCoder 等在线平台的交互手段也是 ICPC 系列赛事中的标准。这类题目中选手只需像往常一样将询问写到标准输出刷新输出缓冲后从标准输入读取结果。关键点在于选手程序刷新输出缓冲后通过管道连接它的测评程序交互器才能立刻接收到数据。在 C/C 中fflush(stdout)和std::cout std::flush可以实现这个操作使用std::cout std::endl换行时也会自动刷新缓冲区但是std::cout \n不会Pascal 则使用flush(output)。STDIO 交互的一个明显优势在于它可以支持任何编程语言但输入输出的耗时容易成为问题设计的瓶颈有时导致评测系统无法区分程序的时间效率差别。Grader 交互Grader 交互方式常见于 IOI、APIO 等国际 OI 赛事特别是 CMS 平台的竞赛。这类题目中选手只需编写一个特定的函数完成某项任务通过调用题目给定的若干辅助函数来进行交互。为了便于选手在本地测试题目会下发一个头文件与一个参考测评程序grader.cpp对于 Pascal 语言是一个库graderlib选手将自己的程序与grader.cpp一同编译方可得到可执行文件g grader.cpp my_solution.cpp -o my_solution -Wall -O2 ./my_solution # 执行程序编译得到的程序表现与传统题程序类似它会打开固定的文件以固定的格式读取数据调用选手编写的函数并将结果和若干信息例如询问的次数、答案正确性显示在标准输出上。实际测评时选手的程序会与一个不同的grader.cpp编译这个版本一般将所有全局符号设为static防止选手通过命名冲突的方式破解任何尝试突破 grader 限制的行为都会被判失格disqualification。Grader 交互由于函数调用开销不大常常可以允许 $10^6$ 数量级的询问次数但语言的限制是其短板。如果自己设计题目或举办比赛需要对两种交互方式认真权衡。三、交互题的特殊评测结果与常见错误交互题的错误形态与普通传统题不同OI Wiki 的交互题文档专门总结了三种特殊的评测结果1. Idleness limit exceededILE选手每一次输出后都需要刷新缓冲区否则会引起Idleness limit exceeded错误。这一错误的本质是交互器在等待选手程序的输出而选手程序的输出仍滞留在缓冲区中没有被刷新。另外需要特别注意如果题目含多组数据并且程序可以在未读入所有数据前就知道答案也仍然要读入所有数据否则会因为读入混乱引起 ILE。一种可行的策略是一次提出多次询问、一次接收所有询问的回答。同时尽量不要使用快读——快读基于getchar/fread等底层的缓冲机制容易与交互流程产生冲突反而引发读取混乱。2. Wrong AnswerWA与 Protocol Limit ExceededPLE如果程序查询次数过多在 Codeforces 上会给出 Wrong Answer 的评测结果不过评测系统会说明 Wrong Answer 的原因而 UVa 会给出Protocol Limit Exceeded (PLE)的评测结果。3. Protocol ViolationPV如果程序交互格式错误UVa 会给出Protocol Violation (PV)的评测结果。这意味着选手的输出不符合题目约定的交互协议格式。小结交互题的两种典型失败模式失败类型触发原因对应平台判定ILE输出后未刷新缓冲区 / 未读入全部数据Idleness limit exceeded查询次数超限询问次数超过题目限制Codeforces: WAUVa: PLE交互格式错误输出格式不符合协议UVa: PV四、I/O 封装交互题的工程化基础由于交互题输入输出较为繁琐OI Wiki 建议分别封装输入和输出函数。这样做一方面保证每次输出后刷新缓冲区这一关键动作不被遗漏另一方面让代码逻辑更清晰、更易排查错误。这里需要特别强调刷新缓冲区与 I/O 优化的冲突关系。在 docs/contest/io.md 中介绍了std::ios::sync_with_stdio(false)与std::cin.tie(nullptr)两个常用优化但文档同时警告在同时进行上述两个操作后程序中必须手动flush才能确保每次std::cout展现的内容可以在std::cin前出现——因为此时调用std::cin时std::cout不会自动刷新缓冲区。这与交互题的 ILE 错误直接相关交互题中使用优化后的流式 I/O 时必须在每次询问输出后显式刷新std::flush或std::endl否则交互器将永远等不到选手的询问。此外OI Wiki 在交互题文档中明确建议尽量不要使用快读。仓库 docs/contest/code/io/io_1.cpp 中的getchar/putchar式快读、docs/contest/code/io/io_2.cpp 中的fread/fwrite式快读其核心思路都是将字符流缓存在程序侧手动处理在交互场景中这类底层字符读取与 printf/scanf 混用极易破坏交互协议的同步性因此交互题更推荐朴素的printf/scanf或std::cout/std::cin 显式 flush并做好函数封装。五、交互题的调试grader、checker 与静态查错比赛时如果出题人给出了 grader 头文件用于 grader 交互题的调试或者 checker 程序用于 stdio 交互题的调试交互题的调试会比较简单因为交互题的对拍会比普通题目的对拍困难很多。从工程角度看交互题的调试成本相当可观没有testlib.h的情况下交互细节较多的题目的 stdio 交互库一般有 3k 代码量再加上 3k 长度的对拍器至少需要一小时实现。但无论是否有调试程序调试交互题的代码都往往需要选手模拟与程序的交互过程。因此交互题对选手的要求是能设计出高质量的程序尽量保证一遍做对拥有较强的静态查错能力在无法运行时定位逻辑错误。六、例题精讲1. CF679A Bear and Prime 100题意交互器隐藏一个 $[2,100]$ 内的整数选手最多询问 20 次该数是否被某个数整除判断其是质数还是合数。思路分析每个质数都有且只有两个因数所以直接枚举要猜的数的因数即可。由于限制最多询问 20 次并且对于较大的数如 92尝试分解质因数时发现需要最多枚举到 $\lfloor\frac{n}{2}\rfloor$ 的质数所以我们先筛出 50 以内的质数每次把所有这些数都询问一遍。关键细节本题对拍比较容易可以直接把值域内的数都尝试一遍。此时会发现程序无法有效处理质数的平方——例如 4 只能被 2 整除若只询问 2、3、5、7 等质数无法区分 $4$ 与质数 $2$ 的倍数特征。因此我们要把 $2,3,5,7$ 的平方 $4,9,25,49$ 都放进去总共 19 个数字符合 20 次询问限制。一旦出现两个是的回答例如 $4$ 被 $2$ 和 $4$ 都整除即可判定为合数。参考代码完整代码来自 docs/contest/interaction.md#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; }注意代码中每次printf后紧跟fflush(stdout)这正是交互题输出铁律的体现。2. CF843B Interactive LowerBound题意给定一个长度为 $n$$n \le 5 \times 10^4$的单向链表已知首元素下标start元素值严格递增。选手每次可询问一个下标得到该下标的元素值及其后继下标最多询问 1999 次求链表中第一个值不小于 $x$ 的元素。思路分析链表最多有 $5 \times 10^4$ 个元素但只能询问 1999 次并且只能获取元素的后一个元素所以普通的遍历整个链表的方法不可用。直接设法逼近目标元素的位置只有一种方法随机撒点。对于 $n 2000$ 的情况直接枚举依次询问每个下标取所有值不小于 $x$ 的元素中的最小值。对于 $n \ge 2000$ 的情况直接撒 1000 个点。由于元素值严格递增这些点之间的期望距离很小可以从小于 $x$ 的最大值开始向后遍历——可以证明在到达下一个撒点之前我们就已得到答案。遍历过程中一旦找到大于等于 $x$ 的元素就可以直接推出答案。虽然整体思路简单但实际情况下如果没有学习过模拟退火等非完美随机算法思考起来可能会困难一些。关键细节——随机种子由于 Codeforces 具有 hack 机制很多人会刻意卡掉没有初始化随机种子的代码所以在random_shuffle()函数前需要srand((size_t)new char)——用动态分配的内存地址作为随机种子每次运行都不同无法被 hack 预测。参考代码#include algorithm #include cstdio #include cstdlib constexpr int N 50005; int n, start, x; int a[N]; int main() { scanf(%d%d%d, n, start, x); if (n 2000) { int ans 2e9; for (int i 1; i n; i) { printf(? %d\n, i), fflush(stdout); int val, next; scanf(%d%d, val, next); if (val x) ans std::min(ans, val); } if (ans 2e9) ans -1; printf(! %d, ans), fflush(stdout); } else { srand((size_t) new char); int p start, ans 0; for (int i 1; i n; i) a[i] i; std::random_shuffle(a 1, a n 1); for (int i 1; i 1000; i) { printf(? %d\n, a[i]), fflush(stdout); int val, next; scanf(%d%d, val, next); if (val x val ans) p a[i], ans val; } while (p ! -1 ans x) { printf(? %d\n, p), fflush(stdout); int val, next; scanf(%d%d, val, next); ans val; p next; } if (ans x) ans -1; printf(! %d, ans), fflush(stdout); } return 0; }本代码展示了一个交互题的完整流程骨架?为询问指令、!为回答指令每次输出后立即fflush(stdout)。3. UOJ206 [APIO2016] Gap题意有 $N$ 个严格递增的非负整数 $a_1, a_2, \cdots, a_N$$0 \le a_1 a_2 \cdots a_N \le 10^{18}$选手不能直接读入序列但可以通过 grader 提供的MinMax(s, t, mn, mx)函数查询区间 $[s,t]$ 内的最小值和最大值若区间内无数则返回 -1。求相邻两数差的最大值。本题分两个子任务分别考察不同的查询限制。子任务 1查询次数限制查询次数限制刚好为 $\frac{N1}{2}$。因为一开始不知道任何数所以需要先询问范围 $[1, 10^{18}]$ 获得全局最大最小值。之后考虑怎么每一次都能获取之前没有获取过的值从而在次数范围内获取序列内的所有数——方法很简单每次查询 $[s, t]$ 后设获得的值为 $mn, mx$则下一次查询 $[mn 1, mx - 1]$。这样每次查询都恰好取到一对新数左右两端各一个$\frac{N1}{2}$ 次查询正好取完所有 $N$ 个数。子任务 2询问区间大小限制子任务 2 要求询问区间内的数的数量之和不能超过 $3N$所以要最小化询问区间。子任务 1 的方法不再可用因为其询问区间内的数数量之和规模为 $O(N^2)$。可以考虑二分值域但这种方法并不可靠最坏可能被卡到 $O(N^2)$。我们需要更有效的划分值域的方法避免查询区间内的点重复查询、浪费机会。考虑到答案不会小于 $\lfloor\frac{a_n - a_1}{N - 1}\rfloor$这是相邻差值的理论下界所以可以按这个值划分值域设 $i$ 初始为 0$ans$ 初始为上述值每次询问 $[i, i ans]$ 并更新 $ans$用取到的相邻差值更新之后再以 $ans$ 为步长让 $i$ 自增。这种方法避免了重复查询总询问区间内的数数量满足限制。不过这种方法也不能很好地适用于子任务 1因为最坏情况下很多询问的值域内可能一个数都没有。参考代码Grader 交互风格包含gap.h头文件#include algorithm #include cstdio #include gap.h long long findGap(int T, int N) { static long long a[100005] {}, ans 0; long long s 0, t 1e18, s1, t1; if (T 1) { int l 1, r N; while (l r) { MinMax(s, t, s1, t1); a[l] s1, a[r--] t1; s s1 1, t t1 - 1; } for (int i 2; i N; i) ans std::max(ans, a[i] - a[i - 1]); } else if (T 2) { MinMax(s, t, s1, t1); ans (t1 - s1) / (N - 1); long long l s1 1, r t1, last s1; for (long long i l; i r;) { MinMax(i, i ans, s1, t1); i ans 1; if (s1 ! -1) ans std::max(ans, s1 - last), last t1; } } return ans; }4. CF750F New Year and Finding Roots题意给定一棵完全二叉树高度 $h \le 7$共 $2^h - 1$ 个节点节点编号未知选手每次询问一个节点交互器返回其邻居数量 $k$$1 \le k \le 3$及所有邻居编号。需要在最多 16 次询问内找到根节点。思路分析$h \le 7$、询问次数 $\le 16$ 的严格要求要求我们非常严格地最大化利用每次访问获得的信息。$h \le 4$ 时可以直接暴力枚举。随机撒点不是好方法随机撒点无法确定自己是否足够接近根节点且单纯随机撒点至少有一次碰到根节点的概率为 $1 - \left(\frac{2^h - 2}{2^h - 1}\right)$即使排除重复撒点的情况后碰到根节点的概率仍然非常小。由于 $1 \le k \le 3$并且我们并不知道哪一边更接近根节点所以考虑最坏情况如果 $k 3$ 时前两次遍历方向都是远离根节点的第三次遍历方向是接近根节点的所以必须往三个方向都遍历。考虑 bfs 和 dfs 两种遍历方法由于 bfs 搜索树可能很大优先考虑 dfs。当然如果知道当前深度并且当前深度小到深度范围内的搜索树规模小于等于剩余次数就可以直接 bfs。关键洞察——如何确定方向与深度知道当前节点的深度以及当前遍历方向会获得很大优势然而当前在往根节点还是往叶子节点遍历是非常难判断的。如果使用 dfs只有当遍历到根节点$k 2$或者叶子节点$k 1$时才知道当前方向。所以需要尽可能知道当前节点深度且不能采用类似迭代加深搜索的方法在遍历中途停下来。考虑随机一个初始节点从初始节点出发可能碰到最坏情况如果 $k 1$就可以直接知道当前节点的深度是叶子如果 $k 2$当前节点即根节点如果 $k 3$直接考虑往三个方向 dfs。其中两个方向是直接往叶子节点的方向遍历路径长度相同另一个方向是往根节点的方向不过可能中途不小心往叶子节点方向走了遍历路径长度会较大。此时就可以计算出当前节点的深度。当 $k 1$ 或 $k 3$ 时需要考虑较长的遍历路径。可以知道路径上深度最小的点必定比初始节点深度小。如果为访问过的节点打标记、不再遍历此时从该节点开始就只有一条遍历路径。虽然这条路径可能还是会走向叶子节点但是这条路径上同样必然存在深度比起点小的节点就可以从这个节点开始继续重复上面的步骤。最坏情况分析考虑 $h 7$ 的最坏情况每次只往根节点走一步就直接往叶子节点走如果只 dfs最坏需要 $\frac{(1 7) \times 7}{2} 28$ 次询问。不过已经知道初始节点的深度所以可以算出所有已遍历节点的深度并判断是否可以从深度最小的点直接 bfs。此时可以算出最坏需要 17 次还差 1 次。于是考虑从搜索树上去掉一个节点当进行深度为 $k$ 的 bfs 时搜索树节点最坏有 $2^k - 1$ 个可能需要 $2^k - 1$ 次询问才能确定哪个节点的邻居恰有 2 个但如果已经对其中 $2^k - 2$ 个节点询问后可以知道最后一个节点肯定是根节点。此时最坏情况下的最优解为$h 7$ 时从叶子节点 dfs每次都是只往根节点走一步就直接往叶子节点走询问 10 次后当前已知最小深度的节点深度为 4。由于已知其父亲直接从其父亲开始 bfs搜索树深度为 3节点数为 $2^3 - 1 7$。在 bfs 时询问了 $2^3 - 2 6$ 次后确定 bfs 搜索树上最后一个节点为根节点。此时算法可以刚好卡到最坏 16 次。参考代码#include algorithm #include cstdio #include queue #include vector using namespace std; constexpr int N 256 5; int T, h, chance; bool ok; vectorint to[N], path; bool read(int x) { if (to[x].empty()) { printf(? %d\n, x), fflush(stdout); int k, t; scanf(%d, k); if (k 0) exit(0); for (int i 0; i k; i) { scanf(%d, t); to[x].push_back(t); } if (k 2) { printf(! %d\n, x), fflush(stdout); return ok true; } chance--; } return false; } bool dfs(int x) { if (to[x].empty()) path.push_back(x); if (read(x)) return true; for (int i : to[x]) if (to[i].empty()) return dfs(i); return false; } void bfs(int s, int k) { queueint q; for (int i : to[s]) if (to[i].empty()) q.push(i); for (int i 1; i k; i) { int x q.front(); q.pop(); if (read(x)) return; for (int j : to[x]) if (to[j].empty()) q.push(j); } for (int i 1; i k; i) { int x q.front(); q.pop(); if (read(x)) return; } printf(! %d\n, q.front()), fflush(stdout); } int main() { for (scanf(%d, T); T--;) { ok false; for (int i 0; i N; i) to[i].clear(); chance 16; scanf(%d, h); if (h 0) exit(0); vectorint long_path; if (read(1)) continue; int root, dep; if (to[1].size() 1) root 1, dep h; else { for (int i : to[1]) { path.clear(); if (dfs(i)) break; if (path.size() long_path.size()) swap(path, long_path); } if (ok) continue; dep h - (path.size() long_path.size()) / 2; root long_path.at((long_path.size() - (h - dep)) - 1); } while ((1 (dep - 1)) - 2 chance) { path.clear(); if (dfs(root)) break; dep h - (h - dep path.size()) / 2; root path.at((path.size() - (h - dep)) - 1); } if (!ok) bfs(root, 1 (dep - 2)); } return 0; }注意代码中的chance变量在每次read真实询问时递减配合while循环条件(1 (dep - 1)) - 2 chance动态判断当前剩余次数是否足够直接 bfs正是把询问次数当作一等公民资源来管理的体现。5. UVa12731 太空站之谜 Mysterious Space Station题意在一个 $n \times m$ 的地图上选手需要远程操控一个机器人探索未知区域找出所有传送门的位置及其配对关系。机器人的唯一反馈是移动时是否撞墙。思路分析由于唯一的反馈是移动时是否撞墙所以应该考虑在机器人不走丢的情况下尽量接近墙边走路。这样做有两个好处靠近墙边走路时很容易知道自己会不会撞墙获取到尽量多的信息墙边都是不会出现传送门的格子可以避免机器人走丢。单手扶墙法如果已知机器人可能在墙边的某个位置要确定机器人是否真的在这个位置就可以通过单手扶墙法确定自己是否真的在这个位置。根据拓扑学原理在两边都是墙的迷宫中如果从入口进入并且总是用一只手扶着同一边墙就可以保证找到出口。由于本题中的墙是闭合的所以只需要沿着墙边的道路走就可以保证回到原点而不会撞墙。另外由于墙边的道路是地图上的最大闭合回路实际代码中并不需要特意撞墙以保证机器人在墙边可以使用标记在地图中标明墙边道路参考代码中的Path状态。而且一旦撞了墙就需要赶快沿着原路返回可以在避免机器人走丢的同时减少步数。由此可以推断出确定机器人是否在特定格子的试错法将机器人从不走到未知格子或已知传送门的情况下走到墙边的道路上然后绕着墙边道路走一圈。这个过程中如果没有撞墙就可以确定机器人确实在特定格子。算法流程初始化一开始标出图中所有未知格子Unknown将所有与墙相邻的格子标记为墙边道路Path并预计算出墙边回路的行走路径。找出传送门从上到下、从左到右依次判断每个未知格子是否是传送门。可以先走到未知格子上方然后向下、向左走再用上面的试错法判断机器人是不是在未知格子的左侧。如果不是说明机器人不在应该在的位置即该未知格子是传送门并将其周围 8 个方向的相邻未知格子标记为普通空地Space。配对传送门找出 $2k$ 个未知格子后需要判断配对关系。实际方法很简单——直接暴力配对。由于 $k \le 5$最多只需要 $9 7 5 3$ 次试错法每对一组的代价递减。作为对比判断图中全部未知格子的情况最多需要 $121 - 40$ 次试错法。回答将 $k$ 组配对输出。关于代码的可用性说明OI Wiki 文档特别注明下面的代码只能通过 UOJ 的镜像题《#247.【Rujia Lius Present 7】Mysterious Space Station》而无法通过 UVa 原题——修改了 UOJ 上刘汝佳的标程后仍无法通过 UVa 原题并且暂时无法联系到刘汝佳所以代码以 UOJ 为准。同时文档指出刘汝佳的标程质量比下面这份代码高很多同一份数据下标程使用的移动次数非常少。参考代码#include algorithm #include cstdio #include cstring #include iostream #include queue #include stack #define Wall 0 #define Unknown 1 #define Space 2 #define Gate 3 #define Path 4 const int N 20; const int dir[8][2] {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {-1, 1}, {1, 1}, {1, -1}, {-1, -1}}; const char dirs[5] ESWN; int n, m, k; int a[N][N], id[N][N]; struct point { int x, y; point(int x 0, int y 0) : x(x), y(y) {} bool operator(const point tmp) const { return x tmp.x y tmp.y; } bool operator!(const point tmp) const { return !(*this tmp); } point side(int d) const { return point(x dir[d][0], y dir[d][1]); } int check(int d) { return a[x dir[d][0]][y dir[d][1]]; } int id() { return ::id[x][y]; } } start; std::vectorstd::pairpoint, int path; std::pairpoint, point ans[N]; std::pairpoint, bool vis[N]; bool walk(int d) { printf(MoveRobot %c\n, dirs[d]); fflush(stdout); int ret; scanf(%d, ret); return ret; } bool walk(int d, std::stackint st) { if (walk(d)) { st.push(d); return true; } return false; } bool read() { if (scanf(%d%d%d, n, m, k) ! 3) return false; if (n 0) return false; memset(a, 0, sizeof(a)); for (int i 0; i n; i) for (int j 0; j m; j) { char c; std::cin c; if (c S) start point(i, j); if (c *) a[i][j] Wall; else a[i][j] Unknown; } return true; } void answer() { for (int i 0; i k; i) printf(Answer %d %d\n, ans[i].first.id(), ans[i].second.id()); fflush(stdout); } // 单手扶墙法因为靠墙的 Path 是极大闭合环所以只需要在沿着 Path // 走的过程中没有碰到障碍就可以了 void wall_follower_init(point x, int last, int wallside, point s) { if (x s !path.empty()) return; if (x.check(wallside) Path) { path.push_back(std::make_pair(x, wallside)); wall_follower_init(x.side(wallside), wallside, last ^ 2, s); } else if (x.check(last) Wall) { for (int i 0; i 4; i) if (i ! (last ^ 2) x.check(i) ! Wall) { path.push_back(std::make_pair(x, i)); wall_follower_init(x.side(i), i, last, s); return; } } else { path.push_back(std::make_pair(x, last)); wall_follower_init(x.side(last), last, wallside, s); } } void init() { int cnt 1; for (int i 0; i n; i) for (int j 0; j m; j) { if (a[i][j] Unknown) { id[i][j] cnt; for (int k 0; k 8; k) if (point(i, j).check(k) Wall) { a[i][j] Path; break; } } else id[i][j] 0; } path.clear(); int wallside 0, last 0; for (int i 0; i 4; i) if (start.check(i) Wall) { wallside i; break; } for (int i 0; i 4; i) if (start.check(i) Path i ! (wallside ^ 2)) { last i; break; } wall_follower_init(start, last, wallside, start); } void undo(std::stackint st) { while (!st.empty()) walk(st.top() ^ 2), st.pop(); } bool wall_follower(point x) { std::stackint st; bool ok true; int i 0; while (i path.size() path[i].first ! x) i; for (int j i; ok j path.size(); j) { if (walk(path[j].second)) st.push(path[j].second); else ok false; } for (int j 0; ok j i; j) { if (walk(path[j].second)) st.push(path[j].second); else ok false; } if (!ok) undo(st); return ok; } // 确定自己当前在 // x使用「摸着石头过河」的方法只需要沿着可以避开障碍、未知格子和传送门的方向走到 // Path 就行 在找传送门和配对传送门时使用 void bfs(point s, point t, std::vectorint v) { static int map[N][N] {}; memset(map, -1, sizeof(map)); std::queuepoint q; map[s.x][s.y] 4; q.push(s); while (!q.empty()) { point x q.front(); q.pop(); if (x t) break; for (int i 0; i 4; i) { point y x.side(i); if ((x.check(i) Path || x.check(i) Space) map[y.x][y.y] -1) { map[y.x][y.y] i; q.push(y); } } } for (point x t; x ! s; x x.side(map[x.x][x.y] ^ 2)) { v.push_back(map[x.x][x.y]); } std::reverse(v.begin(), v.end()); } bool move(point s, point t, std::stackint st) { // 在靠近传送门时使用 static std::vectorint v; v.clear(); bfs(s, t, v); for (int i : v) if (!walk(i, st)) return false; return true; } // 尽可能快地向墙边移动 bool make_sure(point x, int last) { if (a[x.x][x.y] Path) return wall_follower(x); for (int i 0; i 4; i) if ((x.check(i) Path || x.check(i) Space) i ! (last ^ 2)) { if (!walk(i)) return false; bool ret make_sure(x.side(i), i); walk(i ^ 2); return ret; } return false; } void find_gate() { int cnt 0; std::stackint st; for (int i 0; i n; i) for (int j 0; j m; j) if (cnt k * 2 a[i][j] Unknown) a[i][j] Space; else if (a[i][j] Unknown) { bool ok true; if (!move(start, point(i - 1, j), st)) ok false; else if (!walk(1, st)) ok false; else if (!walk(2, st)) ok false; else if (!make_sure(point(i, j - 1), -1)) ok false; if (!ok) { vis[cnt] std::make_pair(point(i, j), false); a[i][j] Gate; for (int k 0; k 8; k) { point y point(i, j).side(k); if (point(i, j).check(k) Unknown) a[y.x][y.y] Space; } } else a[i][j] Space; undo(st); } } void make_gate_pair() { int cnt 0; std::stackint st; for (int i 0; i k * 2; i) if (!vis[i].second) for (int j 0; !vis[i].second j k * 2; j) if (j ! i !vis[j].second) { bool ok true; if (!move(start, vis[i].first.side(2), st)) ok false; else if (!walk(0, st)) ok false; else if (!make_sure(vis[j].first.side(0), -1)) ok false; if (ok) { ans[cnt] std::make_pair(vis[i].first, vis[j].first); vis[i].second vis[j].second true; } undo(st); } } int main() { while (read()) { init(); find_gate(); make_gate_pair(); answer(); } return 0; }这道题的参考代码体现了交互题中几个重要的工程技巧将地图状态用Wall / Unknown / Space / Gate / Path五种标记显式建模用undo()配合栈实现撞墙后沿原路返回所有输出MoveRobot、Answer都紧跟fflush(stdout)。七、习题推荐与拓展阅读OI Wiki 的交互题文档推荐的进阶练习刘汝佳的交互题专场比赛 Rujia Lius Present 7质量非常高推荐一做包含前文的太空站之谜。P5473[NOI2019]I 君的探险2019 年 NOI 交互题考察随机化与图论结合的能力。P5208[WC2019]I 君的商店2019 年 WC 交互题考察二分与询问策略设计。关于交互题评测原理的延伸阅读OI Wiki 文档推荐了用 Linux 管道实现 online judge 的交互题功能的思路——本质上STDIO 交互题就是评测系统通过管道将选手程序与交互器程序的标准输入输出连接起来选手输出的询问经管道送入交互器交互器的应答再经管道送回选手程序的标准输入。理解了这一数据流模型就能更好地把握每次输出后必须刷新缓冲区这条铁律背后的原因。八、结语交互题的核心魅力在于它将算法设计与资源管理紧密结合传统题优化的是时间与空间交互题优化的是询问次数与信息利用效率。从本文五道例题可以看到解决交互题通常需要三个层次的思考协议层严格遵守输出格式、及时刷新缓冲区、按协议读入全部数据否则触发 ILE / PV / PLE策略层设计询问策略使每次询问都能获取最大化的新信息如 Gap 的两段式查询、Finding Roots 的方向与深度推断工程层封装输入输出函数、模拟交互过程调试、为访问过的节点打标记避免重复询问。在 OI Wiki 中交互题的完整知识体系还包括题型分类总览docs/contest/problems.md与 I/O 优化原理docs/contest/io.md建议与本文对照阅读形成从题型认知到代码实现的完整闭环。【免费下载链接】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 的交互题专题文档docs/contest/interaction.md为骨架结合仓库中关于题型分类与输入输出优化的配套文档系统讲解交互题的两种交互方式、评测结果判定规则、缓冲区刷新的关键陷阱、调试手段并逐题剖析 Bear and Prime 100、Interactive LowerBound、APIO2016 Gap、New Year and Finding Roots、太空站之谜五道经典例题及其完整参考代码帮助读者从会写交互代码进阶到能在交互次数限制内稳定 AC。一、交互题背景、定位与学习建议交互题并非新题型——上个世纪的 IOI 就已涉及。虽然交互题在相当长一段时间内未出现在省选以下的比赛中但 2019 年 NOI 系列比赛中连续出现两道交互题《P5208[WC2019]I 君的商店》与《P5473[NOI2019]I 君的探险》这可能代表着交互题重新回到 NOI 系列比赛中。因此掌握交互题对参加 NOI 系列赛事的选手具有现实意义。交互题有着鲜明的特点前置算法要求不高交互题一般没有很高的前置算法门槛通常也没有严格的时间限制。核心约束是交互次数程序的优秀程度往往仅取决于交互次数限制而非运行速度或常数优化。适合锻炼算法思维如果只想学习算法本身交互题未必是最佳载体但若想有意识地锻炼算法思维完成交互题是很不错的方法。建议循序渐进虽然交互题对选手已掌握算法的要求通常较低但仍建议掌握一定提高和省选算法后再尝试做交互题因为此时算法思维水平和知识面已达到一定水准更容易体会到交互题的精妙之处。基础的交互题题型介绍可参见 OI Wiki 的 题型介绍 - 交互题。二、两种交互方式STDIO 交互与 Grader 交互根据 docs/contest/problems.md 的说明交互题在技术实现上主要分为两种方式。虽然技术上有不小的差异但在考察算法的本质上二者没有实际区别。STDIO 交互标准 I/O 交互STDIO 交互是 Codeforces、AtCoder 等在线平台的交互手段也是 ICPC 系列赛事中的标准。这类题目中选手只需像往常一样将询问写到标准输出刷新输出缓冲后从标准输入读取结果。关键点在于选手程序刷新输出缓冲后通过管道连接它的测评程序交互器才能立刻接收到数据。在 C/C 中fflush(stdout)和std::cout std::flush可以实现这个操作使用std::cout std::endl换行时也会自动刷新缓冲区但是std::cout \n不会Pascal 则使用flush(output)。STDIO 交互的一个明显优势在于它可以支持任何编程语言但输入输出的耗时容易成为问题设计的瓶颈有时导致评测系统无法区分程序的时间效率差别。Grader 交互Grader 交互方式常见于 IOI、APIO 等国际 OI 赛事特别是 CMS 平台的竞赛。这类题目中选手只需编写一个特定的函数完成某项任务通过调用题目给定的若干辅助函数来进行交互。为了便于选手在本地测试题目会下发一个头文件与一个参考测评程序grader.cpp对于 Pascal 语言是一个库graderlib选手将自己的程序与grader.cpp一同编译方可得到可执行文件g grader.cpp my_solution.cpp -o my_solution -Wall -O2 ./my_solution # 执行程序编译得到的程序表现与传统题程序类似它会打开固定的文件以固定的格式读取数据调用选手编写的函数并将结果和若干信息例如询问的次数、答案正确性显示在标准输出上。实际测评时选手的程序会与一个不同的grader.cpp编译这个版本一般将所有全局符号设为static防止选手通过命名冲突的方式破解任何尝试突破 grader 限制的行为都会被判失格disqualification。Grader 交互由于函数调用开销不大常常可以允许 $10^6$ 数量级的询问次数但语言的限制是其短板。如果自己设计题目或举办比赛需要对两种交互方式认真权衡。三、交互题的特殊评测结果与常见错误交互题的错误形态与普通传统题不同OI Wiki 的交互题文档专门总结了三种特殊的评测结果1. Idleness limit exceededILE选手每一次输出后都需要刷新缓冲区否则会引起Idleness limit exceeded错误。这一错误的本质是交互器在等待选手程序的输出而选手程序的输出仍滞留在缓冲区中没有被刷新。另外需要特别注意如果题目含多组数据并且程序可以在未读入所有数据前就知道答案也仍然要读入所有数据否则会因为读入混乱引起 ILE。一种可行的策略是一次提出多次询问、一次接收所有询问的回答。同时尽量不要使用快读——快读基于getchar/fread等底层的缓冲机制容易与交互流程产生冲突反而引发读取混乱。2. Wrong AnswerWA与 Protocol Limit ExceededPLE如果程序查询次数过多在 Codeforces 上会给出 Wrong Answer 的评测结果不过评测系统会说明 Wrong Answer 的原因而 UVa 会给出Protocol Limit Exceeded (PLE)的评测结果。3. Protocol ViolationPV如果程序交互格式错误UVa 会给出Protocol Violation (PV)的评测结果。这意味着选手的输出不符合题目约定的交互协议格式。小结交互题的两种典型失败模式失败类型触发原因对应平台判定ILE输出后未刷新缓冲区 / 未读入全部数据Idleness limit exceeded查询次数超限询问次数超过题目限制Codeforces: WAUVa: PLE交互格式错误输出格式不符合协议UVa: PV四、I/O 封装交互题的工程化基础由于交互题输入输出较为繁琐OI Wiki 建议分别封装输入和输出函数。这样做一方面保证每次输出后刷新缓冲区这一关键动作不被遗漏另一方面让代码逻辑更清晰、更易排查错误。这里需要特别强调刷新缓冲区与 I/O 优化的冲突关系。在 docs/contest/io.md 中介绍了std::ios::sync_with_stdio(false)与std::cin.tie(nullptr)两个常用优化但文档同时警告在同时进行上述两个操作后程序中必须手动flush才能确保每次std::cout展现的内容可以在std::cin前出现——因为此时调用std::cin时std::cout不会自动刷新缓冲区。这与交互题的 ILE 错误直接相关交互题中使用优化后的流式 I/O 时必须在每次询问输出后显式刷新std::flush或std::endl否则交互器将永远等不到选手的询问。此外OI Wiki 在交互题文档中明确建议尽量不要使用快读。仓库 docs/contest/code/io/io_1.cpp 中的getchar/putchar式快读、docs/contest/code/io/io_2.cpp 中的fread/fwrite式快读其核心思路都是将字符流缓存在程序侧手动处理在交互场景中这类底层字符读取与 printf/scanf 混用极易破坏交互协议的同步性因此交互题更推荐朴素的printf/scanf或std::cout/std::cin 显式 flush并做好函数封装。五、交互题的调试grader、checker 与静态查错比赛时如果出题人给出了 grader 头文件用于 grader 交互题的调试或者 checker 程序用于 stdio 交互题的调试交互题的调试会比较简单因为交互题的对拍会比普通题目的对拍困难很多。从工程角度看交互题的调试成本相当可观没有testlib.h的情况下交互细节较多的题目的 stdio 交互库一般有 3k 代码量再加上 3k 长度的对拍器至少需要一小时实现。但无论是否有调试程序调试交互题的代码都往往需要选手模拟与程序的交互过程。因此交互题对选手的要求是能设计出高质量的程序尽量保证一遍做对拥有较强的静态查错能力在无法运行时定位逻辑错误。六、例题精讲1. CF679A Bear and Prime 100题意交互器隐藏一个 $[2,100]$ 内的整数选手最多询问 20 次该数是否被某个数整除判断其是质数还是合数。思路分析每个质数都有且只有两个因数所以直接枚举要猜的数的因数即可。由于限制最多询问 20 次并且对于较大的数如 92尝试分解质因数时发现需要最多枚举到 $\lfloor\frac{n}{2}\rfloor$ 的质数所以我们先筛出 50 以内的质数每次把所有这些数都询问一遍。关键细节本题对拍比较容易可以直接把值域内的数都尝试一遍。此时会发现程序无法有效处理质数的平方——例如 4 只能被 2 整除若只询问 2、3、5、7 等质数无法区分 $4$ 与质数 $2$ 的倍数特征。因此我们要把 $2,3,5,7$ 的平方 $4,9,25,49$ 都放进去总共 19 个数字符合 20 次询问限制。一旦出现两个是的回答例如 $4$ 被 $2$ 和 $4$ 都整除即可判定为合数。参考代码完整代码来自 docs/contest/interaction.md#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; }注意代码中每次printf后紧跟fflush(stdout)这正是交互题输出铁律的体现。2. CF843B Interactive LowerBound题意给定一个长度为 $n$$n \le 5 \times 10^4$的单向链表已知首元素下标start元素值严格递增。选手每次可询问一个下标得到该下标的元素值及其后继下标最多询问 1999 次求链表中第一个值不小于 $x$ 的元素。思路分析链表最多有 $5 \times 10^4$ 个元素但只能询问 1999 次并且只能获取元素的后一个元素所以普通的遍历整个链表的方法不可用。直接设法逼近目标元素的位置只有一种方法随机撒点。对于 $n 2000$ 的情况直接枚举依次询问每个下标取所有值不小于 $x$ 的元素中的最小值。对于 $n \ge 2000$ 的情况直接撒 1000 个点。由于元素值严格递增这些点之间的期望距离很小可以从小于 $x$ 的最大值开始向后遍历——可以证明在到达下一个撒点之前我们就已得到答案。遍历过程中一旦找到大于等于 $x$ 的元素就可以直接推出答案。虽然整体思路简单但实际情况下如果没有学习过模拟退火等非完美随机算法思考起来可能会困难一些。关键细节——随机种子由于 Codeforces 具有 hack 机制很多人会刻意卡掉没有初始化随机种子的代码所以在random_shuffle()函数前需要srand((size_t)new char)——用动态分配的内存地址作为随机种子每次运行都不同无法被 hack 预测。参考代码#include algorithm #include cstdio #include cstdlib constexpr int N 50005; int n, start, x; int a[N]; int main() { scanf(%d%d%d, n, start, x); if (n 2000) { int ans 2e9; for (int i 1; i n; i) { printf(? %d\n, i), fflush(stdout); int val, next; scanf(%d%d, val, next); if (val x) ans std::min(ans, val); } if (ans 2e9) ans -1; printf(! %d, ans), fflush(stdout); } else { srand((size_t) new char); int p start, ans 0; for (int i 1; i n; i) a[i] i; std::random_shuffle(a 1, a n 1); for (int i 1; i 1000; i) { printf(? %d\n, a[i]), fflush(stdout); int val, next; scanf(%d%d, val, next); if (val x val ans) p a[i], ans val; } while (p ! -1 ans x) { printf(? %d\n, p), fflush(stdout); int val, next; scanf(%d%d, val, next); ans val; p next; } if (ans x) ans -1; printf(! %d, ans), fflush(stdout); } return 0; }本代码展示了一个交互题的完整流程骨架?为询问指令、!为回答指令每次输出后立即fflush(stdout)。3. UOJ206 [APIO2016] Gap题意有 $N$ 个严格递增的非负整数 $a_1, a_2, \cdots, a_N$$0 \le a_1 a_2 \cdots a_N \le 10^{18}$选手不能直接读入序列但可以通过 grader 提供的MinMax(s, t, mn, mx)函数查询区间 $[s,t]$ 内的最小值和最大值若区间内无数则返回 -1。求相邻两数差的最大值。本题分两个子任务分别考察不同的查询限制。子任务 1查询次数限制查询次数限制刚好为 $\frac{N1}{2}$。因为一开始不知道任何数所以需要先询问范围 $[1, 10^{18}]$ 获得全局最大最小值。之后考虑怎么每一次都能获取之前没有获取过的值从而在次数范围内获取序列内的所有数——方法很简单每次查询 $[s, t]$ 后设获得的值为 $mn, mx$则下一次查询 $[mn 1, mx - 1]$。这样每次查询都恰好取到一对新数左右两端各一个$\frac{N1}{2}$ 次查询正好取完所有 $N$ 个数。子任务 2询问区间大小限制子任务 2 要求询问区间内的数的数量之和不能超过 $3N$所以要最小化询问区间。子任务 1 的方法不再可用因为其询问区间内的数数量之和规模为 $O(N^2)$。可以考虑二分值域但这种方法并不可靠最坏可能被卡到 $O(N^2)$。我们需要更有效的划分值域的方法避免查询区间内的点重复查询、浪费机会。考虑到答案不会小于 $\lfloor\frac{a_n - a_1}{N - 1}\rfloor$这是相邻差值的理论下界所以可以按这个值划分值域设 $i$ 初始为 0$ans$ 初始为上述值每次询问 $[i, i ans]$ 并更新 $ans$用取到的相邻差值更新之后再以 $ans$ 为步长让 $i$ 自增。这种方法避免了重复查询总询问区间内的数数量满足限制。不过这种方法也不能很好地适用于子任务 1因为最坏情况下很多询问的值域内可能一个数都没有。参考代码Grader 交互风格包含gap.h头文件#include algorithm #include cstdio #include gap.h long long findGap(int T, int N) { static long long a[100005] {}, ans 0; long long s 0, t 1e18, s1, t1; if (T 1) { int l 1, r N; while (l r) { MinMax(s, t, s1, t1); a[l] s1, a[r--] t1; s s1 1, t t1 - 1; } for (int i 2; i N; i) ans std::max(ans, a[i] - a[i - 1]); } else if (T 2) { MinMax(s, t, s1, t1); ans (t1 - s1) / (N - 1); long long l s1 1, r t1, last s1; for (long long i l; i r;) { MinMax(i, i ans, s1, t1); i ans 1; if (s1 ! -1) ans std::max(ans, s1 - last), last t1; } } return ans; }4. CF750F New Year and Finding Roots题意给定一棵完全二叉树高度 $h \le 7$共 $2^h - 1$ 个节点节点编号未知选手每次询问一个节点交互器返回其邻居数量 $k$$1 \le k \le 3$及所有邻居编号。需要在最多 16 次询问内找到根节点。思路分析$h \le 7$、询问次数 $\le 16$ 的严格要求要求我们非常严格地最大化利用每次访问获得的信息。$h \le 4$ 时可以直接暴力枚举。随机撒点不是好方法随机撒点无法确定自己是否足够接近根节点且单纯随机撒点至少有一次碰到根节点的概率为 $1 - \left(\frac{2^h - 2}{2^h - 1}\right)$即使排除重复撒点的情况后碰到根节点的概率仍然非常小。由于 $1 \le k \le 3$并且我们并不知道哪一边更接近根节点所以考虑最坏情况如果 $k 3$ 时前两次遍历方向都是远离根节点的第三次遍历方向是接近根节点的所以必须往三个方向都遍历。考虑 bfs 和 dfs 两种遍历方法由于 bfs 搜索树可能很大优先考虑 dfs。当然如果知道当前深度并且当前深度小到深度范围内的搜索树规模小于等于剩余次数就可以直接 bfs。关键洞察——如何确定方向与深度知道当前节点的深度以及当前遍历方向会获得很大优势然而当前在往根节点还是往叶子节点遍历是非常难判断的。如果使用 dfs只有当遍历到根节点$k 2$或者叶子节点$k 1$时才知道当前方向。所以需要尽可能知道当前节点深度且不能采用类似迭代加深搜索的方法在遍历中途停下来。考虑随机一个初始节点从初始节点出发可能碰到最坏情况如果 $k 1$就可以直接知道当前节点的深度是叶子如果 $k 2$当前节点即根节点如果 $k 3$直接考虑往三个方向 dfs。其中两个方向是直接往叶子节点的方向遍历路径长度相同另一个方向是往根节点的方向不过可能中途不小心往叶子节点方向走了遍历路径长度会较大。此时就可以计算出当前节点的深度。当 $k 1$ 或 $k 3$ 时需要考虑较长的遍历路径。可以知道路径上深度最小的点必定比初始节点深度小。如果为访问过的节点打标记、不再遍历此时从该节点开始就只有一条遍历路径。虽然这条路径可能还是会走向叶子节点但是这条路径上同样必然存在深度比起点小的节点就可以从这个节点开始继续重复上面的步骤。最坏情况分析考虑 $h 7$ 的最坏情况每次只往根节点走一步就直接往叶子节点走如果只 dfs最坏需要 $\frac{(1 7) \times 7}{2} 28$ 次询问。不过已经知道初始节点的深度所以可以算出所有已遍历节点的深度并判断是否可以从深度最小的点直接 bfs。此时可以算出最坏需要 17 次还差 1 次。于是考虑从搜索树上去掉一个节点当进行深度为 $k$ 的 bfs 时搜索树节点最坏有 $2^k - 1$ 个可能需要 $2^k - 1$ 次询问才能确定哪个节点的邻居恰有 2 个但如果已经对其中 $2^k - 2$ 个节点询问后可以知道最后一个节点肯定是根节点。此时最坏情况下的最优解为$h 7$ 时从叶子节点 dfs每次都是只往根节点走一步就直接往叶子节点走询问 10 次后当前已知最小深度的节点深度为 4。由于已知其父亲直接从其父亲开始 bfs搜索树深度为 3节点数为 $2^3 - 1 7$。在 bfs 时询问了 $2^3 - 2 6$ 次后确定 bfs 搜索树上最后一个节点为根节点。此时算法可以刚好卡到最坏 16 次。参考代码#include algorithm #include cstdio #include queue #include vector using namespace std; constexpr int N 256 5; int T, h, chance; bool ok; vectorint to[N], path; bool read(int x) { if (to[x].empty()) { printf(? %d\n, x), fflush(stdout); int k, t; scanf(%d, k); if (k 0) exit(0); for (int i 0; i k; i) { scanf(%d, t); to[x].push_back(t); } if (k 2) { printf(! %d\n, x), fflush(stdout); return ok true; } chance--; } return false; } bool dfs(int x) { if (to[x].empty()) path.push_back(x); if (read(x)) return true; for (int i : to[x]) if (to[i].empty()) return dfs(i); return false; } void bfs(int s, int k) { queueint q; for (int i : to[s]) if (to[i].empty()) q.push(i); for (int i 1; i k; i) { int x q.front(); q.pop(); if (read(x)) return; for (int j : to[x]) if (to[j].empty()) q.push(j); } for (int i 1; i k; i) { int x q.front(); q.pop(); if (read(x)) return; } printf(! %d\n, q.front()), fflush(stdout); } int main() { for (scanf(%d, T); T--;) { ok false; for (int i 0; i N; i) to[i].clear(); chance 16; scanf(%d, h); if (h 0) exit(0); vectorint long_path; if (read(1)) continue; int root, dep; if (to[1].size() 1) root 1, dep h; else { for (int i : to[1]) { path.clear(); if (dfs(i)) break; if (path.size() long_path.size()) swap(path, long_path); } if (ok) continue; dep h - (path.size() long_path.size()) / 2; root long_path.at((long_path.size() - (h - dep)) - 1); } while ((1 (dep - 1)) - 2 chance) { path.clear(); if (dfs(root)) break; dep h - (h - dep path.size()) / 2; root path.at((path.size() - (h - dep)) - 1); } if (!ok) bfs(root, 1 (dep - 2)); } return 0; }注意代码中的chance变量在每次read真实询问时递减配合while循环条件(1 (dep - 1)) - 2 chance动态判断当前剩余次数是否足够直接 bfs正是把询问次数当作一等公民资源来管理的体现。5. UVa12731 太空站之谜 Mysterious Space Station题意在一个 $n \times m$ 的地图上选手需要远程操控一个机器人探索未知区域找出所有传送门的位置及其配对关系。机器人的唯一反馈是移动时是否撞墙。思路分析由于唯一的反馈是移动时是否撞墙所以应该考虑在机器人不走丢的情况下尽量接近墙边走路。这样做有两个好处靠近墙边走路时很容易知道自己会不会撞墙获取到尽量多的信息墙边都是不会出现传送门的格子可以避免机器人走丢。单手扶墙法如果已知机器人可能在墙边的某个位置要确定机器人是否真的在这个位置就可以通过单手扶墙法确定自己是否真的在这个位置。根据拓扑学原理在两边都是墙的迷宫中如果从入口进入并且总是用一只手扶着同一边墙就可以保证找到出口。由于本题中的墙是闭合的所以只需要沿着墙边的道路走就可以保证回到原点而不会撞墙。另外由于墙边的道路是地图上的最大闭合回路实际代码中并不需要特意撞墙以保证机器人在墙边可以使用标记在地图中标明墙边道路参考代码中的Path状态。而且一旦撞了墙就需要赶快沿着原路返回可以在避免机器人走丢的同时减少步数。由此可以推断出确定机器人是否在特定格子的试错法将机器人从不走到未知格子或已知传送门的情况下走到墙边的道路上然后绕着墙边道路走一圈。这个过程中如果没有撞墙就可以确定机器人确实在特定格子。算法流程初始化一开始标出图中所有未知格子Unknown将所有与墙相邻的格子标记为墙边道路Path并预计算出墙边回路的行走路径。找出传送门从上到下、从左到右依次判断每个未知格子是否是传送门。可以先走到未知格子上方然后向下、向左走再用上面的试错法判断机器人是不是在未知格子的左侧。如果不是说明机器人不在应该在的位置即该未知格子是传送门并将其周围 8 个方向的相邻未知格子标记为普通空地Space。配对传送门找出 $2k$ 个未知格子后需要判断配对关系。实际方法很简单——直接暴力配对。由于 $k \le 5$最多只需要 $9 7 5 3$ 次试错法每对一组的代价递减。作为对比判断图中全部未知格子的情况最多需要 $121 - 40$ 次试错法。回答将 $k$ 组配对输出。关于代码的可用性说明OI Wiki 文档特别注明下面的代码只能通过 UOJ 的镜像题《#247.【Rujia Lius Present 7】Mysterious Space Station》而无法通过 UVa 原题——修改了 UOJ 上刘汝佳的标程后仍无法通过 UVa 原题并且暂时无法联系到刘汝佳所以代码以 UOJ 为准。同时文档指出刘汝佳的标程质量比下面这份代码高很多同一份数据下标程使用的移动次数非常少。参考代码#include algorithm #include cstdio #include cstring #include iostream #include queue #include stack #define Wall 0 #define Unknown 1 #define Space 2 #define Gate 3 #define Path 4 const int N 20; const int dir[8][2] {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {-1, 1}, {1, 1}, {1, -1}, {-1, -1}}; const char dirs[5] ESWN; int n, m, k; int a[N][N], id[N][N]; struct point { int x, y; point(int x 0, int y 0) : x(x), y(y) {} bool operator(const point tmp) const { return x tmp.x y tmp.y; } bool operator!(const point tmp) const { return !(*this tmp); } point side(int d) const { return point(x dir[d][0], y dir[d][1]); } int check(int d) { return a[x dir[d][0]][y dir[d][1]]; } int id() { return ::id[x][y]; } } start; std::vectorstd::pairpoint, int path; std::pairpoint, point ans[N]; std::pairpoint, bool vis[N]; bool walk(int d) { printf(MoveRobot %c\n, dirs[d]); fflush(stdout); int ret; scanf(%d, ret); return ret; } bool walk(int d, std::stackint st) { if (walk(d)) { st.push(d); return true; } return false; } bool read() { if (scanf(%d%d%d, n, m, k) ! 3) return false; if (n 0) return false; memset(a, 0, sizeof(a)); for (int i 0; i n; i) for (int j 0; j m; j) { char c; std::cin c; if (c S) start point(i, j); if (c *) a[i][j] Wall; else a[i][j] Unknown; } return true; } void answer() { for (int i 0; i k; i) printf(Answer %d %d\n, ans[i].first.id(), ans[i].second.id()); fflush(stdout); } // 单手扶墙法因为靠墙的 Path 是极大闭合环所以只需要在沿着 Path // 走的过程中没有碰到障碍就可以了 void wall_follower_init(point x, int last, int wallside, point s) { if (x s !path.empty()) return; if (x.check(wallside) Path) { path.push_back(std::make_pair(x, wallside)); wall_follower_init(x.side(wallside), wallside, last ^ 2, s); } else if (x.check(last) Wall) { for (int i 0; i 4; i) if (i ! (last ^ 2) x.check(i) ! Wall) { path.push_back(std::make_pair(x, i)); wall_follower_init(x.side(i), i, last, s); return; } } else { path.push_back(std::make_pair(x, last)); wall_follower_init(x.side(last), last, wallside, s); } } void init() { int cnt 1; for (int i 0; i n; i) for (int j 0; j m; j) { if (a[i][j] Unknown) { id[i][j] cnt; for (int k 0; k 8; k) if (point(i, j).check(k) Wall) { a[i][j] Path; break; } } else id[i][j] 0; } path.clear(); int wallside 0, last 0; for (int i 0; i 4; i) if (start.check(i) Wall) { wallside i; break; } for (int i 0; i 4; i) if (start.check(i) Path i ! (wallside ^ 2)) { last i; break; } wall_follower_init(start, last, wallside, start); } void undo(std::stackint st) { while (!st.empty()) walk(st.top() ^ 2), st.pop(); } bool wall_follower(point x) { std::stackint st; bool ok true; int i 0; while (i path.size() path[i].first ! x) i; for (int j i; ok j path.size(); j) { if (walk(path[j].second)) st.push(path[j].second); else ok false; } for (int j 0; ok j i; j) { if (walk(path[j].second)) st.push(path[j].second); else ok false; } if (!ok) undo(st); return ok; } // 确定自己当前在 // x使用「摸着石头过河」的方法只需要沿着可以避开障碍、未知格子和传送门的方向走到 // Path 就行 在找传送门和配对传送门时使用 void bfs(point s, point t, std::vectorint v) { static int map[N][N] {}; memset(map, -1, sizeof(map)); std::queuepoint q; map[s.x][s.y] 4; q.push(s); while (!q.empty()) { point x q.front(); q.pop(); if (x t) break; for (int i 0; i 4; i) { point y x.side(i); if ((x.check(i) Path || x.check(i) Space) map[y.x][y.y] -1) { map[y.x][y.y] i; q.push(y); } } } for (point x t; x ! s; x x.side(map[x.x][x.y] ^ 2)) { v.push_back(map[x.x][x.y]); } std::reverse(v.begin(), v.end()); } bool move(point s, point t, std::stackint st) { // 在靠近传送门时使用 static std::vectorint v; v.clear(); bfs(s, t, v); for (int i : v) if (!walk(i, st)) return false; return true; } // 尽可能快地向墙边移动 bool make_sure(point x, int last) { if (a[x.x][x.y] Path) return wall_follower(x); for (int i 0; i 4; i) if ((x.check(i) Path || x.check(i) Space) i ! (last ^ 2)) { if (!walk(i)) return false; bool ret make_sure(x.side(i), i); walk(i ^ 2); return ret; } return false; } void find_gate() { int cnt 0; std::stackint st; for (int i 0; i n; i) for (int j 0; j m; j) if (cnt k * 2 a[i][j] Unknown) a[i][j] Space; else if (a[i][j] Unknown) { bool ok true; if (!move(start, point(i - 1, j), st)) ok false; else if (!walk(1, st)) ok false; else if (!walk(2, st)) ok false; else if (!make_sure(point(i, j - 1), -1)) ok false; if (!ok) { vis[cnt] std::make_pair(point(i, j), false); a[i][j] Gate; for (int k 0; k 8; k) { point y point(i, j).side(k); if (point(i, j).check(k) Unknown) a[y.x][y.y] Space; } } else a[i][j] Space; undo(st); } } void make_gate_pair() { int cnt 0; std::stackint st; for (int i 0; i k * 2; i) if (!vis[i].second) for (int j 0; !vis[i].second j k * 2; j) if (j ! i !vis[j].second) { bool ok true; if (!move(start, vis[i].first.side(2), st)) ok false; else if (!walk(0, st)) ok false; else if (!make_sure(vis[j].first.side(0), -1)) ok false; if (ok) { ans[cnt] std::make_pair(vis[i].first, vis[j].first); vis[i].second vis[j].second true; } undo(st); } } int main() { while (read()) { init(); find_gate(); make_gate_pair(); answer(); } return 0; }这道题的参考代码体现了交互题中几个重要的工程技巧将地图状态用Wall / Unknown / Space / Gate / Path五种标记显式建模用undo()配合栈实现撞墙后沿原路返回所有输出MoveRobot、Answer都紧跟fflush(stdout)。七、习题推荐与拓展阅读OI Wiki 的交互题文档推荐的进阶练习刘汝佳的交互题专场比赛 Rujia Lius Present 7质量非常高推荐一做包含前文的太空站之谜。P5473[NOI2019]I 君的探险2019 年 NOI 交互题考察随机化与图论结合的能力。P5208[WC2019]I 君的商店2019 年 WC 交互题考察二分与询问策略设计。关于交互题评测原理的延伸阅读OI Wiki 文档推荐了用 Linux 管道实现 online judge 的交互题功能的思路——本质上STDIO 交互题就是评测系统通过管道将选手程序与交互器程序的标准输入输出连接起来选手输出的询问经管道送入交互器交互器的应答再经管道送回选手程序的标准输入。理解了这一数据流模型就能更好地把握每次输出后必须刷新缓冲区这条铁律背后的原因。八、结语交互题的核心魅力在于它将算法设计与资源管理紧密结合传统题优化的是时间与空间交互题优化的是询问次数与信息利用效率。从本文五道例题可以看到解决交互题通常需要三个层次的思考协议层严格遵守输出格式、及时刷新缓冲区、按协议读入全部数据否则触发 ILE / PV / PLE策略层设计询问策略使每次询问都能获取最大化的新信息如 Gap 的两段式查询、Finding Roots 的方向与深度推断工程层封装输入输出函数、模拟交互过程调试、为访问过的节点打标记避免重复询问。在 OI Wiki 中交互题的完整知识体系还包括题型分类总览docs/contest/problems.md与 I/O 优化原理docs/contest/io.md建议与本文对照阅读形成从题型认知到代码实现的完整闭环。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
