2026/9/9 18:20:04
FEATURED · 精选文章 
每年 Codeforces 的 Div. 4 场次里G 题往往不会用到高深的数据结构但它特别能筛选思维习惯。Round 964 的 G1/G2 Ruler 就是这样一道题表面上是个交互式构造题本质上考的是你建模时能不能把乱七八糟的规则压缩成一个可以二分的判断。作为一名刷过几百道交互题的选手我很负责任地说这道题值得慢下来拆一遍尤其是 Hard 版本它把二分这件事玩得特别纯粹。这篇文章我会从题目背后的构造思维讲起把 Easy 到 Hard 的进化路线、二分边界的推导、交互题常见的坑、以及构造题通用的几种思维模型全部串在一起说最后附上我自己调试这类题时常用的排错清单。整个话题围绕 Codeforces 构造题展开你可以把它当成一篇交互式二分题型的专项复盘来读。1. 构造题到底在考什么1.1 一句话说清构造题Codeforces 的构造题英文叫 Constructive Algorithm题目会给你一个目标状态和若干限制条件要求你构造出一个满足这些条件的方案而不是像普通算法题那样只输出一个最优数值。常见的输出形式有构造一个数组、一段字符串、一个匹配方案、一套操作顺序或者像 Ruler 这样——构造出一组交互询问用来确定隐藏的答案。构造题和其他题型最本质的区别在于它不问你答案是多少而是问存不存在某个结构请你把它造出来或者你需要通过什么样的操作来逼近这个结构。所以解构造题的第一反应不应该是套模板而是先问自己这个题想要的形式是什么能不能先画个图、列几组小数据、甚至暴力枚举几个小样例来感知规律。Ruler 这道题更特殊一点它是个交互题。交互题的本质是构造询问序列你可以向评测机发出有限次查询每个查询会返回一点信息你要利用这些信息拼出最终答案。这里要构造的东西不是最终解本身而是获取最终解的信息获取策略。这是构造题中最容易让人困惑分支因为大多数新手习惯了题目把输入喂到嘴边很难反过来想我该主动问什么。1.2 为什么竞赛选手绕不开构造题一个很现实的原因是Codeforces 从 Div. 2 到 Div. 1构造题的出场率非常高几乎每场都会有 B、C 甚至 D 位份的构造题。它们和数据结构题最大的不同是不需要背板子但需要你在十几分钟内看清结构的本质。这种题型天然具备区分度能让会思考的人和不思考的人在排名上天差地别。另一个原因和实际参赛体验有关。很多人在 CF 上卡住不是因为看不懂题而是因为习惯了输入 → 计算 → 输出的反射弧。构造题打破了这种反射弧它逼着你倒过来思考先想答案长什么样再想怎么证明它的条件性。这种反向思维在真实工程里同样有用。比如做系统设计时先想清楚系统最终长什么样再反推数据怎么流、模块怎么划分本质上就是一种构造思维。所以我一直觉得刷构造题不是单纯为比赛服务。它训练的是建模能力是从一团乱麻里抽出决定性因素的能力。这道 Ruler 题就是极好的训练样本信息量极小状态空间也不大但足够把一个可二分性用极其干净的方式呈现出来。1.3 构造题与常规算法题的边界为了后面展开不跑偏先把边界说清楚。常规算法题通常给一个输入要求输出满足条件的答案解法的核心往往是从已有条件推导出答案比如最短路、DP、网络流。构造题的核心则是从零开始设计一个满足约束的结构它没有输入作为推导的起点只有约束本身。这就像一个是做破案——根据线索找出真相另一个是做工程——根据需求做出成品。交互题落在两者之间它更像边破案边做实验你每问一个问题就在缩小答案所在的状态空间直到状态空间里只剩一个可能。Ruler 这道题里有效状态空间是 2 到 999 共 998 个整数。Hard 版把询问次数限制在一定范围内本质上就是让你设计一个高效的提问方案让每次提问都能尽可能多地带回信息量。看到这种限制大多数人脑子里会立刻浮现二分——实际上确实就是二分但难点在于怎么把测量读数和大小比较对应起来这正是构造思维的用武之地。2. 先用Ruler找题感读懂交互式的题面2.1 题面拆解一把少了一个刻度的尺子Ruler 的题面讲的是这么个故事你有一把长度为至少 1000 的尺子上面刻的是整数刻度。现在尺子上 2 到 999 之间的某一个刻度 x 被磨掉了导致当你用这把尺子去量一个物体的长度 d 时会出现这样的现象如果 d 小于 x尺子没有碰到缺损区域读数准确返回 d。如果 d 大于等于 x物体末端跨过了那个缺失的刻度尺子显示出的读数比真实长度多 1也就是返回 d 1。这里我要特别强调为什么不是返回 d - 1这就牵扯到读数的定义。假设物体末端落在 5 这个整刻度前面一点的位置尺面上所有整数刻度中只有 x 消失了所以你看到的第一个超过物体末端的刻度在缺失刻度之后都会整体向后迁移一个单位。换句话说正常尺子上 x 刻度被抹去后x 之后的所有刻度在视觉上前移了于是测量超过 x 的物体时你的眼睛会停在比真实长度大 1 的刻度上。题面这样设计核心是制造一种不对称性小于 x 的测量完全准确不小于 x 的测量稳定偏差 1。这个不对称性就是整道题唯一的逻辑锚点。它说明一次询问 d返回结果 ret 要么是 d要么是 d 1不会有第三种情况。而这两种情况恰好对应 d 与 x 的位置关系于是测量一个数就转化成了对这个数做一次与 x 的大小比较。2.2 关键转化把物理场景抽象成判断逻辑新手卡在这里很正常因为物理场景容易让人带着尺子坏了读数应该变小的生活经验走偏。真正做题的时候你要把物理画面全部丢掉只保留下面的抽象规则询问长度 m返回 ret。若 ret m说明 m x。若 ret m 1说明 m ≥ x。这两个条件可以直接成为代码里的判断分支。这也是构造题里特别重要的一种能力把具象约束抽象成一个只包含必要信息的判断函数。一旦抽象出来整个世界就变得干净了所有大于等于 x 的数字测量结果都是自身 1所有小于 x 的数字测量结果都是自身。相当于你拥有一个带噪探针它能告诉你我测的数在不在坏人 x 后面。实际写代码时这个判断函数可以封装成一次询问bool query_ge_x(int m) { cout ? m endl; int ret; cin ret; return (ret m 1); // 说明 m x }这个封装的思路值得多说一句写交互题时把一次交互 判断逻辑封装成布尔函数会让主逻辑的二分代码非常干净后续 debug 时也能单独检查这个函数有没有写反。2.3 信息量分析一次询问到底买到了什么我们换一个更信息论的视角看这个过程。x 的取值范围是 2 到 999一共 998 个等可能状态理论上下限是 ceil(log2(998)) ≈ 10 次询问因为每次询问最多获得一比特是/否信息。二分恰好就是用 log2(N) 次操作完成查找的信息获取过程每次询问把候选状态一分为二两边概率均等信息增益最大。在你的交互方案里询问一个 m 得到的反馈只有两种正好一比特而且这个比特能把当前候选区间干净地切成小于 m和大于等于 m两段。任何一个满足这个性质的探针都可以配合二分使用。所以这道题虽然顶着构造的名头真正考的其实是对二分适用条件的敏感度单调性在哪里怎么把询问次数严格控制在预算内以及为什么最终一定会落在唯一状态上。很多同学看到题目就闷头去猜规律、甚至想直接从 2 到 999 枚举那当然也能过 Easy 版但 Hard 版一限制次数就只能暴露裸奔。所以下面一节重点展开 Easy 到 Hard 的演化路径帮你把这条构造线看得更清。3. 从 Easy 到 Hard暴力到二分的进化路线3.1 Easy 版为什么线性枚举也能过Easy 版本对询问次数限制非常宽松官方题解给的方法是直接询问长度 2 到 999 的所有可能。由于 998 次询问以内一定能找出那个异常的 m所以枚举法在 Easy 版是合法且稳妥的。实际做法从 1 开始依次询问长度 i如果第一次出现 ret i 1说明 i 就是 x输出 i 然后退出。但是我建议你在做 Easy 版时不要急着交而是多用几组小数据手推一下体会第一次出现异常的位置就是 x 这个结论。比如假设 x 5你问 1、2、3、4 得到的都是原数问到 5 时返回 6那么 x 就是 5。反过来如果你问到了 6 才返回 7那说明 6 也大于等于 x而 5 一定还在候选里不符合“最早异常位置”的定义。手推几个样例后你会发现Easy 版本质上是把二分里每一轮该有的判断拆成了一轮一个地去做非常浪费但非常直观。它存在的意义是让你先理解测量的行为模式为 Hard 版铺路。3.2 Hard 版寻找区间可二分性的本质Hard 版的限制一般是询问次数不超过 20理论上 998 个状态用二分 10 轮就够了加上最终输出答案完全在预算内。但关键问题在于怎么确保每次询问对任何 x 都能稳定缩小候选区间。我们设当前候选区间为 [L, R]初始 L 2R 999。询问 mid (L R) / 2然后看 ret若 ret mid说明 mid x所以 x 至少是 mid 1候选区间更新为 [mid 1, R]。若 ret mid 1说明 mid ≥ x所以 x 至多是 mid候选区间更新为 [L, mid]。这个更新规则没有遗漏也没有重叠。因为 x 不可能同时小于 mid 又大于等于 mid所以两分支覆盖了全部可能。这里的小心机是虽然你只知道 ret 是 mid 还是 mid 1但这正好对应 x 在 mid 的哪一侧形成一比特的完美二分。你会注意到这里的更新条件非常类似标准二分查找里如果中间值小于目标则右边界收缩的逻辑只是把比较对象从数组元素换成了交互系统的返回值。本质上是把目标值 x与查询值 mid的比较编码在了返回结果里。构造题的精髓就在这种编码方式你要找到一种询问方式让它的输出天然携带你需要的比较信息。3.3 完整实现边界、初始化与询问次数预算直接放一个我打完这道题最终提交的版本代码不长但每行都有讲究#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin t; while (t--) { int l 2, r 999; while (l r) { int mid (l r) 1; cout ? mid endl; int ret; cin ret; if (ret mid) { l mid 1; } else { // ret mid 1 r mid; } } cout ! l endl; } return 0; }这里有几个需要解释的细节。第一左边界是 2因为题面保证 x 在 2 到 999不需要去问 1问了也只会返回 1没有任何信息量。第二l r 作为循环条件退出的时刻一定是 l r此时唯一候选就是答案。第三mid 取 (l r) 1因为 r 最大 999mid 在 int 范围内完全安全求和不会溢出所以用位运算只是为了快可读性上mid (l r) / 2也没区别。询问次数方面初始区间长度是 998。二分每轮一次询问到 l r 时大约需要 ceil(log2(998)) ≈ 10 次询问最后输出答案不需要询问。Hard 版的 20 次限制给你留了充足余量哪怕二分边界写得稍微保守一点也够用。这也是这道题 Easy 到 Hard 跃迁相对温和的原因——它不要求你发明什么奇特的构造只需要你识别出二分模型并准确实现。4. 构造题常见思维模型与套路归纳4.1 逆向构造从目标反推初始部署Ruler 的交互策略实际上就是一种逆向构造你不是直接计算 x 是多少而是设计一个探针让它的返回结果能替你缩小范围。很多构造题都遵循这个模式。比如构造一个长度为 n 的排列使得相邻两个数的差的绝对值都不相同这种题正着拼怎么都别扭但你从目标条件反推会发现让后半段折返放置差的绝对值自然序列化。这种从最终状态回推每一步应该做什么的思维是构造题里最常用的一个模型。实操时我习惯先在小黑板上画出目标状态再倒着标出为了得到这个状态上一步必须是什么。如果每一步都能唯一确定那构造就完成了如果步与步之间有冲突就说明你选的路径不对可以尝试换一种回推顺序。逆向构造的难点不是每一步怎么推而是当某个分支出现矛盾时你敢不敢果断回退重新规划而不是在原地打转。4.2 二分、倍增与分治探路灯模型Ruler 这类交互式构造题最经典的思维模型就是把每次询问当作一盏探路灯这盏灯只能照亮你当前位置附近的情况但可以根据反馈调整位置最终逼近答案。二分是最简单的探路灯控制策略倍增则适用于答案边界范围未知的场景比如先 a[1] 看是否越过边界越过就按指数退回去再细调。在更复杂的构造题里你会看到这种探路灯被包装成各种样子有时候是询问一个子集有时候是执行一个操作序列但它们共同的原则是确保每次反馈能稳定地对消一部分候选状态。一旦你发现某次询问的反馈不能排除任何状态说明询问设计有问题或者这道题根本不能用这种探针正确解决需要换一个反馈维度。Ruler 里的反馈维度是偏了 0 还是偏了 1这个维度恰好和 x 的位置一一对应所以二分成了天作之合。4.3 把一定成立写清楚构造题的证明习惯很多同学能猜出构造方案但一写证明就慌。我自己的习惯是在构造时同步思考为什么这个构造合法不一定要写严谨的数学证明但必须有一个无懈可击的口头推理。比如 Ruler 这题合法性就两条第一循环不变式是x 一定在 [l, r] 中第二每轮循环要么 l 增大到 mid 1要么 r 缩小到 mid区间长度严格减小所以最终必然终止且 l r。这两条一旦确认整个算法就不可能错。这种构造后立刻证明的习惯不是比赛里浪费时间恰恰是帮你躲坑的最好工具。因为很多构造方案在样例上看起来没问题但状态一变大就崩原因就是你漏掉了某个边界条件或者某个状态转移。把合法性先想透再写代码心态会稳很多debug 成本也会骤降。5. 交互题的实战排错与经验清单5.1 交互类题目最容易踩的三个坑第一个坑是缓冲问题。交互题要求你每次输出询问后立刻刷新输出缓冲区否则评测程序可能等不到你的输出。这个在旧标准里要用fflush(stdout)或者cout flushC 里我一般直接cout endl因为它自带刷新缓冲区的功能最省心。注意如果用了\n就必须手动 flush漏一次就可能超时或者 idleness limit exceeded。第二个坑是边界写错。二分区间初始化以及 mid 的更新方向非常容易和普通数组二分搞混。比如有人习惯l mid 1、r mid - 1但在这道题里如果查询 mid 时返回 ret mid 1说明 mid ≥ xx 有可能正好等于 mid所以右边界只能是 r mid 而不能是 r mid - 1。写错这一行整个二分就会漏掉正确解。建议把两分支的边界条件先写在纸上再抄进代码。第三个坑是死循环。当 l 和 r 相差 1 时如果 mid 取 (l r) / 2 得到 l而某个分支更新成 l mid就会陷入无限循环。Ruler 这题因为取 l mid 1 和 r mid 的分配方式天然避开了这个经典死循环但你在其他交互题里未必有这样的运气。通用的防御手段是要么 mid 取 (l r 1) / 2 配合配套的更新规则要么在循环里打印调试日志把 mid、ret、l、r 都打出来看一眼是否正确收敛。5.2 本地调试与对拍技巧交互题难以直接在本地测试因为标准输入输出都被评测程序占据。我的做法是写一个模拟评测脚本用脚本模拟那个隐藏的 x 并返回读数。比如 Ruler 题的模拟器可以这样设计import sys def main(): hidden 42 # 测试用的隐藏刻度 data sys.stdin.read().split() idx 0 t int(data[idx]); idx 1 for _ in range(t): while True: op data[idx]; idx 1 if op ?: m int(data[idx]); idx 1 if m hidden: print(m) else: print(m 1) sys.stdout.flush() else: guess int(data[idx]); idx 1 if guess hidden: print(OK) else: print(fWA expected {hidden}) break main()然后本地用python3 simulator.py input.txt跑你编译好的程序。这种模拟器写起来很快但能帮你验证二分逻辑在大量随机 hidden 值下的正确性。每次改完代码跑个随机数据批量对拍比肉眼盯代码强一百倍。很多交互题的边界问题只有在这种模拟环境下才会暴露。顺便提一句如果你经常做 CF 积分赛或周赛建议在本地留一份通用的交互模拟器模板遇到交互题直接套能省下大量手搓本地环境的时间。5.3 构造题刷题路线建议最后聊点更长线的经验。如果你想系统地提升构造题能力光刷 Div. 4 的题目不够建议按难度梯度推进先做 CF 上标签含 constructive algorithms 的 800 到 1300 分题目这类题主要培养对规律和结构的敏感度再做 1400 到 1700 分段的构造题这个区间经常混合贪心、数学归纳、逆向思维等元素是提升最明显的阶段上了 1800 分以后构造题往往和交互、图论、组合数学杂交那时候再针对性补专项。刷的时候有个习惯我非常推荐每道构造题不管 AC 没有都要写下我是怎么想到这个构造的和还有哪个方向没想到。比如 Ruler 这题你可以在日记里写下我最初没想到把测量行为抽象成布尔比较我想到二分花了 5 分钟边界更新 r mid 差点写错。这种想法日志回头看特别有价值因为它记录了你的思维盲区在哪比重复做题更能提高效率。写在最后Ruler 这道题真正教会我的东西不是二分本身而是如何把一个看似物理的问题翻译成一个纯粹的判断器并让这个判断器和二分模型严丝合缝地对接。在 CF 构造题里这种翻译能力比任何一种具体算法都稀缺。你需要的不是背更多套路而是练就一双能在复杂场景里找到关键反馈维度的眼睛。希望通过这篇关于 Codeforces 构造题和 Ruler 的详细拆解你下次再遇到交互式构造题能从容地先问自己一句这个题目里哪一次询问能让我稳定地排除掉一半可能找到它题就赢了一半。
Codeforces Ruler 题解：交互式构造题与二分边界全解析
每年 Codeforces 的 Div. 4 场次里G 题往往不会用到高深的数据结构但它特别能筛选思维习惯。Round 964 的 G1/G2 Ruler 就是这样一道题表面上是个交互式构造题本质上考的是你建模时能不能把乱七八糟的规则压缩成一个可以二分的判断。作为一名刷过几百道交互题的选手我很负责任地说这道题值得慢下来拆一遍尤其是 Hard 版本它把二分这件事玩得特别纯粹。这篇文章我会从题目背后的构造思维讲起把 Easy 到 Hard 的进化路线、二分边界的推导、交互题常见的坑、以及构造题通用的几种思维模型全部串在一起说最后附上我自己调试这类题时常用的排错清单。整个话题围绕 Codeforces 构造题展开你可以把它当成一篇交互式二分题型的专项复盘来读。1. 构造题到底在考什么1.1 一句话说清构造题Codeforces 的构造题英文叫 Constructive Algorithm题目会给你一个目标状态和若干限制条件要求你构造出一个满足这些条件的方案而不是像普通算法题那样只输出一个最优数值。常见的输出形式有构造一个数组、一段字符串、一个匹配方案、一套操作顺序或者像 Ruler 这样——构造出一组交互询问用来确定隐藏的答案。构造题和其他题型最本质的区别在于它不问你答案是多少而是问存不存在某个结构请你把它造出来或者你需要通过什么样的操作来逼近这个结构。所以解构造题的第一反应不应该是套模板而是先问自己这个题想要的形式是什么能不能先画个图、列几组小数据、甚至暴力枚举几个小样例来感知规律。Ruler 这道题更特殊一点它是个交互题。交互题的本质是构造询问序列你可以向评测机发出有限次查询每个查询会返回一点信息你要利用这些信息拼出最终答案。这里要构造的东西不是最终解本身而是获取最终解的信息获取策略。这是构造题中最容易让人困惑分支因为大多数新手习惯了题目把输入喂到嘴边很难反过来想我该主动问什么。1.2 为什么竞赛选手绕不开构造题一个很现实的原因是Codeforces 从 Div. 2 到 Div. 1构造题的出场率非常高几乎每场都会有 B、C 甚至 D 位份的构造题。它们和数据结构题最大的不同是不需要背板子但需要你在十几分钟内看清结构的本质。这种题型天然具备区分度能让会思考的人和不思考的人在排名上天差地别。另一个原因和实际参赛体验有关。很多人在 CF 上卡住不是因为看不懂题而是因为习惯了输入 → 计算 → 输出的反射弧。构造题打破了这种反射弧它逼着你倒过来思考先想答案长什么样再想怎么证明它的条件性。这种反向思维在真实工程里同样有用。比如做系统设计时先想清楚系统最终长什么样再反推数据怎么流、模块怎么划分本质上就是一种构造思维。所以我一直觉得刷构造题不是单纯为比赛服务。它训练的是建模能力是从一团乱麻里抽出决定性因素的能力。这道 Ruler 题就是极好的训练样本信息量极小状态空间也不大但足够把一个可二分性用极其干净的方式呈现出来。1.3 构造题与常规算法题的边界为了后面展开不跑偏先把边界说清楚。常规算法题通常给一个输入要求输出满足条件的答案解法的核心往往是从已有条件推导出答案比如最短路、DP、网络流。构造题的核心则是从零开始设计一个满足约束的结构它没有输入作为推导的起点只有约束本身。这就像一个是做破案——根据线索找出真相另一个是做工程——根据需求做出成品。交互题落在两者之间它更像边破案边做实验你每问一个问题就在缩小答案所在的状态空间直到状态空间里只剩一个可能。Ruler 这道题里有效状态空间是 2 到 999 共 998 个整数。Hard 版把询问次数限制在一定范围内本质上就是让你设计一个高效的提问方案让每次提问都能尽可能多地带回信息量。看到这种限制大多数人脑子里会立刻浮现二分——实际上确实就是二分但难点在于怎么把测量读数和大小比较对应起来这正是构造思维的用武之地。2. 先用Ruler找题感读懂交互式的题面2.1 题面拆解一把少了一个刻度的尺子Ruler 的题面讲的是这么个故事你有一把长度为至少 1000 的尺子上面刻的是整数刻度。现在尺子上 2 到 999 之间的某一个刻度 x 被磨掉了导致当你用这把尺子去量一个物体的长度 d 时会出现这样的现象如果 d 小于 x尺子没有碰到缺损区域读数准确返回 d。如果 d 大于等于 x物体末端跨过了那个缺失的刻度尺子显示出的读数比真实长度多 1也就是返回 d 1。这里我要特别强调为什么不是返回 d - 1这就牵扯到读数的定义。假设物体末端落在 5 这个整刻度前面一点的位置尺面上所有整数刻度中只有 x 消失了所以你看到的第一个超过物体末端的刻度在缺失刻度之后都会整体向后迁移一个单位。换句话说正常尺子上 x 刻度被抹去后x 之后的所有刻度在视觉上前移了于是测量超过 x 的物体时你的眼睛会停在比真实长度大 1 的刻度上。题面这样设计核心是制造一种不对称性小于 x 的测量完全准确不小于 x 的测量稳定偏差 1。这个不对称性就是整道题唯一的逻辑锚点。它说明一次询问 d返回结果 ret 要么是 d要么是 d 1不会有第三种情况。而这两种情况恰好对应 d 与 x 的位置关系于是测量一个数就转化成了对这个数做一次与 x 的大小比较。2.2 关键转化把物理场景抽象成判断逻辑新手卡在这里很正常因为物理场景容易让人带着尺子坏了读数应该变小的生活经验走偏。真正做题的时候你要把物理画面全部丢掉只保留下面的抽象规则询问长度 m返回 ret。若 ret m说明 m x。若 ret m 1说明 m ≥ x。这两个条件可以直接成为代码里的判断分支。这也是构造题里特别重要的一种能力把具象约束抽象成一个只包含必要信息的判断函数。一旦抽象出来整个世界就变得干净了所有大于等于 x 的数字测量结果都是自身 1所有小于 x 的数字测量结果都是自身。相当于你拥有一个带噪探针它能告诉你我测的数在不在坏人 x 后面。实际写代码时这个判断函数可以封装成一次询问bool query_ge_x(int m) { cout ? m endl; int ret; cin ret; return (ret m 1); // 说明 m x }这个封装的思路值得多说一句写交互题时把一次交互 判断逻辑封装成布尔函数会让主逻辑的二分代码非常干净后续 debug 时也能单独检查这个函数有没有写反。2.3 信息量分析一次询问到底买到了什么我们换一个更信息论的视角看这个过程。x 的取值范围是 2 到 999一共 998 个等可能状态理论上下限是 ceil(log2(998)) ≈ 10 次询问因为每次询问最多获得一比特是/否信息。二分恰好就是用 log2(N) 次操作完成查找的信息获取过程每次询问把候选状态一分为二两边概率均等信息增益最大。在你的交互方案里询问一个 m 得到的反馈只有两种正好一比特而且这个比特能把当前候选区间干净地切成小于 m和大于等于 m两段。任何一个满足这个性质的探针都可以配合二分使用。所以这道题虽然顶着构造的名头真正考的其实是对二分适用条件的敏感度单调性在哪里怎么把询问次数严格控制在预算内以及为什么最终一定会落在唯一状态上。很多同学看到题目就闷头去猜规律、甚至想直接从 2 到 999 枚举那当然也能过 Easy 版但 Hard 版一限制次数就只能暴露裸奔。所以下面一节重点展开 Easy 到 Hard 的演化路径帮你把这条构造线看得更清。3. 从 Easy 到 Hard暴力到二分的进化路线3.1 Easy 版为什么线性枚举也能过Easy 版本对询问次数限制非常宽松官方题解给的方法是直接询问长度 2 到 999 的所有可能。由于 998 次询问以内一定能找出那个异常的 m所以枚举法在 Easy 版是合法且稳妥的。实际做法从 1 开始依次询问长度 i如果第一次出现 ret i 1说明 i 就是 x输出 i 然后退出。但是我建议你在做 Easy 版时不要急着交而是多用几组小数据手推一下体会第一次出现异常的位置就是 x 这个结论。比如假设 x 5你问 1、2、3、4 得到的都是原数问到 5 时返回 6那么 x 就是 5。反过来如果你问到了 6 才返回 7那说明 6 也大于等于 x而 5 一定还在候选里不符合“最早异常位置”的定义。手推几个样例后你会发现Easy 版本质上是把二分里每一轮该有的判断拆成了一轮一个地去做非常浪费但非常直观。它存在的意义是让你先理解测量的行为模式为 Hard 版铺路。3.2 Hard 版寻找区间可二分性的本质Hard 版的限制一般是询问次数不超过 20理论上 998 个状态用二分 10 轮就够了加上最终输出答案完全在预算内。但关键问题在于怎么确保每次询问对任何 x 都能稳定缩小候选区间。我们设当前候选区间为 [L, R]初始 L 2R 999。询问 mid (L R) / 2然后看 ret若 ret mid说明 mid x所以 x 至少是 mid 1候选区间更新为 [mid 1, R]。若 ret mid 1说明 mid ≥ x所以 x 至多是 mid候选区间更新为 [L, mid]。这个更新规则没有遗漏也没有重叠。因为 x 不可能同时小于 mid 又大于等于 mid所以两分支覆盖了全部可能。这里的小心机是虽然你只知道 ret 是 mid 还是 mid 1但这正好对应 x 在 mid 的哪一侧形成一比特的完美二分。你会注意到这里的更新条件非常类似标准二分查找里如果中间值小于目标则右边界收缩的逻辑只是把比较对象从数组元素换成了交互系统的返回值。本质上是把目标值 x与查询值 mid的比较编码在了返回结果里。构造题的精髓就在这种编码方式你要找到一种询问方式让它的输出天然携带你需要的比较信息。3.3 完整实现边界、初始化与询问次数预算直接放一个我打完这道题最终提交的版本代码不长但每行都有讲究#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin t; while (t--) { int l 2, r 999; while (l r) { int mid (l r) 1; cout ? mid endl; int ret; cin ret; if (ret mid) { l mid 1; } else { // ret mid 1 r mid; } } cout ! l endl; } return 0; }这里有几个需要解释的细节。第一左边界是 2因为题面保证 x 在 2 到 999不需要去问 1问了也只会返回 1没有任何信息量。第二l r 作为循环条件退出的时刻一定是 l r此时唯一候选就是答案。第三mid 取 (l r) 1因为 r 最大 999mid 在 int 范围内完全安全求和不会溢出所以用位运算只是为了快可读性上mid (l r) / 2也没区别。询问次数方面初始区间长度是 998。二分每轮一次询问到 l r 时大约需要 ceil(log2(998)) ≈ 10 次询问最后输出答案不需要询问。Hard 版的 20 次限制给你留了充足余量哪怕二分边界写得稍微保守一点也够用。这也是这道题 Easy 到 Hard 跃迁相对温和的原因——它不要求你发明什么奇特的构造只需要你识别出二分模型并准确实现。4. 构造题常见思维模型与套路归纳4.1 逆向构造从目标反推初始部署Ruler 的交互策略实际上就是一种逆向构造你不是直接计算 x 是多少而是设计一个探针让它的返回结果能替你缩小范围。很多构造题都遵循这个模式。比如构造一个长度为 n 的排列使得相邻两个数的差的绝对值都不相同这种题正着拼怎么都别扭但你从目标条件反推会发现让后半段折返放置差的绝对值自然序列化。这种从最终状态回推每一步应该做什么的思维是构造题里最常用的一个模型。实操时我习惯先在小黑板上画出目标状态再倒着标出为了得到这个状态上一步必须是什么。如果每一步都能唯一确定那构造就完成了如果步与步之间有冲突就说明你选的路径不对可以尝试换一种回推顺序。逆向构造的难点不是每一步怎么推而是当某个分支出现矛盾时你敢不敢果断回退重新规划而不是在原地打转。4.2 二分、倍增与分治探路灯模型Ruler 这类交互式构造题最经典的思维模型就是把每次询问当作一盏探路灯这盏灯只能照亮你当前位置附近的情况但可以根据反馈调整位置最终逼近答案。二分是最简单的探路灯控制策略倍增则适用于答案边界范围未知的场景比如先 a[1] 看是否越过边界越过就按指数退回去再细调。在更复杂的构造题里你会看到这种探路灯被包装成各种样子有时候是询问一个子集有时候是执行一个操作序列但它们共同的原则是确保每次反馈能稳定地对消一部分候选状态。一旦你发现某次询问的反馈不能排除任何状态说明询问设计有问题或者这道题根本不能用这种探针正确解决需要换一个反馈维度。Ruler 里的反馈维度是偏了 0 还是偏了 1这个维度恰好和 x 的位置一一对应所以二分成了天作之合。4.3 把一定成立写清楚构造题的证明习惯很多同学能猜出构造方案但一写证明就慌。我自己的习惯是在构造时同步思考为什么这个构造合法不一定要写严谨的数学证明但必须有一个无懈可击的口头推理。比如 Ruler 这题合法性就两条第一循环不变式是x 一定在 [l, r] 中第二每轮循环要么 l 增大到 mid 1要么 r 缩小到 mid区间长度严格减小所以最终必然终止且 l r。这两条一旦确认整个算法就不可能错。这种构造后立刻证明的习惯不是比赛里浪费时间恰恰是帮你躲坑的最好工具。因为很多构造方案在样例上看起来没问题但状态一变大就崩原因就是你漏掉了某个边界条件或者某个状态转移。把合法性先想透再写代码心态会稳很多debug 成本也会骤降。5. 交互题的实战排错与经验清单5.1 交互类题目最容易踩的三个坑第一个坑是缓冲问题。交互题要求你每次输出询问后立刻刷新输出缓冲区否则评测程序可能等不到你的输出。这个在旧标准里要用fflush(stdout)或者cout flushC 里我一般直接cout endl因为它自带刷新缓冲区的功能最省心。注意如果用了\n就必须手动 flush漏一次就可能超时或者 idleness limit exceeded。第二个坑是边界写错。二分区间初始化以及 mid 的更新方向非常容易和普通数组二分搞混。比如有人习惯l mid 1、r mid - 1但在这道题里如果查询 mid 时返回 ret mid 1说明 mid ≥ xx 有可能正好等于 mid所以右边界只能是 r mid 而不能是 r mid - 1。写错这一行整个二分就会漏掉正确解。建议把两分支的边界条件先写在纸上再抄进代码。第三个坑是死循环。当 l 和 r 相差 1 时如果 mid 取 (l r) / 2 得到 l而某个分支更新成 l mid就会陷入无限循环。Ruler 这题因为取 l mid 1 和 r mid 的分配方式天然避开了这个经典死循环但你在其他交互题里未必有这样的运气。通用的防御手段是要么 mid 取 (l r 1) / 2 配合配套的更新规则要么在循环里打印调试日志把 mid、ret、l、r 都打出来看一眼是否正确收敛。5.2 本地调试与对拍技巧交互题难以直接在本地测试因为标准输入输出都被评测程序占据。我的做法是写一个模拟评测脚本用脚本模拟那个隐藏的 x 并返回读数。比如 Ruler 题的模拟器可以这样设计import sys def main(): hidden 42 # 测试用的隐藏刻度 data sys.stdin.read().split() idx 0 t int(data[idx]); idx 1 for _ in range(t): while True: op data[idx]; idx 1 if op ?: m int(data[idx]); idx 1 if m hidden: print(m) else: print(m 1) sys.stdout.flush() else: guess int(data[idx]); idx 1 if guess hidden: print(OK) else: print(fWA expected {hidden}) break main()然后本地用python3 simulator.py input.txt跑你编译好的程序。这种模拟器写起来很快但能帮你验证二分逻辑在大量随机 hidden 值下的正确性。每次改完代码跑个随机数据批量对拍比肉眼盯代码强一百倍。很多交互题的边界问题只有在这种模拟环境下才会暴露。顺便提一句如果你经常做 CF 积分赛或周赛建议在本地留一份通用的交互模拟器模板遇到交互题直接套能省下大量手搓本地环境的时间。5.3 构造题刷题路线建议最后聊点更长线的经验。如果你想系统地提升构造题能力光刷 Div. 4 的题目不够建议按难度梯度推进先做 CF 上标签含 constructive algorithms 的 800 到 1300 分题目这类题主要培养对规律和结构的敏感度再做 1400 到 1700 分段的构造题这个区间经常混合贪心、数学归纳、逆向思维等元素是提升最明显的阶段上了 1800 分以后构造题往往和交互、图论、组合数学杂交那时候再针对性补专项。刷的时候有个习惯我非常推荐每道构造题不管 AC 没有都要写下我是怎么想到这个构造的和还有哪个方向没想到。比如 Ruler 这题你可以在日记里写下我最初没想到把测量行为抽象成布尔比较我想到二分花了 5 分钟边界更新 r mid 差点写错。这种想法日志回头看特别有价值因为它记录了你的思维盲区在哪比重复做题更能提高效率。写在最后Ruler 这道题真正教会我的东西不是二分本身而是如何把一个看似物理的问题翻译成一个纯粹的判断器并让这个判断器和二分模型严丝合缝地对接。在 CF 构造题里这种翻译能力比任何一种具体算法都稀缺。你需要的不是背更多套路而是练就一双能在复杂场景里找到关键反馈维度的眼睛。希望通过这篇关于 Codeforces 构造题和 Ruler 的详细拆解你下次再遇到交互式构造题能从容地先问自己一句这个题目里哪一次询问能让我稳定地排除掉一半可能找到它题就赢了一半。 
