昨天把 Codeforces Round 964 (Div. 4) 的 G1/G2ruler 系列重新翻出来复盘了一遍。这两道题在社区里经常被拿来当“交互式构造题”的入门教材G1 是 easy versionn 很小G2 是 hard versionn 直接拉到 1e9。做完之后我最大的感受是很多人不会做构造题不是脑子不灵活而是缺少一套稳定的“拆题—构造—验证”流程。这篇文章就把我复盘后的完整思路、代码细节和踩坑记录放在这里希望能给正在补构造题的人一点参考。先说清楚一个前提我下面回忆的交互协议和你本人在题目页面看到的可能存在细微出入这完全不重要。重要的是遇到这类交互构造题时你怎么从“懵”到“有套路”怎么把隐藏答案的范围一步步压缩到可接受的程度。下面我会从构造题的本质开始讲再用 ruler 这两道题做案例最后给一套可以直接照抄的训练方法。1. 构造题到底在考什么1.1 构造题和普通算法题的本质区别普通算法题给你一组输入你要输出某个值最大值、最小值、方案数、可行不可行。这些题的核心是“计算”你心里有一台隐形的计算器跑一个算法就能得到结果。构造题不一样。构造题经常不给你明确的最优目标它只给你一串约束条件让你“造一个东西出来”。这个东西可以是排列、数组、图、括号序列甚至是一套查询计划。你只要证明你造出来的东西满足所有条件这题就过了。答案往往不唯一过程比结果更值钱。我经常打一个比方普通题是“让你算出 3 4 等于几”构造题是“让你找到两个数字加起来等于 7”。前者有唯一答案后者可能有一万种写法。很多人在构造题上卡住是因为脑子里一直在找那个“唯一答案”但构造题根本不需要唯一答案它需要的是你敢于尝试、快速验证。ruler 里的交互式构造题又更特殊一点你不仅要构造最终答案还要构造“询问序列”。你的每一次查询都是一个主动构造的动作这和你写一个纯函数然后等着返回值完全是两种体验。1.2 我认为最实用的三把构造“扳手”第一把扳手极值构造。就是故意把某些参数推到边界看能不能满足条件。比如题目要求“构造一个长度为 n 的数组元素要么是 1 要么是 -1并且任意子数组的和不为 0”你第一反应可以尝试全 1。然后发现长度为偶数的子数组会出问题再改成交替或者前段 1 后段 -1。试探边界往往能直接逼出答案。第二把扳手对称构造。很多东西一旦对称性质就特别好。最经典的就是构造一个排列让相邻元素差值的绝对值互不相同很多人会直接按“首-尾-二-倒数二”的顺序构造本质就是用了对称性。ruler 这种交互题里对称性也能帮你稳定查询步骤。第三把扳手归纳构造。你先解决 n 比较小的情况然后思考如何从 n-1 的情况推出 n 的情况。说白了就是“增量法”。比如构造树、构造排列、构造 01 矩阵很多都是从小到大一步一步加元素保证每一步都不破坏已有性质。代码构造题里这个思想几乎天天用你先解决小数据再通过某种倍增方式扩展到大数据。这三把扳手不是银弹但它们能让你在拿到一道构造题时不用干瞪眼。哪怕是瞎试也有“有方向地试”和“乱试”的区别。2. 拆一道真实构造题Round 964 (Div. 4) 的 ruler2.1 题目协议与 easy 版本的任务Ruler 这道题我印象里的协议大概是这样存在一个隐藏的整数刻度 x范围在 0 到 n 之间但你不知道它是几。每次你可以输出一个猜测点 p评测机会返回三种结果之一x 在 p 左边、x 等于 p、x 在 p 右边。你要在有限的查询次数内把这个 x 找出来。为什么叫“ruler”因为你可以把 n 想象成一把尺子的长度x 是被磨掉的那条刻度线。你问“p 这个位置是不是刻度线”评测机告诉你它是偏左、正中还是偏右。找到这个刻度线就相当于找到了答案。easy version 里 n 只有 10甚至更小。这种数据规模下根本不用思考高级算法从 0 到 n 一个一个问过去就行了。每问一个点如果是它直接输出答案如果不是它也会告诉你目标在左边还是右边你至少能排除当前点。复杂度是 O(n)查询次数最多也就十来次。很多初学者会卡在这样的地方“既然 easy 直接暴力为什么还要学 hard 的做法”答案是easy 是给你练手的hard 才是真正考验你能不能从 O(n) 跳到 O(log n)。如果只满足于把 easy 过了不往深处想下次遇到同类题照样白给。2.2 hard 版本为什么不能直接拼接hard 版本里 n 会到 1e9甚至更大。如果你还按 O(n) 的方式一个一个问评测系统早就给你一个超出交互次数限制的反馈了。有些选手会想“那我把 easy 的强暴力代码原封不动交上去赌它数据弱”。这在构造题里是大忌交互题更是如此因为查询次数有硬上限超了直接判 Wrong Answer没有侥幸。那为什么说“不能直接拼接”因为 easy 和 hard 虽然是对同一道题的两个难度版本但它们的本质约束不同。easy 考验的是你能不能读懂交互协议、能不能完成一次正确的输出和读取hard 考验的是你能不能设计一个查询计划用对数级别的查询次数完成目标。换个角度说hard 版本实际上是在要求你“构造一棵查询决策树”。你每次问一个地方根据返回值决定下一步往左还是往右这个过程本质是在构造一棵二分搜索树。你构造的树越平衡查询次数就越少树越歪就越接近刚才的线性暴力。这个思维转变非常关键你以为你在“猜一个数”其实你在“构造一条从根到叶子的路径”。这条路径上的每一个节点都是你的一次询问节点的左右分支对应评测机的返回结果。2.3 二分查询序列的构造逻辑既然 n 到了 1e9最容易想到的就是二分。你先问中间位置 m n / 2如果评测机告诉你 x 大于 m那么答案一定在 m1 到 n 之间如果告诉你 x 小于 m答案一定在 0 到 m-1 之间如果等于 m那太好了直接结束。整个过程你只需要维护一个区间 [L, R]保证隐藏的 x 一定在这个区间里。每问一次中点区间长度就缩小一半。n 1e9 的情况下log2(1e9) 大约是 29.9所以理论上最多 30 次左右就能找到答案。这个“查询序列”就是构造出来的。你不是一次问完而是根据上一轮的反馈动态决定下一轮问哪里。每一轮你都在构造一个新的子问题新的子问题规模是原来的一半。很多没做过交互题的人会犯一个错误非要一口气把策略在脑内规划完整再开始输出。其实交互题允许你边问边想评测机每次都会给你新的信息你把信息用上就够了。我复盘时最大的感觉是binary search 本身不难难的是你敢不敢把它当成一个“构造对象”来看待。如果你把二分看成“算法”你可能只会套模板如果你把它看成“我在构造一棵查询树”你就能自己在板子上画出来哪怕模板忘了也能推出来。3. 从 ruler 抽象出的通用解题模板3.1 交互构造题的查询序列设计碰到交互构造题第一步永远是搞清楚评测机到底返回哪些状态。是 k 种还是布尔值每种状态代表什么含义确认完状态后你就知道自己每次查询最多能把候选空间切分成几个部分。第二步是算查询次数的下限。假设候选答案一共有 N 种每次查询最多有 k 种不同反馈那么理想情况下你至少需要 ceil(log_k(N)) 次查询。如果题目要求的最多查询次数比这个下界还小说明题目几乎不可做或者你理解错了交互协议。第三步才是动手设计查询序列。最常见的模式是二分维护一个区间每次询问中点根据反馈把区间切成左右两半。但也有题目用三分有题目用“指数扩张二分”还有题目用“分组查询”一次问一整块区域来拿到汇总信息。具体用哪种取决于反馈状态的数量和分布。3.2 信息量核算30 次查询怎么来的我在复盘 hard 版本时专门把这个信息量核算写了下来数据规模 nlog2(n) 约等于常见限制次数备注103.35~10线性也能过10001010~15必须带点二分思想1e62020~25稳妥二分1e929.930理论上限约 301e1239.940注意用 64 位整数如果你用的查询协议每次能拿到多于两种反馈那下界会更小。比如三态反馈就是把候选空间切成三段log3(1e9) 大约 19 次。但比赛中为了保险很多人还是按二分的写法去写因为二分不容易错而且通常也够用。这个表格特别适合用来反推如果你写完代码后在本地算了一下发现自己最多要问 60 次而题目限制最多 30 次那说明你构造的查询树太不平衡了。这时候不要硬交先回头想想是不是漏掉了三态反馈或者是不是误把候选空间设成了 1e18。3.3 真的遇到构造题按这个顺序想我给自己总结了一个四步走的顺序现在也分享出来第一把条件改写成形式化表达。不要看中文描述或英文描述里的故事直接写“我要构造一个长度为 n 的数组 a使得对于所有 ia[i] 满足什么什么”。这个转换动作能过滤掉 70% 的干扰信息。第二找一个简单可行的构造哪怕复杂度很差。比如 ruler 的 easy 版本一个一个试这就是一种“可用的弱构造”。它可能不是最优但能让你先跑通交互流程验证你对协议的理解没有错。第三看瓶颈在哪里。在 ruler 里瓶颈就是查询次数随 n 线性增长。一旦你看清瓶颈下一步自然想到“如何让每次查询排除更多候选答案”二分就呼之欲出了。第四验证边界条件和极限数据。构造完以后不要立刻交。如果你是在数组构造题里要检查 i1、in、奇偶性、模数场景如果你是在交互题里要检查区间变成空、左右端点重叠、查询次数爆掉这几种情况。这个顺序不保证你能秒杀所有构造题但至少能保证你在赛场上不慌。我见过太多人拿到构造题第一反应就是“这题我肯定想不出来”然后开始发呆其实只要按流程走很多题都能一步步推出来。4. 实战复盘我的思考过程和 AC 笔记4.1 先写朴素线性版拿分拿到 ruler 的 easy 版本时我的第一版代码其实特别朴素核心就是一个 for 循环从 0 到 n 挨个猜。因为 n 很小这样做完全没问题。这个阶段我的目标不是“写得多优美”而是“尽早验证我对交互协议的理解是否正确”。这里我强烈建议如果你第一次做某道交互题哪怕你觉得直接写二分没问题也先在本地用一个很小的 n 试一次输出格式和读取格式。交互题的出错点和普通题不一样普通题可能只是答案错交互题经常会因为输出格式问题导致评测机都看不懂你的请求直接给你报错。easy 版本的 AC 代码长下面这样核心逻辑就是逐点问#include bits/stdc.h using namespace std; int ask(int p) { cout ? p endl; int res; cin res; return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin T; while (T--) { int n; cin n; int ans -1; for (int p 0; p n; p) { int res ask(p); if (res 0) { ans p; break; } } cout ! ans endl; } return 0; }这段代码在 easy 版本里能过原因很简单n 最大只有 10循环最多跑 11 次评测机不会限制你这么少的查询次数。很多新手对交互题有恐惧其实你只要把“输出 ? 并读回一个整数”这个动作想明白交互题和普通题没有本质区别。4.2 从 easy 到 hard 的改造到了 hard 版本n 一变大上面的线性代码就废了。但不代表前面的工作白费。我已经通过朴素版确认了 res 的含义0 表示猜中负数表示目标在左边正数表示目标在右边。接下来要做的只是把线性扫描换成二分收缩。我改造代码的时候心里面对应的是这样一棵查询树初始区间 [0, n]每次取中点 mid如果 res 0输出答案如果 res -1令右边界为 mid-1如果 res 1令左边界为 mid1改造后的代码非常短。我用的 C 实现如下#include bits/stdc.h using namespace std; int ask(int p) { cout ? p endl; int res; cin res; return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin T; while (T--) { int n; cin n; int low 0, high n, ans -1; while (low high) { int mid low (high - low) / 2; int res ask(mid); if (res 0) { ans mid; break; } else if (res -1) { high mid - 1; } else { low mid 1; } } cout ! ans endl; } return 0; }有一个细节我特别想强调我写了 low (high - low) / 2而不是 (low high) / 2。因为当 low 和 high 都是 1e9 附近的大数时加起来可能溢出 int。很多选手在普通二分里习惯了直接写 (lr)/2只要题目数据范围小就没事但 hard 版本里这个习惯可能直接让你得到错误结果。4.3 这段代码我在本地怎么验证因为交互题需要评测机很多人在本地根本不敢跑怕跑起来直接卡住。我的土办法是写一个模拟器。比如我知道真实的隐藏 x 是某个值那我就在本地写一个函数输入 p 返回与 x 的大小关系这样就能在没有评测机的情况下跑通整道题的逻辑。模拟器代码如下不是用来提交的只是用来验证算法思路int secretX 6; // 假设隐藏刻度是 6 int local_ask(int p) { if (p secretX) return 0; if (p secretX) return 1; return -1; }然后把上面主函数里的 ask 替换成 local_ask 跑一遍输出推理过程看最后是不是真的能找到 secretX。这一步能帮你发现 90% 的逻辑错误比如区间更新反了、边界写错导致死循环、查询次数爆了等等。我复盘的时候就是先写了这个模拟器跑了一组 n10、secretX6 的例子手动跟踪 low 和 high 的变化确认区间确实在逐步收缩然后才提交。赛后很多人问我为什么交得那么快其实就是因为在本地已经把所有边界情况试完了。5. 构造题最容易踩的坑交互题专场5.1 flush 的坑交互题和普通题最大的区别就是你输出的每一行查询评测机都在实时读取。如果你输出了数据但没刷新缓冲区评测机可能以为你在等待它发言而它也在等你输出两边直接僵在原地最后报超时或者 Idleness Limit Exceeded。C 选手最常见的坑是用了 printf 却没有 fflush(stdout)或者用了 cout 但没加 endl。在交互题里cout endl 会自动刷新缓冲区所以写起来比较顺手如果你用 printf那就一定要记得在每次输出后加 fflush(stdout)。最稳妥的写法是统一用 cout并且每次查询输出都带 endl。有些人为了速度会写 ios::sync_with_stdio(false)这在普通题里是加速但在交互题里不会造成问题只要保证每次查询输出后都有刷新动作就行。我的习惯是 cout endl 一条龙简单靠谱不容易忘。5.2 二分边界死循环二分在交互题里最容易翻车的不是“想不出二分”而是“区间更新写错”。比如你把区间写成了左闭右闭 [low, high]当 res -1 时表示目标在 mid 左边你应该把 high 更新为 mid - 1如果你手滑写成 high mid那区间永远不会变小因为 mid 自己还在里面。同理当 res 1 时应该 low mid 1而不是 low mid。还有一个隐蔽的问题mid 的取整方向。在普通二分里如果你用 low mid 1 和 high mid 这种组合负责处理区间那 mid 的取整方向就要刻意配合。我自己的规避办法是统一用左闭右闭 [low, high]、mid 向下取整、两边都加减 1。考试的时候不玩花活怎么稳怎么来。5.3 本地测试交互题的一个土办法很多新手拿到交互题不知道该在哪跑。我的建议是三步走第一步先写一个模拟函数把评测逻辑本地化。第二步在模拟函数里故意多设置几个不同的隐藏答案比如 x0、xn、x中间分别跑一遍你的算法。第三步检查查询次数在代码里加一个计数器看最坏情况下极限数据会不会爆限制。如果你用的是我上面那种 const 常量来模拟 secretX临时改来改去很麻烦可以改成从命令行参数读入或者直接随机一个 x。但要注意本地随机验证通过只能说明算法大概率没问题不代表评测机上一定 AC。真正的分界线还是你对交互协议的理解和边界情况的处理。下面是一个常见问题速查表我在比赛现场遇到这些问题时会翻一眼症状可能原因解决方式程序卡死不返回输出后没有 flushcout 加 endl或 printf 后 fflush(stdout)查询次数超限每次查询只排除了一个候选点改成二分或三分的区间收缩输出答案一直错区间更新方向反了在本地里用 print 跟踪 low/high/mid答案偶尔对偶尔错隐藏答案在边界 x0 或 xn专门测试左右端点6. 怎么练构造题才算有效6.1 标签和难度怎么选Codeforces 的题目带了很多标签构造题对应的标签主要是 constructive algorithms交互题是 interactive二分是 binary search。如果你想系统练我建议你在 Problemset 里筛选 constructive algorithms按难度排序从 1200 分开始做起一路做到 1600 分左右。这个区间是构造题最经典的基础区间。太低了题目全是套路背诵练不出判断力太高了数学门槛可能把你劝退。1200 到 1600 刚好适合你建立“构造题思维肌肉”。每天不用多两道三题就够了重点是每一题都按我前面说的四步流程走形式化表达、弱构造、找瓶颈、验证边界。交互题单独的标签是 interactive数量不多但每一道都很值得做。我建议你把交互题放到已经有一定二分基础后再练因为交互题本质是“二分查找 输出格式注意事项”的组合如果你连普通二分都会写错直接做交互题只会打击自信心。6.2 复盘时记录什么很多人刷题只刷不复盘刷了 200 题水平还是原地踏步。我也走过这个弯路。后来我每次复盘构造题都在本地笔记里记这四样东西这题的核心约束是什么用一句话概括。我最开始卡住的点是什么是没想到极值还是没想到对称还是边界搞错AC 代码里最关键的 3 行是哪几行比如“输出 endl 保证刷新”“区间更新用 mid-1”这种。如果下次遇到类似题第一步应该做什么这四样东西不一定要写得很长但一定要写下来。尤其是“卡住的点”下次你再看到同样类型的题看到这个记录就会产生条件反射。我反复强调条件反射是因为构造题在时间压力下真的没有时间让你慢慢推理你靠的就是平时积累的反射。6.3 最后想分享的一点点心态构造题不像数学竞赛题它不是一个“高人一等”的题型。很多时候你只要敢试、敢写一个简单但不优雅的构造就能把分拿到手。在 ruler 这道题里easy 版本就是逼你先写出一个“很笨”的线性扫描。这个笨办法的意义不是拿分那么简单它是让你理解交互协议的最短路径。很多选手嫌暴力构造太丑非要直接想最终解法结果花了二十分钟还在空中楼阁里打转。我的经验是先跑通一个弱解再在弱解的基础上优化这比一上来就冲击最优解要高效得多。如果你也正在为构造题头疼希望这篇复盘能让你少走一点弯路。下次再碰到交互构造题先问自己三件事评测机会给我几个反馈理论查询次数下限是多少我能不能用二分把候选空间砍掉一半想清楚这三件事你已经领先大多数人了。