《洛谷深入浅出基础篇》——P3405 citis and state ——哈希表

上链接：P3405 [USACO16DEC] Cities and States S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P3405

上题干：

题目描述

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

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

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

输入格式

输入共 N+1 行。

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

输出格式

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

输入输出样例

输入 #1复制

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

输出 #1复制

1

说明/提示

数据规模与约定

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

 这道题其中思路很简单，我们只要把每一个城市的名称的前两个字符，以及它的代号，分别存储在结构体里面，然后再遍历一遍找出所有的特殊字符就可以了。

但是，

有个问题，在我们进行上面的操作，会发现复杂度是O（n^2)的，显然无法通过本题。

所以我们必须减少无效的遍历次数。

那这样的话，我们就必须给所有的数据定义某个性质，并且使得每对特殊城市之间都满足这个性质，从而进行精确查找。

也就是说，我们只要给每个数据定义某个性质，然后只需要遍历一次，每次查询这个性质是否在之前出现过，如果出现过，第二次出现的时候，答案就++，说明多了一对，这样的特殊城市。

那么怎么定义这个性质才能只让特殊城市之间相同，

我们可以观察到，一对特殊城市，MI FA ————FA MI

只要把其中一个反过来，那么这两个标记就相同了。我们可以利用哈希表

给每个数据都定义一个独一无二的哈希值，这个哈希值就是我们所说的性质。

然后只要把代号和城市名字的前俩个字符反过来查询就可以了；

上代码：

using namespace std;
const int N = 2e5 + 10;
const int base = 27;
#define mod 1007
typedef long long LL;
int ans;
bool times = 1;
struct city {string city, id;
};
city a[N];int fn[mod][mod];int main()
{int n;cin >> n;int ans = 0;for (int i = 1; i <= n; i++){int hash1 = 0, hash2 = 0;cin >> a[i].city >> a[i].id;string t = a[i].city.substr(0, 2);for(int j=0;j<t.size();j++)hash1 = (hash1*base+a[i].city[j]) % mod;for (int j = 0; j < a[i].id.size(); j++)hash2 = (hash2 * base + a[i].id[j]) % mod;if (hash1 != hash2){fn[hash1][hash2]++;ans += fn[hash2][hash1];}}cout << ans;
}