题解 P3405 【[USACO16DEC]Cities and States S】

· · 题解

这篇题解主要为不太清楚map用法的同学服务，这题用数组即可。（不会map还是尽快学会，可问度娘，或者写一下线性表）

主体思路和楼下楼上的大佬一样，先读取输入的两个字符串，然后选取他们各自的第一位第二位组成一个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;
}