[USACO16DEC] Cities and States S
题目描述
Farmer John 有若干头奶牛。为了训练奶牛们的智力,Farmer John 在谷仓的墙上放了一张美国地图。地图上表明了每个城市及其所在州的代码(前两位大写字母)。
由于奶牛在谷仓里花了很多时间看这张地图,他们开始注意到一些奇怪的关系。例如,FLINT 的前两个字母就是 MIAMI 所在的 FL
州,MIAMI 的前两个字母则是 FLINT 所在的 MI
州。
确切地说,对于两个城市,它们的前两个字母互为对方所在州的名称。
我们称两个城市是一个一对「特殊」的城市,如果他们具有上面的特性,并且来自不同的州。对于总共 $N$ 座城市,奶牛想知道有多少对「特殊」的城市存在。请帮助他们解决这个有趣的地理难题!
输入格式
输入共 $N + 1$ 行。
第一行一个正整数 $N$,表示地图上的城市的个数。
接下来 $N$ 行,每行两个字符串,分别表示一个城市的名称($2 \sim 10$ 个大写字母)和所在州的代码($2$ 个大写字母)。同一个州内不会有两个同名的城市。
输出格式
输出共一行一个整数,代表特殊的城市对数。
样例 #1
样例输入 #1
6
MIAMI FL
DALLAS TX
FLINT MI
CLEMSON SC
BOSTON MA
ORLANDO FL
样例输出 #1
1
提示
数据规模与约定
对于 $100%$ 的数据,$1 \leq N \leq 2 \times 10 ^ 5$,城市名称长度不超过 $10$。
算法1
(字符串哈希 + map)
由题意可知
(1)一对「特殊」的城市:对于两个城市,它们的前两个字母互为对方所在州的名称
(2)同一个州内不会有两个同名的城市
整体思路
1.把州和城市的前两位分别提出来进行hash,映射到26进制的一个整数
2.对于给定的字符串(a,b),找出对应的(b,a),利用map实现
3.特判: a != b; 两个城市不能所在同一个州
欠缺的知识:map 的二维数组
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n;
map<int,int> mp [N];
string a,b;
int ans;
int main(){
cin >> n;
while(n--){
cin >> a >> b;
int A = (a[0]-'0') * 26 + (a[1] - '0');
int B = (b[0]-'0') * 26 + (b[1] - '0');
ans += mp[B][A];
if(A == B) //一个州不能有两个同名城市
{
ans -= mp[A][B];
}
mp[A][B]++;
}
cout << ans ;
return 0;
}
标签:10,两个,map,int,城市,States,mp,Cities,USACO16DEC From: https://www.cnblogs.com/ltphy-/p/18381511