昨晚又卡在了一道 Div2 C 上看到题解第一行写着 “By Pigeonhole Principle”差点没把键盘拍烂。鸽巢原理这个名字我在入门书里见过但说实在的真正在 Codeforces 上刷题时我很少第一时间往这个方向想。后来陆续整理了一批涉及鸽巢原理的 CF 题我才意识到它根本不是那种可遇不可求的数学技巧而是很多题目藏在地板底下的承重墙——一旦看出来整道题的复杂度直接掉一个量级。这篇文章我不打算讲教科书式的定理证明而是直接以刷题为线索把鸽巢原理在 Codeforces 里的几种常见长相、对应的破题姿势、以及我亲自踩过的坑都梳理一遍。适合的人大概是rating 1200 到 1700 左右、经常在 Div2 C/D 卡壳、看完题解发现只缺一个“关键观察”的刷题党。1. 先搞清楚竞赛里的鸽巢原理到底长什么样1.1 鸽巢原理的三种表达教科书版本大家应该都记得把 n1 个物体放进 n 个抽屉至少有一个抽屉放了 2 个物体。但竞赛里真正常用的是它的两个变体。第一个是数量变体如果要把 n 个物体放进 m 个盒子且 n m那么至少有一个盒子里有至少 ceil(n/m) 个物体。第二个是模运算变体如果我有 m 种余数却生成了 m1 个数那么必然有两个数对模 m 同余——这两个数的差就是 m 的倍数。第三个变体容易被忽略但出题人特别喜欢用当一个问题的“答案状态数”远小于“输入规模”时答案从一开始就已经由鸽巢原理锁死了你要做的只是把它找出来。这个变体在后面 CF 1500A 那道题里会有非常直观的体现。我自己的体会是刷题时不要死记“鸽巢原理”这个名字而是把它当成一种“数量压过状态数”的直觉只要某个东西的可能取值只有 K 种而你手里有超过 K 个样本那么重复是不可避免的。重复这个词才是大多数题目的题眼。1.2 竞赛里最高频的三个“变体”我把 Codeforces 里跟鸽巢沾边的题粗略分了三类这三类几乎覆盖了九成以上的情况第一类是“余数抽屉”。给定一个数组和一个模数 m让你判断是否存在某个子序列或连续子段其和能被 m 整除。这类题的核心就是把前缀和对 m 取模前缀和数量是 n1而余数只有 m 种一旦 n1 m同余的两个前缀和之间夹的那一段就是答案。CF 577B 就是这个模型的典型代表。第二类是“值域桶”。问题的答案状态是数值比如两个数的和这个和的取值范围有限。当两两组合的数量超过和的取值范围时一定有两个组合的和重复。CF 1500A 就是拿这个原理把看似不可做的 O(n²) 暴力“安全化”的经典例子。第三类是“构造保证”。题面里带着“必然存在”“至少有两个”这类字眼通常解法是先通过鸽巢原理证明答案一定存在再根据这个存在性去设计构造或者搜索。这种题在 Div2 B/C 里很常见有时候你证出来存在性之后连构造都变得顺理成章。变体触发信号典型套路代表题余数抽屉出现取模、整除、前缀和前缀和取模找同余CF 577B值域桶和的范围远小于组合数用桶或哈希表记录状态CF 1500A构造保证“必然存在”“至少两个”先证存在性再构造Div2 B/C 常客2. 两道必须吃透的 Codeforces 原题2.1 CF 577B Modulo Sumn m 时直接输出 YES 的底气从哪来这道题我第一次做的时候没往鸽巢想上去就是裸的背包 DP结果 n 开到 1e6直接 MLE。后来才知道第一步应该先看 n 和 m 的大小关系。题意很简单给一个长度为 n 的数组问是否存在一个非空子序列使得这个子序列的和能被 m 整除。m 最大只有 1000但 n 可以很大。很多人第一反应是 DP因为 m 很小对余数做背包看起来可行。但 n 大到一定程度时连输入扫描一遍都嫌多更别提 DP 了。关键观察是如果 n m答案一定是 YES。为什么考虑数组的前缀和 S[i] (a[1] a[2] ... a[i]) mod m再规定 S[0] 0。这样的前缀和一共有 n1 个而余数只有 m 种。当 n m 时n1 m由鸽巢原理必然存在两个不同的前缀和 S[p] 和 S[q] 满足 S[p] S[q]。于是 a[p1] 到 a[q] 这一段的和模 m 为 0这一段作为子序列是合法的答案自然就是 YES。有了这个结论DP 就只需要在 n m 的情况下跑。此时 n 最多 999m 最多 1000复杂度 O(n*m) 大约 1e6 级别随便写都能过。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorint a(n); for (int i 0; i n; i) { cin a[i]; a[i] % m; } if (n m) { cout YES\n; return 0; } vectorint dp(m, 0); for (int i 0; i n; i) { vectorint ndp dp; ndp[a[i]] 1; for (int j 0; j m; j) { if (dp[j]) { ndp[(j a[i]) % m] 1; } } if (ndp[0]) { cout YES\n; return 0; } dp move(ndp); } cout NO\n; return 0; }这段代码里有个细节值得多说一句ndp[a[i]] 1 这一行赋值很关键它保证了子序列可以从当前元素单独出发不会漏掉“只选一个 a[i]”的情况。但也要注意这行要在循环 j 之前执行因为 j 的循环里 dp[j] 是上一轮的状态如果先更新了 ndp 再基于 dp 转移不会有问题但如果你贪图省事直接复用 dp 原地转移就会出现同一个元素被多次使用的错误。2.2 CF 1500A Going Home值域桶和鸽巢的正面碰撞如果说 577B 是“余数抽屉”的教科书那 1500A 就是“值域桶”的最典型代表。题意是给定一个长度为 n 的数组 a找到四个下标 i, j, k, l两两不同且满足 a[i] a[j] a[k] a[l]。n 最大可以到 2e5值域大约是 2.5e6。直接枚举所有下标对是 O(n²)显然不可行。但你反过来想两个数的和能取得多少种不同的值最大值约为 5e6。也就是说和的取值空间只有 500 万个而下标对的数量是 n(n-1)/2在 n 较大时远超 500 万。由鸽巢原理必然存在两个不同的下标对具有相同的和。问题在于两对下标相同之和它们的四个下标可能不是互不相同的比如 (1, 3) 和 (1, 5) 共享了下标 1。这种情况在实现里比想象中常见。我第一次写的时候没注意这个细节直接找到一个相同和就输出结果 WA 了一发。正解的做法是用一个数组或哈希表记录每个和值第一次出现的下标对然后枚举所有 (i, j)。遇到一个和值已经出现过的检查之前记录的下标对和当前下标对是否有交集如果完全没有交集答案就找到了。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorint a(n); for (int i 0; i n; i) cin a[i]; const int MAX_SUM 5000005; vectorpairint, int first(MAX_SUM, {-1, -1}); for (int i 0; i n; i) { for (int j i 1; j n; j) { int s a[i] a[j]; if (first[s].first ! -1) { auto [x, y] first[s]; if (x ! i x ! j y ! i y ! j) { cout YES\n; cout x 1 y 1 i 1 j 1 \n; return 0; } } else { first[s] {i, j}; } } } cout NO\n; return 0; }这里有个性能话题值得展开这个代码表面上是 O(n²)但实测在 CF 数据下不会超时。原因就在于鸽巢原理——一旦枚举到一定数量的下标对相同和必然出现而只要出现一组四个互异下标程序就直接输出了如果始终找不到说明所有相同和的下标对都集中在同几个下标上这种情况能容纳的下标对数量极其有限枚举量也被卡在一个可控范围内。换句话说鸽巢原理在这里不是单纯的理论证明而是实打实地把最坏情况的枚举规模压下来了。2.3 顺带一提n1 个球放进 n 个格子的直接应用有个比 1500A 简单得多、但出镜率极高的变体给你 n1 个整数每个数的取值范围是 1 到 n让你找出任意两个相等的数。这题直接开一个布尔数组标记遇到重复就输出看起来简单但它是很多复杂题的基础模块。我在 Div2 的 B 题里见过不少这个模型的“马甲”比如一个数组经过某种变换后变成新数组要求找重复元素又比如给你 n 个区间让你找两个重叠的区间端点。这些题剥掉外壳之后核心都是“数量超过取值空间重复必然存在”。把这一层想明白做题时就不会被各种包装唬住。3. 把题面翻译成“鸽巢信号”的实战直觉3.1 看到“至少/必然/存在两个”时的条件反射很多刷题党一看到“至少存在两个”就觉得这题要构造、要贪心其实这类措辞往往是鸽巢原理的信号。如果题面里同时出现了“任意”“无论怎么安排”“必然存在”这些词那八成是先拿鸽巢证一遍存在性再考虑怎么把这个存在的东西找出来。我现在的做题习惯是读完题先把题面里的关键短语划出来如果出现“至少两个”“必然有”“重复”这类词我会在草稿纸上单独写一行“Pigeonhole candidate”然后开始统计这里面的“数量”和“状态数”分别是什么数量是不是比状态数多一旦答案是肯定的这题的核心思路基本就浮出水面了。3.2 数量 vs 值域的差值一眼看穿更通用一点的识别方式是看数量和取值空间的比值。数组长度 n 有 2e5而某个状态的取值只有 1000 种组合数有 1e10而和的取值范围只有 5e6。这些巨大的数量差就是出题人给你留的门缝。遇到这种情况不要急着优化常规算法先停下来问自己一句需要处理的“状态”到底有多少种如果状态数远小于输入规模鸽巢原理必然会制造重复而重复往往就是解题的抓手。这比一上来想线段树、二分、数论要直接得多也快得多。3.3 前缀和取模最常用的转化前缀和取模是鸽巢原理在算法题里最经典、也最容易被忽略的转化方式。只要题目涉及“连续子段能/不能如何如何”而模数又比较小我就优先想前缀和取模。两个前缀和同余等价于它们之间的连续段和模 m 为 0。这个转化把“找子段”变成了“找重复的桶”复杂度往往直接从 O(n²) 降到 O(n)。但要注意前缀和取模只能处理连续子段不能直接处理任意子序列。CF 577B 里 n m 的剪枝之所以成立是因为连续子段本身就是一个合法的子序列但如果题目要求的是任意选取若干个数且不要求连续那前缀和的思路就不够了需要回到 DP 或其他方法。4. 我踩过的几个坑4.1 “四个下标互不相同”看着简单写起来全是 bugCF 1500A 的 AC 代码竞争者里WA 得最多的原因就是下标判重写错。很多人知道要判断 i, j, k, l 互不相同但写出来的是 p.first ! i || p.second ! j 这种或逻辑把“两个下标都不能出现在另一对里”错写成“只要不完全相等就行”。我自己也栽过一次。记录里存的是 (2, 5)当前枚举到 (2, 6)两者只有一个下标重复本来应该跳过继续找我却因为 (2, 5) 和 (2, 6) 不完全相同就当成了合法答案。正确写法是if (p.first ! i p.first ! j p.second ! i p.second ! j)四个条件缺一不可任何一个下标出现在另一对里都不行。这个细节值得在本地多造几组数据测一下比如数组里很多重复值时非常容易触发这种共享下标的场景。4.2 子序列、子数组、非空读题错一个全盘皆输鸽巢原理相关的题目对“子段”的定义极其敏感。子序列可以不连续子数组必须连续非空意味着不能取空集而“至少两个”意味着至少要有两个元素。这些限定词直接决定前缀和思路能不能用、DP 状态要怎么设计。CF 577B 这道题官方题解里 n m 直接 YES 的证明用的是连续子段但因为连续子段也是子序列所以结论对“子序列”也成立。如果把题目改成“是否存在两个不同的空子序列”或者改成“恰好一个”整个结论都会崩掉。我的习惯是做题时先圈出这些限定词尤其是英文原题里的 subsequence、subarray、non-empty、distinct绝对不靠猜。4.3 存在性证明不能当构造用鸽巢原理告诉你“一定有解”但它不会告诉你解在哪。CF 577B 的 n m 剪枝只负责告诉你不用跑 DP 了但如果你遇到的是输出方案的版本还是得老老实实把 DP 跑一遍或者二分找答案。这一点在高强度刷题时尤其容易误判我有时候证完存在性就觉得自己会做了结果发现题目要输出具体下标还得重新设计算法。鸽巢原理的价值是帮你缩小搜索范围或者直接跳过不可能的情况但它很少直接给出答案本身。把“证明有解”和“求出解”两件事分开是避免浪费比赛时间的重要心法。5. 刷题路线与工具5.1 Codeforces 里怎么找鸽巢题Codeforces 的 Problemset 页面可以用标签筛选鸽巢原理对应的标签是 math 和 combinatorics但直接筛这两个标签范围太宽一天刷不完。我的做法是先按难度排序只看 rating 1200 到 1800 的题再从里面找题解或 Discussion 里出现过 pigeonhole 字眼的题逐个做。我自己用过一个叫 Codeforces Better 的增强工具它能在题目列表里叠加标签和题目评分筛选效率比原站高不少方便我做专项统计。如果你想系统刷我建议从以下顺序开始先做 577B 这种“余数抽屉”题再做 1500A 这种“值域桶”题然后去 Div2 B/C 里随机挑几道数学标签的题专门训练从题面措辞里捕捉“数量大于状态数”的感觉。这个顺序是从容易识别的题到需要自己挖掘的题递进比较舒服。5.2 我的做题节奏与笔记习惯我现在做一道涉及鸽巢的题节奏大致是这样的前 10 分钟先暴力写一版能过小数据的代码然后把 n 和 m 这些关键参数拉到极限看一看如果发现某个状态数很小而数量很大就停下来写一段“鸽巢检查”——把数量、状态数、可能的重复模式列在草稿纸上。这一步看起来浪费时间但往往能直接避免在错误方向上花一个小时。另外我会在笔记软件里专门建一个“抽屉原理”的标签页每道题只记三行题目编号、核心的“数量 vs 状态数”对比、以及 AC 代码里最关键的几行。刷到后面这个笔记本身就成了一个识别系统。比如再看到“n 很大、m 只有 1000”时我会本能地想到 577B 的模板看到“两个元素的和”时会立刻想到值域桶和 pair 判重。最后再分享一个实战小技巧在验证鸽巢原理相关的代码时多用全相同元素构造测试数据。比如 CF 1500A 的数组全为 1所有二元组和都是 2这时最容易暴露下标判重 bug也最能验证你的程序是否能在极端重复下快速退出。我见过不少代码在随机数据上能过却被全相同的数据卡到超时或 WA提前用这种数据测一遍能帮你省下一整场比赛的血压。
鸽巢原理在Codeforces刷题中的实战指南：从余数抽屉到值域桶
昨晚又卡在了一道 Div2 C 上看到题解第一行写着 “By Pigeonhole Principle”差点没把键盘拍烂。鸽巢原理这个名字我在入门书里见过但说实在的真正在 Codeforces 上刷题时我很少第一时间往这个方向想。后来陆续整理了一批涉及鸽巢原理的 CF 题我才意识到它根本不是那种可遇不可求的数学技巧而是很多题目藏在地板底下的承重墙——一旦看出来整道题的复杂度直接掉一个量级。这篇文章我不打算讲教科书式的定理证明而是直接以刷题为线索把鸽巢原理在 Codeforces 里的几种常见长相、对应的破题姿势、以及我亲自踩过的坑都梳理一遍。适合的人大概是rating 1200 到 1700 左右、经常在 Div2 C/D 卡壳、看完题解发现只缺一个“关键观察”的刷题党。1. 先搞清楚竞赛里的鸽巢原理到底长什么样1.1 鸽巢原理的三种表达教科书版本大家应该都记得把 n1 个物体放进 n 个抽屉至少有一个抽屉放了 2 个物体。但竞赛里真正常用的是它的两个变体。第一个是数量变体如果要把 n 个物体放进 m 个盒子且 n m那么至少有一个盒子里有至少 ceil(n/m) 个物体。第二个是模运算变体如果我有 m 种余数却生成了 m1 个数那么必然有两个数对模 m 同余——这两个数的差就是 m 的倍数。第三个变体容易被忽略但出题人特别喜欢用当一个问题的“答案状态数”远小于“输入规模”时答案从一开始就已经由鸽巢原理锁死了你要做的只是把它找出来。这个变体在后面 CF 1500A 那道题里会有非常直观的体现。我自己的体会是刷题时不要死记“鸽巢原理”这个名字而是把它当成一种“数量压过状态数”的直觉只要某个东西的可能取值只有 K 种而你手里有超过 K 个样本那么重复是不可避免的。重复这个词才是大多数题目的题眼。1.2 竞赛里最高频的三个“变体”我把 Codeforces 里跟鸽巢沾边的题粗略分了三类这三类几乎覆盖了九成以上的情况第一类是“余数抽屉”。给定一个数组和一个模数 m让你判断是否存在某个子序列或连续子段其和能被 m 整除。这类题的核心就是把前缀和对 m 取模前缀和数量是 n1而余数只有 m 种一旦 n1 m同余的两个前缀和之间夹的那一段就是答案。CF 577B 就是这个模型的典型代表。第二类是“值域桶”。问题的答案状态是数值比如两个数的和这个和的取值范围有限。当两两组合的数量超过和的取值范围时一定有两个组合的和重复。CF 1500A 就是拿这个原理把看似不可做的 O(n²) 暴力“安全化”的经典例子。第三类是“构造保证”。题面里带着“必然存在”“至少有两个”这类字眼通常解法是先通过鸽巢原理证明答案一定存在再根据这个存在性去设计构造或者搜索。这种题在 Div2 B/C 里很常见有时候你证出来存在性之后连构造都变得顺理成章。变体触发信号典型套路代表题余数抽屉出现取模、整除、前缀和前缀和取模找同余CF 577B值域桶和的范围远小于组合数用桶或哈希表记录状态CF 1500A构造保证“必然存在”“至少两个”先证存在性再构造Div2 B/C 常客2. 两道必须吃透的 Codeforces 原题2.1 CF 577B Modulo Sumn m 时直接输出 YES 的底气从哪来这道题我第一次做的时候没往鸽巢想上去就是裸的背包 DP结果 n 开到 1e6直接 MLE。后来才知道第一步应该先看 n 和 m 的大小关系。题意很简单给一个长度为 n 的数组问是否存在一个非空子序列使得这个子序列的和能被 m 整除。m 最大只有 1000但 n 可以很大。很多人第一反应是 DP因为 m 很小对余数做背包看起来可行。但 n 大到一定程度时连输入扫描一遍都嫌多更别提 DP 了。关键观察是如果 n m答案一定是 YES。为什么考虑数组的前缀和 S[i] (a[1] a[2] ... a[i]) mod m再规定 S[0] 0。这样的前缀和一共有 n1 个而余数只有 m 种。当 n m 时n1 m由鸽巢原理必然存在两个不同的前缀和 S[p] 和 S[q] 满足 S[p] S[q]。于是 a[p1] 到 a[q] 这一段的和模 m 为 0这一段作为子序列是合法的答案自然就是 YES。有了这个结论DP 就只需要在 n m 的情况下跑。此时 n 最多 999m 最多 1000复杂度 O(n*m) 大约 1e6 级别随便写都能过。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorint a(n); for (int i 0; i n; i) { cin a[i]; a[i] % m; } if (n m) { cout YES\n; return 0; } vectorint dp(m, 0); for (int i 0; i n; i) { vectorint ndp dp; ndp[a[i]] 1; for (int j 0; j m; j) { if (dp[j]) { ndp[(j a[i]) % m] 1; } } if (ndp[0]) { cout YES\n; return 0; } dp move(ndp); } cout NO\n; return 0; }这段代码里有个细节值得多说一句ndp[a[i]] 1 这一行赋值很关键它保证了子序列可以从当前元素单独出发不会漏掉“只选一个 a[i]”的情况。但也要注意这行要在循环 j 之前执行因为 j 的循环里 dp[j] 是上一轮的状态如果先更新了 ndp 再基于 dp 转移不会有问题但如果你贪图省事直接复用 dp 原地转移就会出现同一个元素被多次使用的错误。2.2 CF 1500A Going Home值域桶和鸽巢的正面碰撞如果说 577B 是“余数抽屉”的教科书那 1500A 就是“值域桶”的最典型代表。题意是给定一个长度为 n 的数组 a找到四个下标 i, j, k, l两两不同且满足 a[i] a[j] a[k] a[l]。n 最大可以到 2e5值域大约是 2.5e6。直接枚举所有下标对是 O(n²)显然不可行。但你反过来想两个数的和能取得多少种不同的值最大值约为 5e6。也就是说和的取值空间只有 500 万个而下标对的数量是 n(n-1)/2在 n 较大时远超 500 万。由鸽巢原理必然存在两个不同的下标对具有相同的和。问题在于两对下标相同之和它们的四个下标可能不是互不相同的比如 (1, 3) 和 (1, 5) 共享了下标 1。这种情况在实现里比想象中常见。我第一次写的时候没注意这个细节直接找到一个相同和就输出结果 WA 了一发。正解的做法是用一个数组或哈希表记录每个和值第一次出现的下标对然后枚举所有 (i, j)。遇到一个和值已经出现过的检查之前记录的下标对和当前下标对是否有交集如果完全没有交集答案就找到了。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorint a(n); for (int i 0; i n; i) cin a[i]; const int MAX_SUM 5000005; vectorpairint, int first(MAX_SUM, {-1, -1}); for (int i 0; i n; i) { for (int j i 1; j n; j) { int s a[i] a[j]; if (first[s].first ! -1) { auto [x, y] first[s]; if (x ! i x ! j y ! i y ! j) { cout YES\n; cout x 1 y 1 i 1 j 1 \n; return 0; } } else { first[s] {i, j}; } } } cout NO\n; return 0; }这里有个性能话题值得展开这个代码表面上是 O(n²)但实测在 CF 数据下不会超时。原因就在于鸽巢原理——一旦枚举到一定数量的下标对相同和必然出现而只要出现一组四个互异下标程序就直接输出了如果始终找不到说明所有相同和的下标对都集中在同几个下标上这种情况能容纳的下标对数量极其有限枚举量也被卡在一个可控范围内。换句话说鸽巢原理在这里不是单纯的理论证明而是实打实地把最坏情况的枚举规模压下来了。2.3 顺带一提n1 个球放进 n 个格子的直接应用有个比 1500A 简单得多、但出镜率极高的变体给你 n1 个整数每个数的取值范围是 1 到 n让你找出任意两个相等的数。这题直接开一个布尔数组标记遇到重复就输出看起来简单但它是很多复杂题的基础模块。我在 Div2 的 B 题里见过不少这个模型的“马甲”比如一个数组经过某种变换后变成新数组要求找重复元素又比如给你 n 个区间让你找两个重叠的区间端点。这些题剥掉外壳之后核心都是“数量超过取值空间重复必然存在”。把这一层想明白做题时就不会被各种包装唬住。3. 把题面翻译成“鸽巢信号”的实战直觉3.1 看到“至少/必然/存在两个”时的条件反射很多刷题党一看到“至少存在两个”就觉得这题要构造、要贪心其实这类措辞往往是鸽巢原理的信号。如果题面里同时出现了“任意”“无论怎么安排”“必然存在”这些词那八成是先拿鸽巢证一遍存在性再考虑怎么把这个存在的东西找出来。我现在的做题习惯是读完题先把题面里的关键短语划出来如果出现“至少两个”“必然有”“重复”这类词我会在草稿纸上单独写一行“Pigeonhole candidate”然后开始统计这里面的“数量”和“状态数”分别是什么数量是不是比状态数多一旦答案是肯定的这题的核心思路基本就浮出水面了。3.2 数量 vs 值域的差值一眼看穿更通用一点的识别方式是看数量和取值空间的比值。数组长度 n 有 2e5而某个状态的取值只有 1000 种组合数有 1e10而和的取值范围只有 5e6。这些巨大的数量差就是出题人给你留的门缝。遇到这种情况不要急着优化常规算法先停下来问自己一句需要处理的“状态”到底有多少种如果状态数远小于输入规模鸽巢原理必然会制造重复而重复往往就是解题的抓手。这比一上来想线段树、二分、数论要直接得多也快得多。3.3 前缀和取模最常用的转化前缀和取模是鸽巢原理在算法题里最经典、也最容易被忽略的转化方式。只要题目涉及“连续子段能/不能如何如何”而模数又比较小我就优先想前缀和取模。两个前缀和同余等价于它们之间的连续段和模 m 为 0。这个转化把“找子段”变成了“找重复的桶”复杂度往往直接从 O(n²) 降到 O(n)。但要注意前缀和取模只能处理连续子段不能直接处理任意子序列。CF 577B 里 n m 的剪枝之所以成立是因为连续子段本身就是一个合法的子序列但如果题目要求的是任意选取若干个数且不要求连续那前缀和的思路就不够了需要回到 DP 或其他方法。4. 我踩过的几个坑4.1 “四个下标互不相同”看着简单写起来全是 bugCF 1500A 的 AC 代码竞争者里WA 得最多的原因就是下标判重写错。很多人知道要判断 i, j, k, l 互不相同但写出来的是 p.first ! i || p.second ! j 这种或逻辑把“两个下标都不能出现在另一对里”错写成“只要不完全相等就行”。我自己也栽过一次。记录里存的是 (2, 5)当前枚举到 (2, 6)两者只有一个下标重复本来应该跳过继续找我却因为 (2, 5) 和 (2, 6) 不完全相同就当成了合法答案。正确写法是if (p.first ! i p.first ! j p.second ! i p.second ! j)四个条件缺一不可任何一个下标出现在另一对里都不行。这个细节值得在本地多造几组数据测一下比如数组里很多重复值时非常容易触发这种共享下标的场景。4.2 子序列、子数组、非空读题错一个全盘皆输鸽巢原理相关的题目对“子段”的定义极其敏感。子序列可以不连续子数组必须连续非空意味着不能取空集而“至少两个”意味着至少要有两个元素。这些限定词直接决定前缀和思路能不能用、DP 状态要怎么设计。CF 577B 这道题官方题解里 n m 直接 YES 的证明用的是连续子段但因为连续子段也是子序列所以结论对“子序列”也成立。如果把题目改成“是否存在两个不同的空子序列”或者改成“恰好一个”整个结论都会崩掉。我的习惯是做题时先圈出这些限定词尤其是英文原题里的 subsequence、subarray、non-empty、distinct绝对不靠猜。4.3 存在性证明不能当构造用鸽巢原理告诉你“一定有解”但它不会告诉你解在哪。CF 577B 的 n m 剪枝只负责告诉你不用跑 DP 了但如果你遇到的是输出方案的版本还是得老老实实把 DP 跑一遍或者二分找答案。这一点在高强度刷题时尤其容易误判我有时候证完存在性就觉得自己会做了结果发现题目要输出具体下标还得重新设计算法。鸽巢原理的价值是帮你缩小搜索范围或者直接跳过不可能的情况但它很少直接给出答案本身。把“证明有解”和“求出解”两件事分开是避免浪费比赛时间的重要心法。5. 刷题路线与工具5.1 Codeforces 里怎么找鸽巢题Codeforces 的 Problemset 页面可以用标签筛选鸽巢原理对应的标签是 math 和 combinatorics但直接筛这两个标签范围太宽一天刷不完。我的做法是先按难度排序只看 rating 1200 到 1800 的题再从里面找题解或 Discussion 里出现过 pigeonhole 字眼的题逐个做。我自己用过一个叫 Codeforces Better 的增强工具它能在题目列表里叠加标签和题目评分筛选效率比原站高不少方便我做专项统计。如果你想系统刷我建议从以下顺序开始先做 577B 这种“余数抽屉”题再做 1500A 这种“值域桶”题然后去 Div2 B/C 里随机挑几道数学标签的题专门训练从题面措辞里捕捉“数量大于状态数”的感觉。这个顺序是从容易识别的题到需要自己挖掘的题递进比较舒服。5.2 我的做题节奏与笔记习惯我现在做一道涉及鸽巢的题节奏大致是这样的前 10 分钟先暴力写一版能过小数据的代码然后把 n 和 m 这些关键参数拉到极限看一看如果发现某个状态数很小而数量很大就停下来写一段“鸽巢检查”——把数量、状态数、可能的重复模式列在草稿纸上。这一步看起来浪费时间但往往能直接避免在错误方向上花一个小时。另外我会在笔记软件里专门建一个“抽屉原理”的标签页每道题只记三行题目编号、核心的“数量 vs 状态数”对比、以及 AC 代码里最关键的几行。刷到后面这个笔记本身就成了一个识别系统。比如再看到“n 很大、m 只有 1000”时我会本能地想到 577B 的模板看到“两个元素的和”时会立刻想到值域桶和 pair 判重。最后再分享一个实战小技巧在验证鸽巢原理相关的代码时多用全相同元素构造测试数据。比如 CF 1500A 的数组全为 1所有二元组和都是 2这时最容易暴露下标判重 bug也最能验证你的程序是否能在极端重复下快速退出。我见过不少代码在随机数据上能过却被全相同的数据卡到超时或 WA提前用这种数据测一遍能帮你省下一整场比赛的血压。
