蓝桥杯国赛题解析：哈希表巧解生日相遇计数问题

1. 项目概述与问题拆解最近在带学生备赛蓝桥杯正好刷到一道2025年国赛A组的题目叫“生日相遇问题”。这道题挺有意思的它不像传统的动态规划或者图论题那样有固定的套路更像是一道披着数学外衣的模拟题考察的是对问题本质的理解和将数学模型转化为代码的能力。很多同学一看到“生日”、“概率”、“相遇”这些词再一看是国赛A组的题心里可能就有点发怵觉得是不是要用到很高深的概率论知识。其实不然这道题的核心思路非常直接关键在于如何高效地模拟和计算。简单来说题目描述了一个场景有n个人每个人的生日是某个月份的第几天比如3月15日。我们定义两个人“生日相遇”并不是指他们生日在同一天而是指他们生日的月份和日期之和相等。例如3月15日31518和5月13日51318就是相遇的。题目会给出这n个人的生日问有多少对人是生日相遇的。看到这里你可能已经想到了最朴素的解法双重循环遍历所有人计算每两个人的月份日期之和如果相等则计数。对于n最大可能到10^5的数据范围O(n²)的复杂度显然是无法接受的必然会超时。所以这道题的难点和精髓就在于如何优化这个“找相等和”的过程。我们需要一种能够快速统计相同“和”出现次数的方法这正是哈希表在C里通常是std::map或std::unordered_map大显身手的地方。接下来我就带你一步步拆解这道题从理解题意到写出AC代码并分享一些在信奥和蓝桥杯比赛中处理此类计数问题的通用技巧和避坑指南。2. 核心思路与算法设计2.1 问题转化与数学模型建立首先我们要把模糊的自然语言描述转化为清晰的数学和编程模型。题目输入是n个生日每个生日由月份m和日期d组成。我们关心的核心属性是key m d即月份与日期的和。那么“生日相遇”的条件对于两个人i和j就等价于m_i d_i m_j d_j。我们的目标是统计所有满足i j的人对(i, j)的数量。这里i j是为了避免重复计数(i, j) 和 (j, i) 被视为同一对。2.2 从暴力法到高效算法的跃迁最直接的暴力法伪代码如下long long count 0; for (int i 0; i n; i) { for (int j i 1; j n; j) { if (month[i] day[i] month[j] day[j]) { count; } } }时间复杂度是O(n²)。当n10^5时循环次数大约是5e9在竞赛的时限内通常是1秒是绝对不可能完成的。我们需要优化。观察发现我们并不关心具体是哪两个人只关心有多少对人的key相同。因此我们可以先进行一次遍历用一个数据结构来统计每个key值出现了多少次。假设某个key值比如18出现了k次。那么这k个人之间两两都可以组成一对“生日相遇”的组合。组合的数量是C(k, 2) k * (k - 1) / 2。所以整个算法流程就清晰了读入n个人的生日。遍历每个人计算key m d并用一个哈希表如mapint, int记录每个key出现的次数。map[key]。遍历哈希表对于每个出现次数cnt大于1的key计算cnt * (cnt - 1) / 2并累加到总答案中。输出总答案。这个算法的时间复杂度是O(n log n)如果使用std::map或平均O(n)如果使用std::unordered_map空间复杂度是O(n)完全能够处理10^5的数据量。2.3 数据结构选型map vs unordered_map这里有一个值得讨论的细节选择std::map还是std::unordered_mapstd::map基于红黑树实现键值自动排序查找、插入、删除操作的时间复杂度稳定在O(log n)。std::unordered_map基于哈希表实现平均情况下的查找、插入、删除时间复杂度是O(1)最坏情况哈希冲突严重是O(n)。在竞赛中对于int这类简单的键std::unordered_map通常更快。但是它需要处理哈希函数和可能的冲突。std::map虽然慢一点但稳定性好且键是有序的虽然本题不要求。实操心得在蓝桥杯等竞赛中如果对性能有极致要求且键的范围可控用unordered_map。如果求稳或者需要有序遍历用map。对于本题n10^5两者的差距可能不大但unordered_map通常会更优。一个更保险的做法是使用map因为它的稳定性足以通过本题且避免了哈希表可能带来的意料之外的性能波动或实现细节问题。这也是很多选手在比赛时的选择。另外key的范围是多少月份m是1~12日期d最多31题目虽未明确说遵循日历但按常理所以key的范围是2到43。这个范围非常小这意味着我们甚至可以不使用哈希表而直接使用一个大小为50的数组来计数速度会更快代码也更简单。这是本题的一个关键优化点2.4 答案的数据类型与溢出问题这是本题最大的一个“坑”。n最大为10^5。考虑最极端的情况所有人的key都相同。那么需要计算的对数是C(100000, 2) 100000 * 99999 / 2。 这个值大约是5e950亿。而C中int类型的最大值大约是21亿2.1e9。如果使用int来存储最终答案会导致溢出得到错误的结果。因此必须使用long long类型64位整数来存储答案和中间计算结果。这是一个非常经典的竞赛陷阱旨在考察选手对数据范围的敏感度。3. 代码实现与逐行解析基于以上分析我们给出两种实现方案一种是使用数组计数推荐最快最稳另一种是使用map更通用适用于key范围未知的情况。3.1 方案一数组计数法最优由于key m d的范围在2~43之间保守估计可以开到45或50我们可以直接用一个大小为50的int数组cnt来统计。#include iostream using namespace std; int main() { int n; cin n; int cnt[50] {0}; // 初始化所有元素为0索引范围0-49我们用到2-43 for (int i 0; i n; i) { int m, d; cin m d; int key m d; cnt[key]; // 对应的key计数加1 } long long ans 0; // 关键使用long long for (int key 2; key 43; key) { // 遍历所有可能的key long long c cnt[key]; if (c 1) { ans c * (c - 1) / 2; // 组合数公式 } } cout ans endl; return 0; }代码解析与注意事项int cnt[50] {0};声明并初始化计数数组。{0}会将数组所有元素初始化为0。这是良好习惯避免使用未初始化的内存。int key m d;计算每个人的生日和。cnt[key];对对应的和进行计数。这里隐含了一个假设输入的m和d是合法的使得key不会超过数组边界。根据题目描述这个假设是合理的。在更严谨的代码中可以加一句if (key 0 key 50)的判断但本题中不需要。long long ans 0;这是重中之重。必须用long long来保存答案。ans c * (c - 1) / 2;这里有一个细节。c是intc-1也是int它们相乘的结果可能超过int范围虽然本题中c最大10^5乘积约1e10已超int然后再赋值给long long的ans。在计算过程中c * (c - 1)会先以int类型进行计算此时就会发生溢出得到一个错误的结果然后再转换为long long。这是错误的正确写法应该是ans (long long)c * (c - 1) / 2;或者ans 1LL * c * (c - 1) / 2;。这样保证了乘法运算是在long long类型下进行的避免了中间溢出。避坑技巧在涉及大整数计算的竞赛题中养成习惯在可能溢出的乘法或加法前显式地将第一个操作数转换为long long如(long long)a * b或者使用1LL * a * b来提升整个表达式到long long类型。3.2 方案二map实现法通用如果key的范围未知或者很大我们就需要使用map。#include iostream #include map using namespace std; int main() { int n; cin n; mapint, int countMap; for (int i 0; i n; i) { int m, d; cin m d; int key m d; countMap[key]; // map会自动初始化不存在的key的value为0 } long long ans 0; // 使用迭代器遍历map也可以使用C11的范围for循环: for (auto it : countMap) for (mapint, int::iterator it countMap.begin(); it ! countMap.end(); it) { long long c it-second; // it-first是key, it-second是计数cnt if (c 1) { ans c * (c - 1) / 2; // 同样要注意类型转换 // 更安全的写法 ans (long long)c * (c - 1) / 2; } } cout ans endl; return 0; }两种方案的对比特性数组计数法map实现法时间复杂度O(n K)K为key范围(约50)O(n log n)空间复杂度O(K)固定很小O(n)与输入规模相关优点速度极快代码简单无哈希冲突问题通用性强不依赖key的范围缺点依赖key的范围已知且较小速度稍慢需要处理红黑树开销适用场景本题最佳选择key范围小且固定key范围大或未知的通用计数问题对于本题毫无疑问应该选择数组计数法。它不仅效率高而且代码更简洁出错的概率更低。4. 测试用例与边界情况分析写完代码不能盲目提交必须自己设计测试用例进行验证。以下是一些重要的测试点4.1 常规测试用例用例1基础功能输入 5 1 1 1 1 2 1 1 2 3 1key值2, 2, 3, 3, 4。key2出现2次 - 贡献 1对key3出现2次 - 贡献 1对key4出现1次 - 贡献 0对 总对数 1 1 2。 程序应输出2。用例2无人相遇输入 3 1 1 2 2 3 3key值2, 4, 6。各不相同。 程序应输出0。用例3全部相遇极端情况输入 4 1 1 1 1 1 1 1 1key值2, 2, 2, 2。出现4次。 组合数C(4,2) 6。 程序应输出6。4.2 边界与压力测试用例4最大数据量测试验证效率和溢出输入 100000 // 这里需要生成10万个数据。可以全部相同也可以随机。 // 例如全部为 (1,1)则key2出现10万次。 // 答案应为 C(100000, 2) 100000*99999/2 4999950000这个测试用于验证时间复杂度程序能否在1秒内运行完毕。数组法毫无压力map法在大部分评测机上也应能通过。溢出问题答案4999950000远大于int最大值。如果ans或中间计算用了int结果会错误。必须输出正确的4999950000。用例5key的边界值输入 2 12 31 1 1key值43, 2。测试数组是否够大我们开了50足够。4.3 常见错误自查表在调试时可以对照下表检查错误现象可能原因解决方法答案比预期小很多对于大数据使用int存储答案ans导致溢出将ans改为long long类型答案部分正确部分错误计算组合数时c*(c-1)/2发生中间溢出改为(long long)c * (c-1) / 2程序运行超时TLE使用了O(n²)的双重循环暴力法改用哈希表或数组计数法数组越界导致运行时错误key的计算超出数组声明范围如md49确保数组大小足够本题开到50安全或使用map输出为0计数数组cnt未初始化里面是随机值声明时初始化为零int cnt[50] {0};5. 竞赛技巧与思维延伸5.1 如何快速识别此类问题“生日相遇问题”代表了一类非常常见的竞赛题型“求满足某种条件的配对数量”。其核心特征是需要统计所有(i, j)且i j的组合。一旦看到这种要求并且朴素解法是O(n²)时就要立刻想到使用哈希表或数组将O(n²)降为O(n)的优化思路。通用步骤是定义“键”key。在这个问题里键是md。在其他问题里键可能是字符串、一个元组、或者一个经过转换的数值。一次遍历用哈希表统计每个“键”出现的次数。第二次遍历哈希表对于每个出现次数cnt如果配对条件是在相同键的内部两两配对则贡献为C(cnt, 2)如果是其他条件则套用相应的计算公式。注意答案的数据类型防止溢出。5.2 从本题到更复杂问题的演变本题是这类问题中最简单的一种。我们可以思考一些变种来加深理解变种1三元组相遇。问有多少组三人他们的md之和相等。那么对于出现cnt次的key贡献就是C(cnt, 3)。计算时更要小心溢出可能需要使用long long甚至高精度。变种2差为定值。定义“相遇”为两人md的差值为某个固定值K。那么就不能简单统计相同key了。我们可以遍历每个人计算key然后查询keyK或key-K出现的次数。这依然可以用哈希表在O(n)内完成。变种3多维键。如果“相遇”条件更复杂比如需要月份也相同那么键就变成了一个二元组(m, md)。在C中可以用mappairint, int, int来统计。5.3 关于输入输出的效率在蓝桥杯等竞赛中当输入数据量非常大比如本题的10万时C默认的cin/cout可能会比C的scanf/printf慢一些因为cin/cout需要与C的输入输出流同步并且默认绑定在一起。一个常用的优化方法是在main函数开头加上ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);ios::sync_with_stdio(false)用于解除C标准流与C标准流的同步关闭后不能混用cin/cout和scanf/printf。cin.tie(0)和cout.tie(0)用于解除cin和cout的绑定可以进一步提升输入输出速度尤其是在需要交替进行大量输入输出的场景。对于本题数据量10万即使不使用这行优化cin/cout也完全能胜任。但养成在竞赛代码开头加上这几行的习惯是一个好的实践。5.4 调试与验证在比赛中写完代码后不要急于提交。应该静态检查通读代码检查变量类型特别是long long、数组大小、循环边界、初始化。样例测试使用题目给出的样例和自编的小样例进行测试确保逻辑正确。边界测试思考极端情况n1, n最大答案最大等并模拟运行。输出中间结果如果对逻辑不确定可以在本地调试时输出中间变量如cnt数组的内容帮助理解程序行为。这道“生日相遇问题”很好地体现了竞赛编程中“化繁为简”和“空间换时间”的思想。它不追求高深的算法而是考察选手将实际问题抽象、转化并利用基础数据结构高效解决的能力。掌握这类问题的解法对于应对信奥和蓝桥杯中的大量模拟、计数类题目有着举一反三的效果。下次再遇到“求对数”、“统计配对”这类关键词希望你能够立刻联想到今天的哈希表计数法。