用 Counter 统计每个数的出现次数，按 cnt[x]×cnt[x+C] 累加位置数对。
OJ: luogu
题目 ID: P1102
难度:普及-
标签:计数哈希python
创建: 2026-07-16 17:50
更新: 2026-10-07 12:15
题意
统计有多少对不同位置上的数满足
思路
把等式改写为 B 出现 cnt[B] 次，数值 B+C 出现 cnt[B+C] 次，它们能组成的有序位置数对就是两者乘积。
因此只需统计频率，再对每种 B 累加：
C 为正数，所以一对数值只会按较小值 B 统计一次。
Python 知识
collections.Counter直接把序列变成“数值到出现次数”的映射。- 访问不存在的键时，
Counter[key]返回0，无需单独判断B+C是否出现。 sum(...)配合生成器完成乘积聚合，不创建中间列表。/home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：Counter的频率统计模式。/home/rainboy/mycode/hugo-blog/content/program_language/python/generator_expression.md：生成器与sum的惰性聚合。
代码
python
import sys
from collections import Counter
data = list(map(int, sys.stdin.buffer.read().split()))
n, difference = data[:2]
counts = Counter(data[2:2 + n])
print(sum(count * counts[value + difference] for value, count in counts.items()))cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-07-27 00:00
* update_at: 2026-07-27 00:00
*/
/* P1102 A-B 数对 */
/* 排序后，对每个 a[i] 统计有多少 a[j] == a[i] + C。 */
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int n, c;
int a[MAXN]; // 输入数组
int main() {
cin >> n >> c;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
// 先排序
sort(a + 1, a + n + 1);
long long ans = 0;
// 对每个 a[i]，找 a[i] + c 的出现次数
int j = 1, k = 1;
for (int i = 1; i <= n; i++) {
// 用两个指针分别找等于 a[i]+c 的第一个和最后一个位置
while (j <= n && a[j] < a[i] + c) j++;
while (k <= n && a[k] <= a[i] + c) k++;
// a[i]+c 的出现次数 = k - j
ans += k - j;
}
cout << ans << "\n";
return 0;
}另一种写法：排序后用二分查找统计每个 B 对应的 B+C 出现次数。
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-08-01 02:00
* update_at: 2026-08-01 02:00
*/
/* P1102 A-B 数对 */
/* 排序后，对每个 a[i] 用二分查找统计 a[i]+C 的出现次数。 */
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
const long long INF = 1e18; // 哨兵值，保证 bs_find 一定能找到答案
int n;
long long c;
long long a[MAXN]; // 输入数组，排序后使用；a[n+1]=INF 作为哨兵
int mid(int l,int r) {
return (l+r) >> 1; //这是最快的写法
}
//检查pos位置的值是否符合要求
bool check(int pos,long long val){
return a[pos] >= val;
}
//bs_find = binary search find
//返回 [l,r] 中第一个满足 a[pos] >= val 的位置，找不到返回 r
int bs_find(int l,int r,long long val) {
while( l < r) {
int m = mid(l,r);
if( check(m,val)) //成立
r = m;
else //不成立,抛弃左半边
l = m+1;
}
return l ;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> c;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
// 先排序
sort(a + 1, a + n + 1);
a[n + 1] = INF; // 哨兵，使二分查找找不到目标时能返回 n+1
long long ans = 0;
// 对每个 B = a[i]，用二分找 A = a[i]+c 的个数
for (int i = 1; i <= n; i++) {
long long target = a[i] + c; // 要找的 A
// 等于 target 的元素个数 = 第一个 >= target+1 的位置 - 第一个 >= target 的位置
int left = bs_find(1, n + 1, target);
int right = bs_find(1, n + 1, target + 1);
ans += right - left;
}
cout << ans << "\n";
return 0;
}STL 写法
用 map<ll, ll> 直接记录「数值 → 出现次数」：读入时 cnt[x]++，再按键遍历每种出现过的数值 x，用 find 查 x + C 的计数，两者相乘累加进答案。数组的下标只能是连续整数位置，而本题的键是数值本身（可达 map 恰好补上这一点。和上面 main.cpp 的排序 + 双指针相比，这里不需要排序，也不用维护两个指针，代价是每次查询从均摊
注意遍历时要用 find 而不是 cnt[x + C]：operator[] 会把不存在的键插入 map，边遍历边插入会让循环失控。
对应的 cppbook 章节：map：通过键找到对应的值
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-07 01:16
* update_at: 2026-10-07 01:17
*/
/* P1102 A-B 数对 */
/* STL 写法：用 map<ll, ll> 统计每个数出现的次数，再对每个键 x 累加 cnt[x] * cnt[x + C]。 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, c;
map<ll, ll> cnt; // cnt[x] 表示数值 x 在原序列中出现的次数；数值可能很大，键用 ll
void read_input() {
cin >> n >> c;
for (ll i = 1; i <= n; i++) {
ll x;
cin >> x;
// 键 x 不存在时 operator[] 先插入默认值 0，再自增，正好完成一次计数。
cnt[x]++;
}
}
void solve() {
ll ans = 0; // 位置数对数量最多到 n^2 量级，用 ll 累加
// 按键升序遍历每一种出现过的数值，把它当作较小的那个数 B，去查 A = B + C 的计数。
for (map<ll, ll>::iterator it = cnt.begin(); it != cnt.end(); it++) {
ll value_b = it->first;
ll count_b = it->second;
// 这里必须用 find：operator[] 会把不存在的键插入 map，
// 边遍历边插入会让后面不断冒出新的键，循环失控。
map<ll, ll>::iterator it_a = cnt.find(value_b + c);
if (it_a != cnt.end()) {
// B 的每个位置和 A 的每个位置都能配对，所以两边计数相乘。
ans += count_b * it_a->second;
}
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
read_input();
solve();
return 0;
}复杂度
统计和遍历不同数值的期望时间复杂度为
总结
题目强调“不同位置”，所以不能只判断数值是否存在。频率乘积恰好把两边所有位置组合完整计入答案。