3027: 【普及-】【P3405】Cities and States S

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：3 解决：3

题目描述

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

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

输入

第一行一个正整数 lns="http://www.w3.org/1998/Math/MathML">�，表示地图上的城市的个数。
接下来 lns="http://www.w3.org/1998/Math/MathML">� 行，每行两个字符串，分别表示一个城市的名称（lns="http://www.w3.org/1998/Math/MathML">2∼10个大写字母）和所在州的代码（lns="http://www.w3.org/1998/Math/MathML">2 个大写字母）。可能出现类似 ZQ 的州代码，即并不真的是美国的一个州的代码。同一个州内不会有两个同名的城市。

输出

输出特殊的城市对数。

样例输入 复制 

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

样例输出 复制 

1

提示

#include<bits/stdc++.h>
using namespace std;
#define mod 23333
int n;
char a[12],b[12];
long long ans;
vector< pair < int,int > > linker[mod + 2];
inline int gethash(char a[],char b[]) {
	//算出两个字符串拼在一起的Hash值
	return (a[0]-'A') + (a[1] - 'A')*26 + (b[0] - 'A')*26*26 + (b[1] - 'A')*26*26*26; 
}
inline 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++; //把 x 所对应的出现次数++
	    	return;
		}
	linker[x % mod].push_back(pair <int,int> (x,1)); //新加入x这个元素,出现1次        			 
}
inline 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; //找到x的出现次数，将其返回 
	return 0; //x没有出现过，返回 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)); //查询b+a构成字符串的出现次数 
    	insert(gethash(a,b)); //在Hash表中插入a+b构成的字符串 
	}
	cout << ans << endl;
	return 0;
}



#include<bits/stdc++.h>
using namespace std;
int n,ans;
map<string,int> m;
string s,s1,s2,a[200005],b[200005];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) {
    	cin>>s>>s2;
    	s1=s.substr(0,2);
    	a[i]=s1+s2;
    	b[i]=s2+s1;
    	m[a[i]]++;
	}
	for(int i=1;i<=n;i++) {
		if(a[i]==b[i]) continue;
		ans+=m[a[i]]*m[b[i]];
		m[a[i]]=0;
	
	}
	cout<<ans;
	return 0;
}


来源/分类

提交提交记录统计露一手!