Cities and States S--Map二维映射（C++完整代码）

[USACO16DEC] Cities and States S

题目描述

Farmer John 有若干头奶牛。为了训练奶牛们的智力，Farmer John 在谷仓的墙上放了一张美国地图。地图上表明了每个城市及其所在州的代码（前两位大写字母）。

由于奶牛在谷仓里花了很多时间看这张地图，他们开始注意到一些奇怪的关系。例如，FLINT 的前两个字母就是 MIAMI 所在的 FL 州，MIAMI 的前两个字母则是 FLINT 所在的 MI 州。

确切地说，对于两个城市，它们的前两个字母互为对方所在州的名称。我们称两个城市是一个一对「特殊」的城市，如果他们具有上面的特性，并且来自不同的州。对于总共 N 座城市，奶牛想知道有多少对「特殊」的城市存在。请帮助他们解决这个有趣的地理难题！

输入格式

输入共 N + 1 行。第一行一个正整数 N，表示地图上的城市的个数。接下来 N 行，每行两个字符串，分别表示一个城市的名称（2 ∼ 10 个大写字母）和所在州的代码（2 个大写字母）。同一个州内不会有两个同名的城市。

输出格式

输出共一行一个整数，代表特殊的城市对数。

样例

输入

1
2
3

6 MIAMI FL DALLAS TX FLINT MI CLEMSON SC BOSTON MA ORLANDO FL

1

提示

数据规模与约定：对于 100% 的数据，1 ≤ N ≤ 2 × 10^5，城市名称长度不超过 10。

解题思路

先把多个字母的 a 只取前两个字母，只有当前缀和州名不同的时候才处理。

st[a + b]++; 将城市前缀 a 和州名 b 组合起来作为键，记录或更新该组合出现的次数。
ans += st[b + a]; 检查是否有反向组合 b + a 已经存在，若存在则将其计数加到 ans 中。

代码如下：

// C++ 代码示例
#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    int N;
    cin >> N;
    unordered_map<string, int> st;
    int ans = 0;

    for (int i = 0; i < N; i++) {
        string city, state;
        cin >> city >> state;
        string prefix = city.substr(0, 2);
        st[prefix + state]++;
        ans += st[state + prefix];
    }

    cout << ans << endl;
    return 0;
}