做 USACO 的 Silver 组题时P3405USACO 2016 December Contest, Silver 组第二题 Cities and States S是我每次给学生讲到“哈希表计数”时一定会拉出来当例子的题。题目表面上看是一堆城市和州的配对实际上思路一转就是一个经典的反向索引计数模型。很多第一次做这题的人都会被“城市名”和“州缩写”这两个概念绕进去拿着字符串去硬比较代码写得又长又乱等你真正想清楚“我要找的到底是什么”解法其实不到二十行就能写完。这篇文章就把这道题的完整思路、代码实现、踩坑点一次性讲透不管你是刚开始刷 USACO 的选手还是准备各类算法竞赛想补一补哈希表应用的人都能从这里拿到可以直接用的东西。1. 题目到底在问什么题意拆解与“反向配对”直觉1.1 原题场景与输入形式这道题的场景比较朴素农夫约翰有 N 个城市每个城市有一个由大写字母组成的名字同时属于一个州。州的缩写固定是两个大写字母城市名字的长度至少是两个字符。输入会给你 N 行每行先是一个城市名然后是一个州缩写例如6 MIAMI FL DALLAS TX FLINT MI CLEMSON SC BOSTON MA ORLANDO FL当然实际数据里的城市名和州缩写都是英文大写长度也未必像我举的这么短但结构就是这样。题目要找的是“特殊配对”如果城市 A 名字的前两个字母恰好等于城市 B 所在州的缩写同时城市 A 所在州的缩写恰好等于城市 B 名字的前两个字母那么 A 和 B 构成一个特殊配对。注意这里强调的是两个城市之间互相“对上”不是单个城市自己满足什么条件。我第一次读这道题的时候脑子里的第一反应是“那是不是要把每两个城市都检查一遍”。但往下看一眼数据范围N 最大可以到 200000两两组合是 C(200000, 2) 的数量级也就是约 2e10 次比较这无论如何都不可能跑完。所以题目真正的考察点从一开始就很明确不能按“城市对”去枚举必须找一种方式把“配对条件”转化为“快速查找”。1.2 把文字题翻译成数学模型把题目里的条件写成数学符号会更清楚。假设城市 i 的信息是 (a_i, b_i)其中 a_i 表示城市名的前两个字母b_i 表示州缩写。那么城市 i 和城市 j 构成特殊配对就需要同时满足a_i b_j b_i a_j这个形式非常漂亮它其实是在说两个城市的“城市名缩写”和“州缩写”正好交换了位置。你只要把每个城市看成二元组 (a_i, b_i)要找的就是能够和它形成“完全反向”的另一个二元组 (b_i, a_i)。一旦意识到这一点这题就不该再被当成字符串模拟题了它本质上是一个“查找互补元素”的问题。这和我之前在《两数之和》里讲过的思路是同构的给定一堆数找两个数之和为 target只不过这里堆里的“数”变成了二元组而要查找的目标是二元组的反向。1.3 第一直觉为什么是错的很多人拿到这题会想我先存下所有城市的 (a_i, b_i)然后对每个城市 i再遍历所有城市 j判断 b_i 是不是等于 a_j 且 a_i 是不是等于 b_j。这个思路本身没有逻辑错误但复杂度是 O(N^2)在 N 达到 2e5 时只能拿到部分分数据再大一点就会超时。还有人会想我把每个城市的 state 单独统计一下再统计 city 前两位然后相乘。这种做法也不对因为题目要求的是“两个城市之间一一配对”而不是把两个独立统计结果胡乱组合。比如城市 A 的州缩写是 FL城市 B 的城市名可能是 FL但城市 B 的州缩写未必等于 A 的城市名前两位所以单纯计数相乘一定会算进去很多不满足条件的组合。正确的方向只有一个对每个城市只花 O(log N) 或 O(1) 的时间去查“有没有以及有多少个城市满足反向条件”。这就是哈希表/字典最擅长的场景。2. 核心解法用 Map 做“反向索引”2.1 关键观察四字符编码与对称性既然配对条件只涉及城市名前两个字母和州缩写那真正影响答案的就只有每个城市的这两个长度都为 2 的字符串。于是每个城市可以进一步被压缩成一个四字符信息城市名前两位 州缩写。比如城市 MIA MI真正参与判断的是MI和FL所以它的核心二元组就是 (MI,FL)。接下来注意对称性。我们要找的配对是 (MI,FL) 和 (FL,MI) 这样两个二元组。如果用字符串表示其中一个的完整 key 是MIFL另一个的完整 key 是FLMI。这两个 key 的区别只是前后两段交换了位置。于是算法就呼之欲出了我维护一个哈希表 cnt里面存的是“某种四字符 key 出现过多少次”。每读到一组城市先构造出“我要找的目标 key”把它的州缩写放在前面城市名前两位放在后面也就是state city_prefix。然后去哈希表里查这个 key 已经有多少个这些都能和当前城市构成特殊配对累加到答案里。最后再把当前城市自己的 keycity_prefix state也放进哈希表。这个“先查自己需要的再登记自己拥有的”顺序非常关键。它保证了每条合法配对只会在两个城市中后出现的那一个被统计时计入一次不会重复也不需要最后再除以 2。2.2 在线累加法和离线累加法网上能搜到的题解里还有另一种常见写法先把所有城市的 cnt 都建好然后再遍历一次每次累加cnt[state city_prefix]最后把答案除以 2。这种离线写法在大多数情况下也能过但它有一个隐患当city_prefix state时当前城市自己的 key 会和它要找的目标 key 完全相同于是cnt[state city_prefix]里包含了自身直接累加会导致答案偏大。很多题解因此会加一句if (city_prefix state) continue;把这种情况直接跳过。但是问题来了如果两个不同的城市恰好都是AB AB这种形式它们难道不满足配对条件吗从题目定义来看城市 1 的 a 是 AB城市 2 的 b 是 AB城市 1 的 b 是 AB城市 2 的 a 是 AB四个条件完全满足它们当然应该构成一个特殊配对。所以离线写法遇到这种情况要么特别处理要么会漏算。相比之下在线写法完全没有这个烦恼因为先查后插当前城市永远不会在哈希表里找到它自己。我在实际代码里强烈推荐在线写法代码更短逻辑也更安全。用文字描述在线写法就是读入城市名 city 和州名 state。令 a city 的前两个字母。令 target state aans 累加上 cnt[target]。令 cur a statecnt[cur] 加一。输出 ans。2.3 复杂度分析为什么 O(N log N) 足够使用 C 的std::map时每次插入和查询都是 O(log M)其中 M 是 map 中不同 key 的数量最多也就是 N。所以整体复杂度是 O(N log N)对 2e5 的数据量非常轻松。如果使用std::unordered_map平均情况下能把单次操作压到 O(1)整体就是 O(N)。用 Python 的dict也是同理。这里其实还有一个更夸张的优化思路因为城市名前两位和州缩写都只包含大写字母所以每种 key 都可以看作一个四位的 26 进制数。最多只有 26^4 456976 种可能这个数量级完全可以开一个定长数组来计数。这样代码不仅不需要哈希表连 map 的 log 开销都省掉了。不过那属于锦上添花的优化竞赛里用 map 已经足够稳了。3. 代码实现与逐行讲解3.1 C 实现map string我先把最推荐的在线写法贴出来然后逐段解释。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; mapstring, long long cnt; long long ans 0; for (int i 0; i n; i) { string city, state; cin city state; city city.substr(0, 2); string target state city; ans cnt[target]; string cur city state; cnt[cur]; } cout ans \n; return 0; }需要特别注意几个地方。第一city city.substr(0, 2)这一行必须做。虽然输入的城市名可能很长但参与配对判断的只有前两个字母所以提前截断能让后面的 key 始终是四个字符。第二cnt的类型是mapstring, long longvalue 用long long而不是int。原因很简单N 最大 2e5最多可以形成约 2e10 个配对已经远超 32 位整数的范围。我见过不少人在这个点上翻车输出用int结果大数据一跑就变成负数或者溢出。第三ans cnt[target]这行利用了map的operator[]特性如果 key 不存在会先插入一个值为 0 的项。所以不需要手动判断 key 是否存在。不过要注意这样会往 map 里插入很多值为 0 的无效项对内存有一些影响但考虑到 N 只有 2e5这点开销完全可以接受。如果比较在意可以换成auto it cnt.find(target); if (it ! cnt.end()) ans it-second;的写法避免不必要的插入。3.2 Python 实现字典 tupleC 选手看上面的代码很舒服Python 选手用字典也很直接。import sys from collections import defaultdict def main(): data sys.stdin.read().strip().split() if not data: return n int(data[0]) cnt defaultdict(int) ans 0 idx 1 for _ in range(n): city data[idx] state data[idx 1] idx 2 city city[:2] target state city ans cnt[target] cur city state cnt[cur] 1 print(ans) if __name__ __main__: main()Python 版本里我用了一个小技巧一次性读取所有输入然后按顺序取。这种写法比一行一行input().split()要快不少在 N 比较大的时候能明显减少 IO 开销。defaultdict(int)则是用来省掉“判断 key 是否存在”的样板代码效果和 C 的operator[]类似。还有更偏函数式风格的写法但没必要。竞赛代码追求的是“一眼能看懂逻辑、出错概率低”不是越花哨越好。3.3 数组哈希的极致优化可选如果你对性能有执念或者想锻炼一下“把 key 压缩成整数”的能力可以考虑用数组替代 map。思路是把四字符 key 当成一个 26 进制数int key(int a, int b, int c, int d) { return ((a * 26 b) * 26 c) * 26 d; }这里 a、b、c、d 分别是四个字符减掉A之后的值取值范围是 0 到 25。这样任意一个四字符大写字符串都可以唯一映射到 0 到 456975 的整数。然后开一个长度 456976 的long long数组剩下的逻辑和 map 版本完全一致。#include bits/stdc.h using namespace std; const int MAXK 26 * 26 * 26 * 26; long long cnt[MAXK]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; long long ans 0; for (int i 0; i n; i) { string city, state; cin city state; int a city[0] - A; int b city[1] - A; int c state[0] - A; int d state[1] - A; int target ((c * 26 d) * 26 a) * 26 b; ans cnt[target]; int cur ((a * 26 b) * 26 c) * 26 d; cnt[cur]; } cout ans \n; return 0; }这个版本的优点是快缺点是可读性稍微弱一点而且它只能处理“字符集固定为 26 个大写字母”的场景。万一题目改成包含小写字母或者数字数组长度就要相应扩大。平时练习我更推荐先用 map 版本把逻辑跑通等到需要卡常数再考虑数组优化。4. 实战踩坑与常见问题4.1 自配对陷阱城市名前两位等于州名很多第一次写这道题的人会下意识地感觉如果city[:2] state那么这个城市自己就满足两个条件应该把它剔除。事实上单看一个城市AB AB如果允许它和自己配对它确实满足a b且b a。但题目要求的是两个城市组成 pair自己不能和自己配对。在线写法里因为我们是先查 target 再插入 cur所以根本不需要显式处理这个情况。当前城市还没有被插入哈希表它不可能在cnt[target]里找到自己。不过如果两个不同的城市都是AB AB它们之间其实是可以配对的。在线写法天然支持这种配对第二个AB AB插入前哈希表里已经有第一个AB AB所以cnt[target]会返回 1。这就是为什么我说尽量不要用离线写法加continue去跳过自配对那样会漏掉这种特殊情况。如果你用了离线写法正确做法应该是这样先统计完所有 cnt再遍历每个城市ans cnt[state city]最后ans / 2但如果 city 前两位等于州名遍历到它时要把cnt[state city]减掉 1 再累加因为那里包含了它自己。这个细节很容易被忽略所以我还是推荐在线写法。4.2 重复城市记录与答案除以 2 的坑裁判数据里可能出现多条完全相同的记录也就是同一个城市名和同一个州出现多次。比如有三条记录都是MIA FL。对于这三条记录任意两条之间是否构成特殊配对判断一下城市 1 的 a 是 MI城市 2 的 b 是 FLMI 不等于 FL所以不构成。在线写法里第一条记录插入 keyMIFL第二条记录读入时 target 是FLMI哈希表里没有所以不会错误配对第三条同理。结果正确。但如果你写的是离线方法而且最后除以 2遇到重复记录时只要逻辑正确也没问题。问题出在那些“分别统计 city 前缀和州名次数然后用乘法算”的歪路子上那种写法在重复记录面前会错得离谱。所以这题的教训是一定要围绕“城市对”来计数不要拆开统计再组合。4.3 字符串读入和 substr 细节C 的cin city在读入普通大写字符串时没有空格问题所以很安全。但如果用getline就要小心换行符残留没有必要。Python 一次性读入所有内容再 split 是最稳的。substr(0, 2)在城市名长度为 2 时没有任何问题返回它自身长度为 1 时才有越界风险但题目保证城市名至少两个字符所以不需要额外判断。C 中如果担心城市名可能只有一位可以用city.substr(0, min(2, (int)city.size()))兜底不过这种防御性代码在本题里属于多余。4.4 答案范围与 long long这是最容易被忽略的地方。N 最大 200000 时假设数据构造得极端一点所有城市都两两配对那么答案量级是 C(200000, 2) 19999900000约 2e10。这个数已经超过 int 最大值 2147483647。所以不管是答案变量、cnt的 value还是 Python 里不必担心但 C 里必须注意都要用long long。我在测试这题时实际遇过一次本地样例全过一交上去数据一大就 WA排查半天发现是int ans溢出了。从那以后所有计数类题目的累加变量我都默认先开long long宁可浪费一点内存也不在这种地方栽跟头。5. 从这道题延伸出去USACO Silver 的思维模式5.1 这类“配对计数”题的通用套路P3405 表面上是字符串题内核却是非常经典的“查找互补元素”模型。USACO Silver 组里还有很多题都用到同一个套路把每个输入元素转化为一个 key然后用哈希表维护已经出现过的 key再在遍历过程中查询“当前元素需要的互补 key”有多少个。这种模式不只是竞赛里好用现实生活中很多场景也类似。比如你有一批订单每个订单有出发城市和目的城市你想统计有多少对订单正好是互相反向的路线那本质就是这道题。再比如在日志分析中统计“请求 A 和请求 B 成对出现”的次数也能用同样的思路。更进一步的抽象是如果每个元素可以被表示成一个二元组 (x, y)你要找的是另一个元素 (y, x)那就把 (x, y) 当成 key 存起来对每个元素查 (y, x)。如果 K 元组的反向形式更复杂也可以用 map 套 vector 或者自定义结构体做 key。核心思想永远是一样的用空间换时间把“找配对”变成“查字典”。5.2 类似的练习题推荐如果你刚做完 P3405 感觉还不够可以顺着这几个方向找同类型的题练手洛谷 P1102 A-B 数对同样是计数问题利用 map 统计每个数出现次数然后查互补关系。USACO 2017 December Silver Cities and States 系列后续虽然这题就是那场的但 USACO Silver 里还有大量和 map 使用相关的题比如 The Cow Run 之前的排序题。LeetCode 1 Two Sum经典中的经典和这道题是一模一样的思考路径只不过把字符串换成了数字。LeetCode 242 Valid Anagram 变种如果题目不要求配对而是统计一组字符串有多少对互为重排那也是先把每个字符串排序或计数后当作 key再查 map。如果把这些题放在一起对比你会发现它们都是一个模式题目描述不同底层模型相同。刷题时最好能有意识地总结这种模型而不是一道一道孤立地记。5.3 赛场上的决策什么时候用 map什么时候用数组拿这道题来收尾说一说选型问题。我实际写的时候第一反应是用unordered_mapstring, long long因为逻辑最直白代码最不容易出错。但如果追求极致性能或者评测机比较老unordered_map在某些极端情况下可能因为哈希冲突退化那就用map更稳妥。要是还想更快再用数组编码。具体怎么选我的经验是需要快速实现、保证正确性的时候用map或unordered_map这种题 N 2e5 随便跑。数据量到 1e6 级别或者时间限制特别紧张优先考虑数组/vector 哈希。字符集和 key 长度都固定且很小的时候数组是最优解否则别强行压缩容易写出错。最后说一个我自己踩过的小坑最早我写这题时把 target 和 cur 的顺序弄反了结果样例怎么都过不了。后来我在代码里加了注释明确写清楚“target 是别人要满足我的条件cur 是我拿出去给别人配对的条件”从此再也没错过。这种命名上的小心思看起来不起眼在赛场上却能帮你省下大量调试时间。
