NC24118. [USACO 2016 Dec S]Cities and States
描述
输入描述
The first line of input contains N (1≤N≤200,000), the number of cities on the map.
The next N lines each contain two strings: the name of a city (a string of at least 2 and at most 10 uppercase letters), and its two-letter state code (a string of 2 uppercase letters). Note that the state code may be something like ZQ, which is not an actual USA state. Multiple cities with the same name can exist, but they will be in different states.
输出描述
Please output the number of special pairs of cities.
示例1
输入:
6 MIAMI FL DALLAS TX FLINT MI CLEMSON SC BOSTON MA ORLANDO FL
输出:
1
C++14(g++5.4) 解法, 执行用时: 96ms, 内存消耗: 4092K, 提交时间: 2020-10-18 17:03:26
#include<bits/stdc++.h>
using namespace std;
int city[676][676], n, x, y, ans;//x表示城市前两个字母的26进制下的数，y是省份的。数相等则对应的省的两个字母和城市的前两个字母就相等。
int main() {
string a, b;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a>>b;
x = (a[0] - 'A') * 26 + a[1] - 'A';//不减的话数据太大，数组开不了那么大（map的优势）
y = (b[0] - 'A') * 26 + b[1] - 'A';
if (x != y) {//x==y的话如果要配对的话只会配到自己省。题目说了不在同一省，所以要排除。
city[x][y]++;
ans += city[y][x];
}
}
cout<<ans;
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 101ms, 内存消耗: 5068K, 提交时间: 2020-10-20 15:01:55
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n;
int f[N][N];
int main()
{
int ans=0;
cin>>n;
for(int i=1;i<=n;i++)
{
string x,y;
cin>>x>>y;
int a=(x[0]-'A')*31+(x[1]-'A');
int b=(y[0]-'A')*31+(y[1]-'A');
if(a!=b)
{
ans+=f[b][a];
f[a][b]+=1;
}
}
cout<<ans<<"\n";
return 0;
}