[USACO16DEC] Cities and States S

题意

每座城市给出城市名和两字母州代码。若城市 A 的前两个字母等于城市 B 的州代码，反过来也成立，并且两城不在同一州，则它们构成特殊城市对。求无序对数量。

思路

把一座城市压缩成二元组 (城市名前缀, 州代码)。

假设当前二元组是 (prefix,state)，能和它配对的历史二元组只能是 (state,prefix)。因此顺序扫描城市时：

把已经出现的二元组放进计数器 seen；
当前答案增加 seen[state,prefix]；
再把 seen[prefix,state] 加一。

这样每个无序对只会在第二座城市出现时统计一次。若 prefix==state，两座匹配城市会来自同一州，不符合题意，必须跳过。

Python 知识

Counter 是“键到出现次数”的字典，访问不存在的键会得到 0，省去初始化判断。
元组可以直接作为字典键，seen[prefix, state] 等价于 seen[(prefix,state)]。
输入保留为 bytes，city[:2] 同样可以切出前两个 ASCII 字节，无需解码。
zip(data[1::2], data[2::2]) 把扁平 token 两两配成城市名和州代码。
/home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：Counter 和字典计数模式。
/home/rainboy/mycode/hugo-blog/content/program_language/python/itertools_recipes.md：流式处理与配对思路。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21import sys
from collections import Counter


def main():
    data = sys.stdin.buffer.read().split()
    seen = Counter()
    answer = 0

    for city, state in zip(data[1::2], data[2::2]):
        prefix = city[:2]
        if prefix == state:
            continue
        answer += seen[state, prefix]
        seen[prefix, state] += 1

    print(answer)


if __name__ == "__main__":
    main()

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38/**
 * P3405 [USACO16DEC] Cities and States S
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

#include <bits/stdc++.h>
using namespace std;

// 2 个大写字母 → 0~675 的编码
int enc(const char *s) {
    return (s[0] - 'A') * 26 + (s[1] - 'A');
}

// cnt[城市前缀][州编码] = 出现次数
int cnt[676][676];
int n;
long long ans;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        char city[15], state[5];
        scanf("%s%s", city, state);
        int prefix = enc(city);
        int st = enc(state);
        if (prefix != st) {
            // 当前城市可以和之前所有 (state == prefix 且 city_prefix == st) 的城市配对
            ans += cnt[st][prefix];
            ++cnt[prefix][st];
        }
    }
    printf("%lld\n", ans);
    return 0;
}

复杂度

每座城市只做常数次哈希表操作，期望时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。

总结

不要枚举城市对。先找出一个对象的“唯一互补键”，再用计数器查询它此前出现了多少次，就能把二次枚举改成一次扫描。

[USACO16DEC] Cities and States S

目录

题意

思路

Python 知识

代码

复杂度

总结