P3405 [USACO16DEC] Cities and States S题解

题目

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

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

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

输入输出格式

输入格式

输入共N+1行。

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

输出格式

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

输入输出样例

输入样例

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

输出样例

1

解析1

此题目是把州和城市的前两位分别提取出来hash，然后存到map里。

注意州和城市的前两位相同时要加上特判

#include<iostream>
#include<map>
using namespace std;
map<int,int> m[100005];
int n,ans;
string s,t;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s>>t;
		int a=s[0]*26+s[1],b=t[0]*26+t[1];
		ans+=m[b][a];//将满足条件的也就是相应位置相反的加上
		if(a==b){
			ans-=m[b][a];
		}
		m[a][b]++;
	}
	cout<<ans<<endl;
	return 0;
}

解析2

#include<iostream>
#include<vector>
#define mod 233333
using namespace std;
int n;
char a[12],b[12];
long long ans;
vector<pair<int,int> >linker[mod+2];
int gethash(char a[],char b[]){
	return (a[0]-'A')+(a[1]-'A')*26+(b[0]-'A')*26*26+(b[1]-'A')*26*26*26;
}
void insert(int x){
	for(int i=0;i<linker[x%mod].size();i++){
		if(linker[x%mod][i].first==x){
			linker[x%mod][i].second++;
			break;
		}
	}
	linker[x%mod].push_back(pair<int,int>(x,1));
}
int find(int x){
	for(int i=0;i<linker[x%mod].size();i++){
		if(linker[x%mod][i].first==x){
			return linker[x%mod][i].second;
		}
	}
	return 0;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a>>b;
		a[2]=0;
		if(a[0]!=b[0]||a[1]!=b[1]){
			ans+=find(gethash(b,a));
		}
		insert(gethash(a,b));
	}
	cout<<ans<<endl;
	return 0;
}