在 Codeforces 上刷题刷到一定量你会发现有个很有意思的现象很多看起来需要高深算法的题最后居然是被一个初中奥数就讲过的“鸽巢原理”一巴掌拍死的。这篇文章就围绕我最近刷题时反复撞上的这个主题展开尤其是 Codeforces Round 964 (Div. 4) 的 G1/G2 Ruler 这两道交互题从 easy 到 hard几乎是把鸽巢原理的应用方式摆在了台面上。如果你正在刷 CF 的 Div.3/Div.4或者想搞懂交互题里“为什么二分次数够用”的底层逻辑这篇应该能帮你省不少力气。1. 鸽巢原理Codeforces 刷题里最难认的“简单模型”1.1 别被名字吓到鸽巢原理讲到底在说什么鸽巢原理也叫抽屉原理听起来像是小学奥数里拿来唬人的名字但核心就一句话如果 n1 个东西要放进 n 个抽屉那么必然存在一个抽屉里至少有两个东西。反过来讲更实用如果你想把 m 个可能的情况分到若干组里而组数少于情况数那就一定有两组“共用”了同一个情况或者说必然有一些情况被分在了一起。这个原理在 Codeforces 题里最常见的出场方式其实不是“找重复”而是“保证存在性”。比如经典的“从 n1 个数中总能找到两个数它们的差能被 n 整除”就是看这些数对 n 取模的结果。模 n 的余数只有 n 种但你手里有 n1 个数那必然有两个余数相同这两个数的差自然被 n 整除。我在刷 CF 时越来越感觉到鸽巢原理很少作为题的“唯一考点”出现更多时候它是藏在结论背后的那根顶梁柱。很多题的解法乍一看是构造、是二分、是贪心但你要追问他为什么可行最后都会落到“把有限种情况划分到有限个盒子里盒子不够用所以一定有某种结构”这个逻辑上。1.2 Codeforces 题目里鸽巢原理常见的三种出场姿势第一种是“余数抽屉”。给定一组数和某个模数让你证明或构造某两个数之间的关系最常见的就是前缀和模 n、区间和整除、或找两个下标使某段区间满足条件。这类题你一旦想到取模代码通常很短但难点恰恰在于“能不能想到取模”。第二种是“二分与决策树”。这一点很多人没意识到二分查找本身就有鸽巢原理的味道。你每次把一个区间切成左右两半答案要么在左要么在右这相当于把“答案所有可能位置”放进了两个抽屉根据反馈丢掉一个抽屉在另一个抽屉里继续切。二分为什么最多需要 log n 次因为 n 个候选答案要放进 2^k 个“叶子抽屉”里如果 2^k n就必然有两个不同答案共用同一个叶子那样你没法区分它们也就不可能保证猜中。第三种是“交互题里的信息量限制”。Codeforces 的交互题经常给一个询问次数上限比如“最多问 10 次”“最多问 20 次”。这种限制本质上也在用鸽巢原理每次询问的返回结果种类是有限的比如返回 0/1或者返回 / / 那么 q 次询问最多只能区分 2^q 种情况。如果候选答案的总数大于 2^q那你必然没办法在所有情况下都正确输出。Ruler 这道题正好就是一个活生生的例子。2. 一道典型例题Round 964 Div.4 的 Ruler 问题2.1 题目背景G1 ruler (easy version)Codeforces Round 964 (Div. 4) 的 G1/G2 构成了一个典型的“easy hard”双版本设计。G1 是 easy versionG2 是 hard version两道题共享同一个交互模型只是在询问次数限制上做了收紧。这题的背景是一把“尺子”。我按赛时记忆做个简化描述有一把刻度范围在 1 到 1000 之间的尺子但它中间缺了一小段你需要通过交互来定位这个缺失位置对应的隐藏数字。实际交互时你每次输出一个查询系统会给你一个反馈结果通过多轮查询最终你要输出隐藏数字是什么。为什么叫 ruler因为题面用了尺子的隐喻让你去“量”出缺失的那一段。但算法上它就是一个典型的“范围缩减”类交互题跟你高中玩过的猜数字游戏本质一样我心里想一个 1 到 1000 之间的数你每次猜一个数我告诉你大了还是小了你要在限定次数内把它猜出来。2.2 G2 ruler (hard version) 到底加在哪G2 是 G1 的加强版。两道题的目标一样都是定位隐藏数字但 G2 把询问次数压得更低。赛时很多人的体验是G1 用比较宽松的查询策略能过到了 G2 同样的策略就超次数了必须换思路。这其实是 Codeforces 双版本题目的一贯套路easy version 考察你“能不能把这个交互模型跑通”hard version 考察你“能不能在最优复杂度下跑通”。G1 可能允许你多问几次甚至可以比较接近线性地收缩范围G2 则要求你必须在对数级别的询问次数内完成定位。换句话说G1 是让你先理解规则G2 是逼你找到理论下界。而这个理论下界恰好就是由鸽巢原理给出来的。2.3 为什么这道题是鸽巢原理的教科书案例很多人第一眼看到 Ruler 这道题知道要用二分但没细想“为什么二分就够用”。当你把候选答案总数看作 n把每次询问的反馈看作“把当前候选集切成若干个互不相交的盒子”那么一场游戏下来本质上就是不断重复“切盒子、丢掉不含答案的盒子”的过程。如果每次询问只返回两类结果比如“目标在左边”和“目标在右边”那么一次询问只能把候选集切成 2 个盒子。进行 q 次询问理论上最多能区分 2^q 个不同的叶子。候选总数是 1000所以就需要满足 2^q ≥ 1000。2^9 512不够2^10 1024刚好够。这就是为什么 10 次查询是一个关键阈值。如果题目把询问次数限制在 9 次那根据鸽巢原理1000 个候选答案分到 512 个叶子盒子里必然有两个答案走到同一个叶子也就是说交互反馈无法区分它们这题就无解了。Ruler 的 G2 之所以可行是因为它把次数限制设定在了刚好能够覆盖所有候选情况的数量级上而这正是鸽巢原理直接导出的结论。3. 从 easy 到 hard交互策略与查询次数的推导3.1 先把交互规则翻译成人话在写解法之前先把交互题的规则翻译成能直接写代码的逻辑。竞赛中的交互题和普通题目的区别在于你的程序不是一次性读完整份输入而是和交互器“一问一答”。你输出一个查询它返回一个结果你再根据结果输出下一个查询直到得出最终答案。对于 Ruler 这种猜数字模型每轮你输出一个猜测值 m交互器告诉你目标 x 和 m 的大小关系。比较常见的反馈形式有 0/1 两种比如返回 0 表示 m x返回 1 表示 m ≥ x或者反过来。具体数值代表什么以题目原文为准但核心逻辑是一样的每次查询都在帮你排除掉一部分候选值。这里有一个新手容易忽略的点交互题的多组数据是连续进行的上一组数据的答案不会带到下一组每一组都要重新初始化左右边界。很多人在 G1/G2 上交了四五发 WA不是算法错了而是多组数据之间没有重置区间。3.2 easy 版本的赛时思路与实现G1 作为 easy version查询次数给得比较宽裕理论上你甚至可以每次从 1 开始逐个试探。但实际没人会那么干正常的做法已经是二分了因为二分写起来简单而且次数一定够用。伪代码大概是设 l 1, r 1000每次取 mid (l r) / 2查询 mid。如果反馈表示目标在 [l, mid] 区间就令 r mid否则令 l mid 1。循环直到 l r最终 l 就是隐藏数字。这个版本的难点不在算法而在“敢不敢写交互”。很多 Div.4 的选手平时几乎不碰交互题第一反应是恐惧觉得交互题很难。其实交互题的关键就两个一是清楚自己每一步在问什么二是保证输出后刷新缓冲区让交互器及时收到消息。把这两点做好G1 就是一道普通的二分题。3.3 hard 版本的二分下界⌈log2 1000⌉ 10 是怎么来的G2 把查询次数压到接近理论极限这时候光知道“用二分”还不够你得确认自己的二分次数确实够用。我们可以把整棵查询决策树画出来最开始有 1000 个候选答案。第一次查询后根据反馈候选集被分成两类一类是“反馈 A 对应的候选集合”另一类是“反馈 B 对应的候选集合”。第二次查询后两类又各被分成两小类总共变成 4 类。查询 q 次后最多产生 2^q 个叶子。现在我们手里有 1000 个候选答案它们最终必须分别落在不同的叶子里否则有两个答案会让交互器产生完全相同的反馈序列程序就没法区分它们。所以必须满足 2^q ≥ 1000。因为 2^9 512小于 1000不够用2^10 1024刚好超过 1000所以 q 的最小值是 10。这个推导过程就是鸽巢原理的反向表述如果允许的查询次数导致叶子数少于候选数那么必然存在至少两个候选答案被塞进同一个叶子。G2 的存在就是让你亲手验证这个结论——次数给到 10题目可解次数给到 9无解。理解这一点之后你就不会再纠结“为什么偏偏是 10 次”了。3.4 鸽巢原理在这里面的真正作用有人可能会觉得讲了一大堆鸽巢原理最后不就是二分吗对算法确实是二分但鸽巢原理给了你两个非常重要的判断工具。第一它能帮你判断“题目给的上限够不够”。如果一道交互题隐藏数字范围是 n每次反馈有两种结果那么最低查询次数就是 ⌈log2 n⌉。你不需要去试错直接用这个式子算。第二它能帮你理解为什么有些优化是必要的。假如 G2 把范围扩大到 2000那么 10 次就不够了至少需要 11 次因为 2^10 1024 2000。你每一次询问都在扩大“叶子盒子”的数量而这正好对应着你能够区分多少种不同的答案。我在刷题时养成了一个习惯拿到交互题先不急着写代码先把候选答案总数和反馈类型数写出来算一下理论下界 q_min。如果当前策略的询问次数远高于 q_min大概率还能优化如果题目要求的次数低于 q_min那说明题目本身就不可能用单纯二分解决需要换一种反馈类型更多的查询方式。这个习惯帮我避免了很多无谓的 WA。4. 完整 C 实现与踩坑实录4.1 一套可以直接改的参考代码下面我给出一份核心逻辑的 C 参考代码。注意不同场次、不同题目的反馈含义可能不同你需要根据题目原文调整“反馈等于多少时往左缩”这个判断条件。#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 1, r 1000; while (l r) { int mid (l r) / 2; cout ? mid endl; int res; cin res; // 这里假设 res 1 表示答案在 [l, mid] 区间 // 具体写的时候以题目给出的交互格式为准 if (res 1) { r mid; } else { l mid 1; } } cout ! l endl; } return 0; }这套代码的核心就是标准二分。如果你做过 Codeforces 上的猜数字交互题会发现代码结构几乎一样。真正容易出问题的不是二分逻辑而是交互题的周边细节。4.2 交互题最容易翻车的三个地方第一个坑是输出后没有刷新缓冲区。C 里如果用的是cout一定要在每次查询输出后endl它会强制刷新输出缓冲区。如果你偷懒用\n有些环境下交互器可能收不到你的输出导致程序一直卡住最后被判 TLE 或者 Idleness Limit Exceeded。我发现很多第一次做交互题的人都会踩这个坑而且很难自己排查因为本地跑起来好像没问题。第二个坑是多组数据之间没有重置状态。有些选手是复制上一题的代码改的写着写着把while (T--)里的 l、r 初始化放到循环外面了结果第二组数据直接沿用上一组的边界输出一个离谱的答案。这个问题在普通题里可能只是 WA但在交互题里可能直接导致交互流程乱掉。第三个坑是猜测输出格式。交互题的最终输出通常是! 答案前面不要加多余的空格、逗号、描述性文本。有些人喜欢在输出里加个cout answer is l endl;这种调试信息这在普通题里无所谓但在交互题里会直接让交互器解析失败导致一堆莫名其妙的 WA。调试信息该注释就注释或者用cerr输出到错误流。4.3 我在刷这题时踩过的坑和排查过程我打 Round 964 的时候G1 一次过了G2 反而卡了两发。第一发 WA 是我把二分的上下界写成了 0 和 1000结果隐藏数字如果是 1000某次查询可能问出边界外的数字题目的隐藏数字范围是 1 到 1000我应该初始化为 l 1, r 1000。当时我以为这是个无关紧要的细节后来发现题目对查询的数字范围可能有要求越界查询会被判成非法交互。第二发超时是因为我用了cout ? mid \n;没有刷新缓冲区。当时本地测试一切正常但提交后直接 TLE。排查了很久才发现是刷新问题改成endl立马上绿。后来我养成了一个习惯交互题的输出一律用endl反正一次查询也就输出一个数字刷新开销可以忽略不计。还有一版代码我把查询结果判断反了因为我没仔细看题面里0和1分别代表什么只是想当然地写了个if (res 0) { l mid 1; }。后来对着样例模拟了一遍才意识到反馈含义反了。交互题真的不能凭感觉猜反馈含义一定要把题目里的交互说明逐字看完否则就是白白送分。下面把这几个常见问题整理成一个速查表方便以后直接对照排查问题可能原因检查方法TLE / Idleness Limit Exceeded输出后没有刷新缓冲区检查是否用了endl或fflush(stdout)WA 且答案很奇怪多组数据没有重置左右边界确认l 1; r 1000;在每次循环内交互器反馈非法查询了范围外的数字检查二分上下界是否和题目范围一致答案差 1二分判断条件反了用样例手动模拟一遍反馈含义5. 从 Ruler 到全场鸽巢原理的扩展应用与刷题建议5.1 Codeforces 里其他喜欢藏鸽巢原理的题Ruler 只是一个引子。CF 里还有不少题表面看起来和鸽巢原理没关系实际上核心论证全在它身上。一类是“出现次数/颜色”类题目。比如给你一个序列让你证明某种情况必然出现。典型套路是把每个元素按某类标准分桶桶数小于元素数于是必有桶里塞进了至少两个元素再从这里推导出题目要的结构。这类题在 div2 的 C、D 题里经常出现很考验观察力。另一类是“前缀和模数”类问题。给你一个长度为 n 的数组问是否存在某个连续子段的和能被 n 整除。做法是计算前缀和并对 n 取模n 个前缀里如果有两个余数相同那这两个前缀中间的区间和一定是 n 的倍数。如果 n 个前缀和的 n 个余数都不相同那么必然有一个前缀的余数是 0也能得到解。无论哪种情况结论都成立这正是鸽巢原理的典型应用。还有一类是交互题的推广。很多交互题本质上都是在有限候选集里做排除候选集越大需要的查询次数越多。你只要看到题目规定了查询次数上限并且每次询问的反馈类型有限就可以条件反射地想到用鸽巢原理来算信息量上界这能让你快速判断题目是否可解。5.2 怎么训练自己“看出鸽巢原理”的直觉很多读者可能会问道理我都懂但真到比赛里我就是看不出来这题能用鸽巢原理怎么办我的经验是做这类题时多问自己三个问题第一题目里有没有一个有限且明确的总数比如“n 个元素”“1000 个候选答案”“m 种余数”。如果你想找矛盾或证明必然性先把这个总数圈出来。第二题目里有没有一个比总数小的“分类数”比如模 n 的余数有 n 种但你拿着 n1 个数比如询问次数为 q最多产生 2^q 种反馈。分类数和总数一比如果总数更大鸽巢原理大概率是突破口。第三题目结论是否涉及“存在”“必然”“至少”如果是那它很可能是在考察存在性证明而鸽巢原理是竞赛中最常用的存在性武器。平时刷题的时候我建议准备一个专门的记录文档每遇到一道和鸽巢原理相关的题就记下它的核心套路比如“前缀和取模”“二分下界计算”“分组构造”等等。积累几十道之后你再看新的题目就能自动联想到对应模式靠的就是量变到质变。5.3 刷题时的几个实用心得最后分享几个我自己的刷题心得都是反复踩坑后总结出来的。第一打 CF 的 Div.3/Div.4 时不要因为题目简单就跳过思路直接写代码。像 Ruler 这种题最难的部分其实是把题面里的交互规则看明白而不是二分本身。我见过太多人代码写得飞快结果反馈含义理解错白交好几发。第二学会用“信息量”的角度去看交互题。拿到一道交互题先算候选答案总数 n 和每次反馈类型数 k那么理论上最少查询次数就是 ⌈logk n⌉。如果这个数大于题目限制那么无论你怎么设计查询都不可能通过如果小于题目限制说明还有优化空间。这个思维方式的来源就是鸽巢原理。第三比赛中如果卡题超过二十分钟果断换个角度重新读题。很多时候我们陷在一种解法里出不来是因为下意识地给自己加了很多题目里根本没有的限制条件。Ruler 这题如果你只想着“怎么优化暴力枚举”而没想到“答案范围只有 1000 个、10 次交互足够覆盖”就会一直绕远路。退一步把范围、次数、反馈类型这几个数字列出来往往思路就通了。
