洛谷P3405[USACO16DEC]Cities and States S题解--zhengjun

一道哈希题。

因为只有两个关键字，直接用进制哈希。

然后存到一个数组里面，每次边更新答案边哈希

代码

#include<cstdio> using namespace std; int n; char a[100],b[100]; int get1(int i){//对城市开头的哈希 return (((a[0]-'A')*26+a[1]-'A')*26+b[0]-'A')*26+b[1]-'A'; } int get2(int i){//对洲代码开头的哈希 return (((b[0]-'A')*26+b[1]-'A')*26+a[0]-'A')*26+a[1]-'A'; } int f[500000]; int main(){ scanf("%d",&n); long long ans=0; for(int i=1;i<=n;i++){ scanf("%s%s",a,b); if(get1(i)!=get2(i)){ ans+=f[get2(i)];//要先更新答案,因为如果自己可以和自己对上,那么就不行了 f[get1(i)]++; } } printf("%lld",ans); return 0; }