企业官网建设流程全解析

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]，计数加一。这样写逻辑完全正确，样例也能过，但提交后就是超时。

我们来算一笔具体账。N=200000，双层循环大约执行 N*(N-1)/2 次比较，约 2 * 10^10 次。每次比较是两个字符串的逐字符比较，每个字符串虽然只有 2 个字符，但加在一起运算量依旧非常可观。即使按每次比较只需要 5 纳秒计算，也要 100 秒以上，而一般 OJ 的时限只有 1 到 2 秒。哪怕是 N=50000，也有大约 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。比如 city="AB", state="CA"，那么 key 就是 "ABCA"。反过来，当我们需要查询“反转记录 (CA, AB)”时，就拼出 key="CAAB"，然后在哈希表里查这个 key 的计数。

value 部分记录的是该 key 出现的次数。为什么需要计数而不是只存是否存在？因为可能出现完全相同的两条记录。虽然两条完全相同的记录，比如 (AB, CA) 和 (AB, CA)，它们之间并不能直接配对（城市 AB 不等于州 CA），但如果之前有多条记录都是同样的反转形态，比如有 3 条 (CA, AB)，那当前这条 (AB, CA) 就可以分别和这 3 条配对，贡献 3 个配对数。所以 value 必须是可累加的次数，而不是布尔值。

用 C++ 的unordered_map<string, 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 个字符，那么城市名的可能取值一共 2626=676 种，州名同样也是 676 种。一条记录的有效 key 组合最多有 676676=456976 种。在 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_map<string, 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 factor

unordered_map在数据量大的时候，如果初始桶数量设置太小，会频繁触发 rehash，也就是重新分配桶数组并重新计算所有元素的哈希值。这个过程虽然不会出错，但会带来额外开销。对于 N=200000，最坏情况下不同 key 的数量可能接近 456976，所以建议提前预留足够的桶空间。

我们可以这样写：

unordered_map<string, 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，这种做法直观且简单。但还有另一种常见写法：用pair<string, string>作为 key。

map<pair<string, string>, int> cnt; // 或者 unordered_map<pair<string, 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都是 "ABAB"，cnt["ABAB"]是 1，ans 会变成 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_map<string, int>都能顺利 AC。但如果你遇到的是极端的反哈希测试数据，或者你想把这段代码用在更严谨的题目环境中，就要考虑自定义哈希函数的问题。

C++ 的unordered_map默认哈希函数对字符串的处理是std::hash<string>，通常基于 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_map<int, int>替代unordered_map<string, 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”的影子。用一套思路串起来，会比单纯刷题效率高很多。