P1102 A-B 数对在洛谷上被标成“普及-”不少新手扫一眼觉得是白给题统计差值等于 C 的数对嘛我两层循环直接数不就行了。可真提交上去迎面就是 TLE这时候才开始怀疑人生。我自己带新人训练时发现这道题其实是非常典型的“二分和双指针入门练手题”它把“枚举位置”硬生生变成了“统计值出现次数”思路一旦转过来后面做两数之和、区间配对之类的问题都会顺手很多。这篇文章把我实际写过的三种解法、C0 这个坑、以及排查超时和重复计数的完整过程都整理出来给正在刷洛谷、或者以后要面对配对统计题型的同学做个参考。1. 先拆题P1102 的考点根本不在于“数对”1.1 题目到底说了什么题面原文很长但核心就一句给出一串数和一个数字 C统计满足 A-BC 的数对个数并且数组中不同位置的相同数字要算不同的数对。举个例子数组是 [2, 1, 1, 1]C1那么 A2 这个位置可以和三个 B1 的位置分别组成数对答案是 3 而不是 1。这一点非常重要很多人第一次做就是在这里漏掉计数。另一个容易被忽略的点是数对是有方向的A 在前B 在后A-BC。也就是说 3-12 是一对数对但 1-3-2 不是。搞清楚这点之后问题就转化为对于每个位置上的 A去找数组里有没有足够多个值为 A-C 的 B。如果某个值出现多次只要 A 的位置不同每个组合都要算一次。1.2 数据范围决定了你只能往 O(n log n) 想题目给的 N 最大可以到 200000 左右具体看洛谷原题的数据范围反正不是几十这种小规模。两层循环枚举 i 和 j复杂度是 n²200000 的平方是 4×10^10。你可以简单估算一下现代 CPU 一秒大约能跑 10^8 到 10^9 次简单运算4×10^10 意味着至少要几十秒TLE 是必然的。所以这道题的核心考点根本不是“你会不会枚举数对”而是“你会不会把枚举位置对改成枚举一个值并快速统计另一个值出现的次数”。排序在这里是总钥匙排序之后所有相等的值会聚成连续的一段一段的长度就是出现次数。配合二分查找 lower_bound 和 upper_bound就能在 O(log n) 时间内知道任意值出现了几次整体复杂度降到 O(n log n)。2. 三种解法拆解为什么排序是这道题的总钥匙2.1 暴力枚举是第一直觉也是验证答案的基准先别急着鄙视暴力写对拍的时候它反而是最有用的工具。暴力写法非常直白long long ans 0; for (int i 0; i n; i) { for (int j 0; j n; j) { if (a[i] - a[j] c) { ans; } } }这段代码在 N 很小的时候完全正确可以用来当“标准答案”。我在实际开发验证算法时经常让优化的程序和小数据暴力程序对拍。如果你发现优化程序的输出和暴力不一致说明你的实现里存在重复计数或者漏计数的问题。暴力 O(n²) 虽然在正式提交时必挂但作为测试基准它比任何理论分析都靠谱。2.2 排序 二分统计“值”的出现次数而不是枚举“位置”这是最推荐掌握的解法。先对数组排序然后遍历每个位置 i把它当作 A那么 B 的值就应该是 target a[i] - c。此时只需要回答一个问题整个排序数组中有多少个元素的值等于 target为什么排序后这个问题好回答因为排序后所有等于 target 的元素挤在连续区间里。用 lower_bound 找到第一个不小于 target 的下标 L用 upper_bound 找到第一个大于 target 的下标 R那么 [L, R) 这个左闭右开区间里的元素全部等于 target个数就是 R-L。#include bits/stdc.h using namespace std; long long a[200005]; int n; long long c; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n c; for (int i 0; i n; i) cin a[i]; sort(a, a n); long long ans 0; for (int i 0; i n; i) { long long target a[i] - c; int L lower_bound(a, a n, target) - a; int R upper_bound(a, a n, target) - a; ans R - L; } if (c 0) ans - n; cout ans \n; return 0; }为什么 C 不等于 0 的时候不用管“当前位置被算进去”的问题因为 target a[i] - c当 c 不为 0 时target 永远不等于 a[i]。也就是说二分统计出来的那些 B 值不可能包含当前这个 A 的位置每个数对都是“A 在某个位置、B 在另一个位置”的有效配对。只有 c0 的时候 target 等于 a[i] 本身才会把当前位置也统计进去这个问题我放在下一章细说。2.3 同向双指针省掉二分的常数细节藏在指针关系里双指针是在排序基础上进一步把统计做到 O(n) 总时间。思路还是枚举 A找值等于 target 的区间只不过这次维护两个指针 L 和 R分别指向当前 target 值段的左右边界。关键洞察是数组是递增的a[i] 也是递增的因此 target a[i] - c 随着 i 的增大单调不减。所以 L 和 R 指针只会向右移动不会回头。总移动次数不超过 2n外层循环 n 次总复杂度 O(n)。#include bits/stdc.h using namespace std; long long a[200005]; int n; long long c; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n c; for (int i 0; i n; i) cin a[i]; sort(a, a n); long long ans 0; int L 0, R 0; for (int i 0; i n; i) { long long target a[i] - c; while (L n a[L] target) L; if (R L) R L; while (R n a[R] target) R; ans R - L; } if (c 0) ans - n; cout ans \n; return 0; }这里最容易写错的就是if (R L) R L;这一句。为什么需要因为 target 可能突然跳过好几种值。举个例子数组是 [1, 5, 10]c 很大导致 target 从 2 直接跳到 6。上一轮 target2 时L 指向 5 的位置R 也停在第一个大于 2 的位置也就是 5 的位置。这一轮 target6L 会向右移动到 10 的位置此时 R 还停留在 5 的位置比 L 小。如果不把 R 拉回来R-L就是负数答案直接错乱。所以双指针看起来简单实际写出来要小心这种指针关系。2.4 哈希表计数不排序也能做但要小心遍历方向如果不想排序也可以用哈希表。先用 unordered_map 统计每个值出现的次数然后遍历哈希表里的每个值 v把它当作 A那么需要的 B 就是 v-c答案累加 cnt[v] 乘以 cnt[v-c]。#include bits/stdc.h using namespace std; int n; long long c; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n c; unordered_maplong long, long long cnt; for (int i 0; i n; i) { long long x; cin x; cnt[x]; } long long ans 0; if (c 0) { for (auto p : cnt) { long long k p.second; ans k * (k - 1); } } else { for (auto p : cnt) { long long v p.first; auto it cnt.find(v - c); if (it ! cnt.end()) { ans p.second * it-second; } } } cout ans \n; return 0; }为什么遍历哈希表时不用除以 2因为这里遍历的是 A 的值每个 A 值对应同一批 B 值顺序是固定的。假设 c2数组里 3 出现了 2 次1 出现了 3 次那么遍历到 v3 时会累加 2×36 个数对遍历到 v1 时会去找 -1找不到不会反向再算一次。正因为数对要求 A 是前一个数哈希解法天然避免重复非常优雅。不过哈希解法在洛谷上不一定比二分快unordered_map 的常数有时候很大极端数据下还可能被卡。我个人的建议是想稳妥 AC用排序加二分想在 Python 里少写代码用 Counter只有特别在意常数时才上双指针。3. C0 这个边界所有解法都躲不掉3.1 同一个位置不能既当 A 又当 BC0 时题目变成统计 AB 的数对也就是找数组里值相等但位置不同的两个数。表面上看更简单了但对写代码的人来说这是个陷阱。先看最简单的场景数组 [1, 1, 1]C0。正确数对应该是多少三个位置任意选两个不同的位置一个当前面的 A一个当后面的 B所以每个无序组合有 2 种方向总数是 3×26。如果用公式表示就是某个值 v 出现 k 次时贡献 k×(k-1)而不是 k×k。多出来的 k 就是你拿同一个位置既当 A 又当 B 的“自我配对”。极端情况下这个数字可以非常大。200000 个相同的数C0答案是 200000×199999≈4×10^10。这个结果早就超过 int 范围了所以答案变量必须用 long long。这也是为什么我在代码里把所有参与计数的变量都声明成 long long宁可多占 8 字节也不能让结果溢出。3.2 二分和双指针为什么也要特判二分和双指针的写法里对每个 A 位置统计的是“整个数组中等于 target 的个数”。当 c 不等于 0 时target 不等于 a[i]这个统计结果天然不包含当前位置完全正确。但当 c0 时target 等于 a[i]当前 A 这个位置也被算进“等于 target 的个数”里了。每个位置都多算了一次自己总共多算了 n 次。所以最简单的处理不是去循环里判断跳过而是最后统一减掉 nif (c 0) ans - n;一小行代码解决所有麻烦。你可以试着自己推一下如果数组是 [1,1,1,3,3]C0。二分法对每位置累加统计1 出现 3 次三个 1 的位置各贡献 3共 9两个 3 的位置各贡献 2共 4总 13。减去 n5得到 8。真实答案是 cnt[1]×(cnt[1]-1)3×26加上 cnt[3]×(cnt[3]-1)2×12总共 8。完全一致。哈希解法在 c0 时用的是另一套分支直接写 k×(k-1)不需要最后减 n。两种思路都能处理但一定要记得这个坑真的存在。我知道很多人刷这道题时测试数据全是 c0就觉得无所谓结果某个隐藏测试点里 c 恰好为 0直接 WA。别问我是怎么知道的问就是我亲眼见过一排排红色提交记录。4. 完整代码与逐行拆解4.1 C 二分版上面已经贴过二分版代码我再把它拆开讲几个容易被忽视的细节。long long a[200005];数组开成 long long是为了和 target 的计算保持一致。a[i] - c里如果 c 比较大结果可能是负数用 int 虽然也能存但一旦数值边界比较紧容易出现类型转换上的意外。直接全用 long long 最省心。ios::sync_with_stdio(false); cin.tie(nullptr);这两行是给 cin、cout 提速的。算法竞赛里很多 TLE 不是算法问题而是输入输出慢了。200000 个整数用默认的 cin 读某些评测机上会明显变慢加上这两行保险很多。注意关闭同步之后不要再混用 scanf 和 cin否则输入顺序会乱。二分部分lower_bound和upper_bound返回的是迭代器减掉数组首地址a才能得到下标。左闭右开区间的长度R-L就是等于 target 的元素个数。如果 target 比数组最小值还小lower_bound 返回 begin()R 也等于 L区间长度为 0结果 0非常自然。4.2 C 双指针版双指针版的完整代码上节已经给出这里只强调一个工程习惯不要一上来就写双指针。双指针的常数确实更小但它比二分容易写错尤其是 R 和 L 的单调关系。我的做法是先用二分版本把题目 AC如果之后发现有性能瓶颈或者题目要求的时间极限卡得很死再换双指针优化。这样能保证正确性优先不至于在调试指针关系上浪费时间。另外双指针中R的更新是从max(R, L)开始的我用的写法是if (R L) R L;如果你直接把 R 重置成 L 也可以因为 R 本来就不小于 L只有可能出现 R 落后于 L 的情况。这个 if 的存在就是为了处理 target 跳变。4.3 Python 版两种写法Python 刷洛谷这道题最简洁的是用 Counter 哈希法import sys from collections import Counter def main(): data sys.stdin.read().split() n int(data[0]) c int(data[1]) a list(map(int, data[2:2 n])) cnt Counter(a) if c 0: print(sum(k * (k - 1) for k in cnt.values())) else: print(sum(cnt[v] * cnt.get(v - c, 0) for v in cnt)) if __name__ __main__: main()如果想用二分Python 需要导入 bisect 模块import sys from bisect import bisect_left, bisect_right def main(): data sys.stdin.read().split() n int(data[0]) c int(data[1]) a list(map(int, data[2:2 n])) a.sort() ans 0 for x in a: t x - c ans bisect_right(a, t) - bisect_left(a, t) if c 0: ans - n print(ans) if __name__ __main__: main()两种我都实测过。Counter 写法代码量小但哈希表的开销在数据量大时会让 Python 跑得比较吃力。bisect 写法是纯 Python 的二分常数也不小但胜在逻辑清晰。如果是在洛谷上提交 Python建议数据量大时优先考虑 bisect 版本或者干脆用 PyPy 跑 Counter 版本效果通常可以接受。4.4 用对拍验证暴力 随机数据把坑提前揪出来写完代码别急着交用对拍验证是最稳的。特别是这道题有 C0 的坑手算几组样例根本想不全面。我建议准备三个文件gen.py 生成随机小数据brute.py 用暴力 O(n²) 算标准答案fast.py 放你要测试的优化算法。随机生成时把数据范围故意调小但让 C 包含 0让重复值经常出现这样能最大概率踩中边界。gen.pyimport random n random.randint(1, 10) c random.randint(0, 10) # 故意包含 0 print(n, c) print( .join(str(random.randint(0, 20)) for _ in range(n)))brute.pyn, c map(int, input().split()) a list(map(int, input().split())) ans 0 for i in range(n): for j in range(n): if a[i] - a[j] c: ans 1 print(ans)然后写一个循环脚本跑几百次for i in $(seq 1 500); do python3 gen.py data.txt python3 brute.py data.txt out_brute.txt python3 fast.py data.txt out_fast.txt if ! diff -q out_brute.txt out_fast.txt /dev/null; then echo WA on test $i cat data.txt break fi done一旦某个数据点两边输出不一致把 data.txt 打出来你就能精确复现出错场景。我用这招抓到过很多“以为写对了其实边界漏了”的问题。对拍这个方法强烈建议每个人都养成习惯尤其是刷这种边界条件多的题。5. 从 A-BC 到 ABC这类配对统计题的通法5.1 换成 ABC双指针思路会怎么变P1102 的套路核心是“枚举一个数统计另一个数出现次数”。这个思路稍加变形就变成另一类经典题求无序数组中有多少对 ij 满足 a[i]a[j]C。如果还是用哈希那逻辑几乎不变遍历数组时维护一个 map对每个当前元素 x查找 C-x 在之前出现过几次累加答案再把 x 的出现次数加一。如果改用排序双指针思路就完全不一样了。因为两个数相加等于 C一个在左一个在右所以可以用左右双指针从两端往中间走。左指针指向数组开头右指针指向数组末尾根据 a[l]a[r] 与 C 的大小关系决定移动哪边。这和 A-BC 的同向双指针不同因为“差”具有方向性而“和”是对称的。5.2 从“数对”到“区间子数组”的延伸P1102 本身考的是值配对但它的统计思想可以延伸到区间问题。比如给定数组统计有多少对下标 (i,j) 满足 ij 且 a[j]-a[i]k这其实就是把数对限制成“后面的数减前面的数”排序之后的反转版本。另一个常见变式是“统计和为定值的子数组个数”通常用前缀和加哈希表一次遍历解决。表面上看和 P1102 没什么关系但底层逻辑都是把问题的某个量转成可快速查询的形式再借助哈希或排序把 O(n²) 降到 O(n) 或 O(n log n)。理解了这一层刷题时就不必每个题都从零开始想了。5.3 我对这道题的理解和使用场景以我自己的刷题习惯来说P1102 这样的题很适合拿来当“算法思维热身”。它不涉及复杂数据结构也没有高深的数学但恰恰能把“枚举位置”和“枚举值”的区别讲透。每次看到“统计满足某种关系的数对”的题目我第一反应永远是能不能先把数组排序把配对关系转化成可以在有序序列上快速查询的问题。如果实在想再深入一步建议把哈希法、二分法、双指针法都各写一遍并且尝试在 C0 时互相验证。写完之后你会明显感觉到三种方法本质是在同一道题上用自己的方式回答同一个问题“数组里某个值到底出现了几次”。把这个问题的答案搞清楚P1102 就真正吃透了。