【题目来源】
洛谷：[P3405 USACO16DEC] Cities and States S - 洛谷
【题目描述】
Farmer John 有若干头奶牛。为了训练奶牛们的智力，Farmer John 在谷仓的墙上放了一张美国地图。地图上表明了每个城市及其所在州的代码（前两位大写字母）。
由于奶牛在谷仓里花了很多时间看这张地图，他们开始注意到一些奇怪的关系。例如，FLINT 的前两个字母就是 MIAMI 所在的 FL 州，MIAMI 的前两个字母则是 FLINT 所在的 MI 州。
确切地说，对于两个城市，它们的前两个字母互为对方所在州的名称。
我们称两个城市是一个一对「特殊」的城市，如果他们具有上面的特性，并且来自不同的州。对于总共 \(N\) 座城市，奶牛想知道有多少对「特殊」的城市存在。请帮助他们解决这个有趣的地理难题！
【输入】
输入共 \(N + 1\) 行。
第一行一个正整数 \(N\)，表示地图上的城市的个数。
接下来 \(N\) 行，每行两个字符串，分别表示一个城市的名称（\(2 \sim 10\) 个大写字母）和所在州的代码（\(2\) 个大写字母）。同一个州内不会有两个同名的城市。
【输出】
输出共一行一个整数，代表特殊的城市对数。
【输入样例】
6
MIAMI FL
DALLAS TX
FLINT MI
CLEMSON SC
BOSTON MA
ORLANDO FL
【输出样例】
1
【解题思路】
【算法标签】
《洛谷 P3405 Cities and States》 #USACO# #2016#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
int n, ans=0;
string s, s1, s2, a[200005], b[200005];
map<string, int> m;
int main()
{cin >> n; // 输入nfor (int i=1; i<=n; i++) { // 遍历n对字符串cin >> s >> s2; // 输入城市和州s1 = s.substr(0, 2); // 城市取前2个字符a[i] = s1+s2; // 拼接成a[i]和b[i]b[i] = s2+s1;m[a[i]]++; // 统计a[i]的个数}for (int i=1; i<=n; i++) { // 所以所有字符串对if (a[i]==b[i]) continue; // 因为同一个州不会有两个同名的城市，所以a[i]不能等于b[i]ans += m[a[i]]*m[b[i]]; // 用a[i]的个数乘以b[i]的个数m[a[i]] = 0; // 乘完一次后，后面再遇到a[i]，不再重复计算}cout << ans << endl;return 0;
}
#include <bits/stdc++.h>
using namespace std;int n; // 输入的关系对数
int ans; // 统计的互相关注对数
int x, y; // 临时变量，存储用户ID的哈希值
int a[700][700]; // 邻接矩阵，记录关注关系
string s, c; // 临时存储输入的用户名/*** 将2字母用户名转换为哈希值* @param s 2字母的用户名* @return 对应的哈希值(0-675)*/
int myhash(string s)
{int code = 0;for (int i = 0; i < 2; i++){code = code * 26 + (s[i] - 'A'); // 26进制转换}return code;
}int main()
{// 输入关系对数cin >> n;// 处理每对关系for (int i = 0; i < n; i++) {cin >> c >> s;// 计算两个用户的哈希IDx = myhash(c);y = myhash(s);// 如果是自关注则跳过if (x == y) {continue;}// 记录x关注y的关系a[x][y]++;// 如果之前y已经关注过x，则形成互相关注ans += a[y][x];}// 输出互相关注的总对数cout << ans;return 0;
}
【运行结果】
6
MIAMI FL
DALLAS TX
FLINT MI
CLEMSON SC
BOSTON MA
ORLANDO FL
1