蓝桥杯备赛：Day3-P1102 A-B 数对

算法笔记P1102 A-B 数对 (枚举与哈希查找)1. 题目简述P1102 A-B 数对 - 洛谷给出一个长度为N NN的正整数数列和一个整数C CC求有多少个不同的数对( A , B ) (A, B)(A,B)满足A − B C A - B CA−BC。数据范围N ≤ 2 × 10 5 N \le 2 \times 10^5N≤2×105答案可能超过int范围。2. 核心代码 (C 实现)#include bits/stdc.h using namespace std; typedef long long ll; int N; ll c; ll arr[200005]; // 存储原始数列 mapll, ll cnt; // 存储每个数字出现的次数 (Key:数字, Value:次数) ll ans 0; // 最终对数必须用 long long void solve() { // 1. 读入数据并进行安全检查 if(!(cin N c)) return; // 2. 第一次遍历读入数组并统计每个数字出现的频率 for (int i 1; i N; i) { cin arr[i]; cnt[arr[i]]; // map 自动处理若不存在则初始化为0再 } // 3. 第二次遍历将每个数看作 B寻找符合条件的 A for (int i 1; i N; i) { // 变形公式A - B C A B C // 我们当前枚举的是 B (即 arr[i])我们要找 A (即 arr[i] c) // 直接从 map 中获取 A 出现的次数并累加到答案中 ans cnt[arr[i] c]; } // 4. 输出最终结果注意不要写在循环内部 cout ans endl; } int main() { // 竞赛必备优化 ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); solve(); return 0; }3. 核心考点与注意事项 核心考点公式变形将A − B C A - B CA−BC转化为A B C A B CABC。这是算法优化的前提将“寻找两个变量”转化为“固定一个变量查找另一个变量”。哈希表计数利用std::map实现O ( log ⁡ N ) O(\log N)O(logN)的查找效率。如果使用双重for循环O ( N 2 ) O(N^2)O(N2)面对2 × 10 5 2 \times 10^52×105的数据量会彻底超时。数据类型意识计数结果N NN个数如果全部相同且C 0 C0C0答案是N 2 N^2N2会爆int。Key 值输入的数字可能很大map的键必须用long long。⚠️ 注意事项Map 的副作用访问cnt[x]时如果x不存在map会自动插入一个0。在本题中由于我们只是累加次数不影响结果但在某些统计总数的场景下需谨慎。重复数字处理题目求的是“数对”数量因此必须统计频率。例如1 1 2 2找C 1 C1C1的对数答案应为 4每个 1 都能匹配两个 2。4. 易错点回顾 (My Mistakes)输出位置错误误将cout放在了遍历B BB的for循环内部导致输出了每一阶段的中间累加值而非最终结果。代码逻辑顺序最初尝试在读入的同时进行匹配。纠正这种题目最稳妥的做法是“先全部读入并统计完毕”再进行二次遍历匹配防止逻辑遗漏。