P3405 Cities and States S 复盘：用哈希表实现反向配对计数

P3405 Cities and States S 复盘一道把“反向配对”讲明白的哈希表好题P3405 Cities and States S 复盘一道把“反向配对”讲明白的哈希表好题这段时间重新刷 USACO 2016 年 12 月的赛季题P3405 Cities and States S 是 Silver 组里非常典型的一道字符串配对计数题。它不考高深算法也不考复杂数据结构核心就是一个反向哈希计数但很多人第一次做都会交出一版 O(N^2) 的双层循环然后盯着超时发呆。我身边好几个刚接触竞赛的朋友刷到这道题时卡点出奇一致题意读懂了样例也能手推但就是想不到要用哈希表去“反向查找”之前出现过的记录。这篇文章就把这道题的完整思路、代码实现、边界条件和踩坑经验都写清楚。无论你是刚开始刷 USACO 的选手还是想在 OJ 上补题找感觉看完之后应该都能顺畅 AC并且以后遇到类似“配对计数”的题脑子里会多一根弦。1. 项目描述与题意拆解1.1 输入输出与数据范围先说清楚先看一眼题面给的信息输入第一行是整数 N代表接下来有 N 条记录每条记录包含两个长度为 2 的大写英文字符串第一个是城市名的前两个字母第二个是州缩写。N 的范围是 1 到 200000。你要统计的是有多少对不同的记录 (i, j)满足第 i 条记录的城市名等于第 j 条记录的州名同时第 i 条记录的州名等于第 j 条记录的城市名。这里有个非常容易漏掉的细节输入给出的“城市名”本身可能是不完整的它只是真实城市名的前两个字母。比如城市全名是 Flint那输入就是 FL。但这不影响解题因为我们只需要按题面给的两个长度为 2 的字符串做匹配。输出的答案是一个整数表示满足条件的无序对数量。注意题目说的是“数对”并且 i 和 j 不能相同也就是说同一条记录不能和自己配对。这个数据范围很关键。N 最大 200000意味着如果写两层 for 循环最坏情况下要比较约 200000 * 199999 / 2 次也就是接近 200 亿次比较。这个量级在任何评测环境下都不可能通过哪怕编译器优化拉满也扛不住。所以看到 200000 就应该立刻意识到这道题要过的不是逻辑关而是复杂度关。1.2 样例推演题目的配对规则到底在说什么原题样例我就不照抄了直接用一个更直观的小例子来说明配对规则。假设输入下面 4 条记录AB CA CA AB AB AB AA AA逐条看第 1 条城市 AB州 CA。第 2 条城市 CA州 AB。这两条就满足条件第 1 条的城市 AB 等于第 2 条的州 AB同时第 1 条的州 CA 等于第 2 条的城市 CA。所以这是一对。第 3 条城市 AB州 AB。它城市名和州名一样能不能和别的记录配对要找一条州是 AB、城市是 AB 的记录目前没有。它自己也不能和自己配对所以第 3 条单独出现时不会产生贡献。第 4 条城市 AA州 AA。情况和第 3 条类似城市名等于州名但并没有另一条城市 AA、州 AA 的记录所以也不产生配对。最终答案是 1。这个推演能帮我们准确理解“城市名等于对方州名州名等于对方城市名”是什么意思。本质上配对的两条记录互为“反转”如果一条记录的 (city, state) 是 (X, Y)那另一条必须是 (Y, X)。“反转”这个词很关键它直接指向了后续的解题思路。1.3 为什么直接双层循环会超时复杂度推演很多人第一次看到这种题第一反应就是暴力枚举。外层遍历 i内层遍历 j然后判断 city[i] state[j] state[i] city[j]计数加一。这样写逻辑完全正确样例也能过但提交后就是超时。我们来算一笔具体账。N200000双层循环大约执行 N*(N-1)/2 次比较约 2 * 10^10 次。每次比较是两个字符串的逐字符比较每个字符串虽然只有 2 个字符但加在一起运算量依旧非常可观。即使按每次比较只需要 5 纳秒计算也要 100 秒以上而一般 OJ 的时限只有 1 到 2 秒。哪怕是 N50000也有大约 12.5 亿次比较依然会超时。所以这道题从一开始就不应该在“如何更快地比较”上面动脑筋而应该换一个角度能不能一次遍历就把所有配对数统计完这也就是接下来要说的核心思路用哈希表记录历史信息对每一条新记录做“反向查找”。2. 核心解题思路拆解2.1 从枚举配对到反查历史记录既然不能两两枚举那就得想办法只遍历一遍输入同时完成计数。我们换个顺序来想问题。假设我们按顺序一条一条处理记录。当处理到第 k 条记录时它只需要关心“之前出现过的记录里面有多少条恰好和自己是反转关系”。如果之前出现过一条 (CA, AB)而现在读入的是 (AB, CA)那它们就配成一对。所以核心变成如何快速知道之前有没有出现过某组“反转记录”这显然是哈希表的强项。我们可以用一个哈希表key 存记录本身value 存这个记录出现过的次数。每读入一条新记录 (X, Y)就在哈希表里查一下 (Y, X) 的计数这个计数就是能和当前记录配对的历史记录数量把答案累加进去。然后再把当前记录 (X, Y) 自己的计数加一。这里有一个微妙但很重要的点为什么要先查询、后插入因为如果先插入再查询当前记录可能会和它自己匹配导致多计数。比如当前记录是 (CA, AB)先插入后再查 (AB, CA)当前记录并不等于 (AB, CA)所以其实也没有错但先查后插的习惯可以保持逻辑清晰避免其他自匹配的边界问题。后面我在自环部分会再展开。2.2 用哈希表记录状态key 和 value 分别存什么哈希表的 key 需要唯一标识一条记录。由于城市名和州名都固定是 2 个字符最简单的方式就是把 city 和 state 拼成一个 4 个字符的字符串作为 key。比如 cityAB, stateCA那么 key 就是 ABCA。反过来当我们需要查询“反转记录 (CA, AB)”时就拼出 keyCAAB然后在哈希表里查这个 key 的计数。value 部分记录的是该 key 出现的次数。为什么需要计数而不是只存是否存在因为可能出现完全相同的两条记录。虽然两条完全相同的记录比如 (AB, CA) 和 (AB, CA)它们之间并不能直接配对城市 AB 不等于州 CA但如果之前有多条记录都是同样的反转形态比如有 3 条 (CA, AB)那当前这条 (AB, CA) 就可以分别和这 3 条配对贡献 3 个配对数。所以 value 必须是可累加的次数而不是布尔值。用 C 的unordered_mapstring, int就能非常自然地实现这个逻辑。key 是拼接后的字符串value 是出现次数。代码非常短但背后的设计思路值得展开讲清楚。2.3 自环问题城市名和州名相同的特殊情况城市名和州名相同的记录比如 (AB, AB)是一个很容易让人困惑的点。它看起来满足“城市 AB 等于州 AB州 AB 等于城市 AB”那它是不是能自己和自己配对题目明确要求 i 和 j 是不同记录所以同一条记录自己不能和自己配对。但在哈希表的处理逻辑里这个问题其实被自动规避了。原因是当我们处理一条 (AB, AB) 时我们先查询哈希表里 key 为 ABAB 的计数这个计数里包含的是之前所有 (AB, AB) 记录的数量不包含当前这条。如果之前有 2 条 (AB, AB)当前这条就会贡献 2 个配对数这正好对应当前记录分别和那 2 条旧记录各配成一对。但要注意如果先插入再查询就会出问题。先把自己插入到哈希表再查 ABAB会把当前这条也算进去导致答案多了 1。所以“先查询、后插入”不是个人偏好而是必须遵守的顺序。我在实现时也把这两行代码的顺序当作固定模式记了下来。那城市名和州名相同、但没有任何其他相同记录的情况呢比如只有一条 (AB, AB)查询时 ABAB 的计数是 0答案不会增加。虽然它看起来可以进行“自我匹配”但因为不允许和自己配对所以这种孤立的自环记录不应该产生贡献。2.4 答案数量的上界分析明明不大为什么还要用 long long有人可能会想N 是 200000答案最大也就 200000 左右吧实际上并不是。仔细想想城市名只有 2 个字符那么城市名的可能取值一共 2626676 种州名同样也是 676 种。一条记录的有效 key 组合最多有 676676456976 种。在 200000 条记录里合法配对关系可以反复出现。如果某一种配对关系对应的两条记录各出现 100000 次那这种配对就能贡献 100000 * 100000 10^10 个配对数。这已经超出 int 的范围了。所以答案变量必须用long long。虽然题目实际数据可能给不到这么极端但刷题习惯一定是能开大就开大避免因为数据边界问题导致溢出。这个上界分析也反过来验证了前面的结论暴力枚举为什么不行因为合法答案本身就可能达到百亿级别暴力枚举和答案规模的差距是数量级的差距。3. 完整实现与细节优化3.1 基础版本不到 30 行代码拿下先给出一版最直接的实现语言用 C。核心逻辑就是之前说的拼 key、查反转 key、计数累加、插入自身。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; unordered_mapstring, int cnt; long long ans 0; for (int i 0; i n; i) { string city, state; cin city state; city city.substr(0, 2); state state.substr(0, 2); string cur city state; string rev state city; ans cnt[rev]; cnt[cur]; } cout ans \n; return 0; }解释几个细节之所以要substr(0, 2)是因为输入给出的城市名可能超过 2 个字符但题面要求只取前两个字母。如果在读入时不截断后面拼接的 key 长度就会不一致配对判断也会出错。cnt[rev]这种写法在 key 不存在时会自动插入一个值为 0 的项所以ans cnt[rev]是安全的。无序映射的operator[]对不存在的 key 会执行默认构造int 默认构造为 0。先ans cnt[rev]再cnt[cur]顺序不能反。原因在自环部分已经讲过。这里用到的核心思想值得再强调一遍我们不是在“找未来的配对”而是在“利用历史记录积累配对”。每一条新记录产生的新配对只能发生在它和所有旧记录之间所以现在把旧记录的计数拿出来用然后把新记录自己也变成“旧记录”供后续使用。3.2 性能取舍unordered_map 的 reserve 和 load factorunordered_map在数据量大的时候如果初始桶数量设置太小会频繁触发 rehash也就是重新分配桶数组并重新计算所有元素的哈希值。这个过程虽然不会出错但会带来额外开销。对于 N200000最坏情况下不同 key 的数量可能接近 456976所以建议提前预留足够的桶空间。我们可以这样写unordered_mapstring, int cnt; cnt.reserve(1 20); cnt.max_load_factor(0.7);reserve(1 20)的意思是为大约 1048576 个元素预留空间而max_load_factor(0.7)设置当装载因子超过 0.7 时就扩容。经过这样的设置后整个程序运行期间的 rehash 次数会非常少哈希表的查询和插入基本稳定在 O(1)。实测下来加了这两行之后在大数据下的运行时间会比默认状态快不少。对于 200000 条输入这种规模直接跑基本都稳定在 0.1 秒以内。那为什么不直接用map呢map底层是红黑树插入和查询都是 O(log M)M 是当前 key 的种类数。当 M 接近 450000 时log M 大约为 19也就是说每条记录要多做十几倍的比较运算。对于 200000 条记录来说map和unordered_map都能过但unordered_map显然更符合“哈希表解决配对计数”的题目设计意图。如果遇到时间限制更紧的题目map就可能被卡掉。3.3 两种变体写法pair 作 key 与字符串拼接 key上面的代码把 city 和 state 拼成一个 4 字符的字符串作为 key这种做法直观且简单。但还有另一种常见写法用pairstring, string作为 key。mappairstring, string, int cnt; // 或者 unordered_mappairstring, string, int, PairHash cnt;用pair作为 key 时逻辑上更清晰不需要额外拼接尤其当城市名不是固定 2 个字符时会更通用。但unordered_map原生不支持pair作为 key需要自己写哈希函数。而map自带pair的比较逻辑可以直接用只是复杂度会多一个 log。对于这道题来说字符串拼接的方案更简洁性能也更好。因为字符串拼接只是两次 2 字符拷贝开销可以忽略不计而且去掉了自定义哈希函数的麻烦。但我建议把pair写法学到手因为之后会遇到不少题目key 本身就不是字符串而是两个整数、三个整数之类那时候自定义哈希函数就成为必备技能。3.4 读入性能关同步流与文件 IO 的坑竞赛环境下的读入优化是老生常谈但这里还是要点一下。在 C 里cin默认会和 C 标准输入输出同步导致读入速度变慢。程序开头加上ios::sync_with_stdio(false); cin.tie(nullptr);可以解除这种同步让cin的效率接近scanf。遇到大数据输入这两行有时候能直接把时间从超时边缘拉回来。另外需要注意的是USACO 原题在官网刷题时需要用文件输入输出就是读citystate.in、写citystate.out这种形式。但在洛谷等 OJ 上题目已经帮你处理好了文件重定向你只需要用标准输入输出即可。如果是从 USACO 官网下载数据本地测试记得在 main 函数开头加上freopen(citystate.in, r, stdin); freopen(citystate.out, w, stdout);这个坑我踩过一次本地样例跑得好好的提交到 oj 却一直 WA最后发现是忘记加文件读写读进来的是空数据。所以先看清楚题目来源和评测方式再决定要不要加文件重定向。4. 常见问题与避坑实录4.1 为什么第一份代码 TLE 而不是 WA很多人在本地测试样例时暴力双层循环瞬间出结果因为样例 N 太小了。提交上去后反馈是 Time Limit Exceeded 而不是 Wrong Answer这意味着你的逻辑是对的但复杂度不行。一个很实用的自查方法是比赛或刷题时一旦觉得某道题可以用双层循环解决先看 N 的范围。N 超过 5000就要警惕N 超过 50000基本可以确定 O(N^2) 会超时N 达到 200000那必须想一个 O(N) 或 O(N log N) 的方案。这道题就是在逼你往哈希表方向思考。我之前认识一个朋友他写的是双层循环加一点剪枝先按城市名分组再在组内比较。这样虽然组变小了但最坏情况所有城市名都一样下复杂度依旧是 O(N^2)照样超时。这说明剪枝能优化常数但没法改变数量级。遇到这种问题正确思路不是优化暴力而是换算法。4.2 重复输入相同城市州名会不会算错这可能是很多人第一次提交后答案偏小或偏大的原因。先说偏大的情况。如果你在查询之前就把当前记录插入哈希表当城市名和州名相同时就会把自己也算进配对里答案会多 1。举个例子只有一条记录 (AB, AB)。正确结果应该是 0因为不能和自己配对。但如果你先cnt[cur]再ans cnt[rev]此时cur和rev都是 ABABcnt[ABAB]是 1ans 会变成 1这就错了。如果有多条相同记录呢比如 3 条 (AB, AB)。正确的配对方式每一条新记录都能和之前已经出现过的 2 条配对所以贡献依次是 0、1、2总数 3。这和组合数 C(3,2)3 一致。但如果先插入再查询贡献会变成 1、2、3总数 6明显翻倍。所以“先查询、后插入”这个顺序可以说就是这道题最重要的一个细节。我在代码注释里专门标了一行“query first, then insert”提醒自己不要手滑。4.3 unordered_map 被卡怎么办从哈希冲突到自定义哈希绝大部分情况下直接用unordered_mapstring, int都能顺利 AC。但如果你遇到的是极端的反哈希测试数据或者你想把这段代码用在更严谨的题目环境中就要考虑自定义哈希函数的问题。C 的unordered_map默认哈希函数对字符串的处理是std::hashstring通常基于 FNV-1a 或类似算法。理论上如果攻击者知道哈希函数可以构造大量相同哈希值的字符串导致哈希表退化成链表查询复杂度变成 O(M)。这在算法竞赛的 Hack 环节里是真实存在的手段。题目里的字符串只有 2 个字符范围有限其实不太可能构造出灾难性的碰撞但为了练习可以自己写一个简单的哈希函数。由于 key 是 4 个字符我们甚至可以把它当作一个 4 位 26 进制数来算这样既快又不容易碰撞int encode(const string s) { return (s[0] - A) * 26 * 26 * 26 (s[1] - A) * 26 * 26 (s[2] - A) * 26 (s[3] - A); }然后用unordered_mapint, int替代unordered_mapstring, int。这样 key 是整数哈希成本更低而且不会有字符串哈希碰撞的担忧。不过要注意如果直接访问下标需要预先确认 key 的范围是否适合开数组。因为 26^4 456976这个数量级完全可以开一个大小为 456976 的 int 数组效率比哈希表还高。这也是这道题的一个进阶优化方案。4.4 自查清单提交前把这三处看一遍我整理了一个非常简单但有效的自查清单每次提交这道题之前按顺序扫一眼第一ans是不是long long。如果是int在大数据下很可能溢出。第二查询和插入的顺序是不是先查后插。顺序反了自环和重复记录都会算错。第三城市名读进来之后有没有截断前 2 个字符。如果忘记截断所有 key 的长度都不对答案基本不会对。这三个问题解决了这道题基本就稳过。我自己第一次提交时栽在第二个问题上被样例迷惑了很久因为简单的样例里先插后查也能碰巧得到正确答案。后来构造了一组自环数据才发现问题。5. 补题复盘从这道题学到的三个通用技巧虽然这题本身的定位是 Silver 组入门题但复盘下来我觉得它至少有三个方面值得反复品味。第一个技巧是“配对条件变成 key 余项”的思考方式。只要题目要求找两个对象互为某种条件就可以考虑把其中一个对象保存下来让另一个对象用某种等价变换去查表。这道题里反转关系就是等价变换。很多看似需要两两枚举的问题本质上都可以通过这种方式降到线性复杂度。第二个技巧是“先查后插”的固定顺序。我相信第一次做这道题的人十个里有八个不会在意这一行代码的前后顺序。但正是这一行顺序决定了自环记录会不会被错误计入。以后但凡遇到“统计满足条件的数对”且允许对象相同但索引不同的问题我都会提醒自己检查插入和查询的顺序。第三个技巧是数据范围的敏感性。看到 200000第一反应不是“能不能两层循环”而是“答案可能有多大、能不能用线性扫描”。这个敏感度不是天生的是靠一次次超时教训换来的。如果你还在刷题初期建议在每道题读完数据范围之后先停下来估算一下大概率需要的复杂度再动手写。避免写完一版暴力后才发现要推倒重来。这题还有一个可以延伸的变体如果城市名和州名都变成长度不固定的字符串配对规则不变字符串拼接作为 key 的方法依然成立只是截断操作需要调整。如果输入的城市名不再只是前两个字母而是完整名称思路同样适用。说到底这类题的核心从来不是字符串本身而是“反转对应”这个关系能不能被高效索引。另外我个人的一个小习惯是用 Python 刷题的朋友可以直接用collections.Counter或普通字典做同样的事情代码写起来比 C 还短。Python 的字典天然是哈希表也天然支持任意可哈希对象作为 key所以思路迁移过去非常顺畅。但在大数据下要注意 Python 的运行速度200000 条记录一般没问题超过百万就要考虑性能优化了。如果你是在校学生建议做完这题后再找几道类似标签的题巩固一下比如“两数之和”“回文对”这类都能看到“值作为 key、索引或次数作为 value”的影子。用一套思路串起来会比单纯刷题效率高很多。