Luogu P3405 省市|假哈希

蒟蒻表示不会用map，于是想出这种奇特解。

考虑因为城市名只有前两位对我们有用，所以城市名可以只保留前两个字母。那么，我们可以把城市名的两个字母与州名的两个字母分别转成数字，再拼接起来

如：AAAA转换成00000000，ZZZZ转换成26262626。

显然，我们可以用数组储存转换为某一个数的个数，当我们寻找某一个城市的特殊城市对时，数组中”把州名和城市颠倒后组成的字符串所转成的数“里面的数就是答案。

贴代码

 1 //不要在意头文件
 2 #include<iostream>
 3 #include<fstream>
 4 #include<algorithm>
 5 using namespace std;
 6 long long n,ans;
 7 int co[28282828]={0};
 8 string c,p;
 9 int stos(string st)//把字符串转为数字
10 {
11   int s=0;
12   for (int i=0;i<st.size();i++)
13   {
14     s=s*100+(st[i]-65);
15   }
16   return s;
17 }
18 int main()
19 {
20   cin>>n;
21   for (int i=1;i<=n;i++)
22   {
23     cin>>c>>p;
24     c=c.substr(0,2);//城市名只保留前两位
25     int x=stos(c),y=stos(p);
26     if (co[y*10000+x]&&y!=x) ans+=co[y*10000+x];
27 //累加与前面城市的特殊城市对数
28     co[x*10000+y]++;//把拼接成的数记录下来
29   }
30   cout<<ans<<endl;
31   return 0;
32 }

[提交记录]

用时660ms, 内存11253KB