P3405 [USACO16DEC]Cities and States S 题解（作业）

题面

题目描述

为了促进奶牛的智力发展， Farmer John 在牛棚的墙上放置了一幅很大的美国地图。在奶牛们花费 很多时间研究地图后，他们注意到一个奇特的现象。例如，有这样两个城市：弗林特(Flint)，其州代 码为 MI，和迈阿密(Miami)，州代码为 FL，他们之间存在一个特殊的关系： “弗林特”(Flint)的前两个 字母刚好是迈阿密的州代码(FL)，同时迈阿密(Miami)前两个字母也刚好是弗林特的州代码(MI)。如果 两个来自不同州的城市满足这一属性，那我们就说这两个城市是特殊的一对。奶牛们想知道有多少对这 样的城市存在。请帮助他们解决这个有趣的地理难题！

输入

第 1 行输入地图上城市的个数 N； 接下去的 N 行，每行分别输入两个字符串。第一个表示城市名称(字符串由大写英文字母组成， 最少两 个，最多不能超过 10 个)，第二个表示该城市的州代码(两个大写字母)。多个城市的名称允许相同，但 他们必须属于不同的州。

输出

输出共一行一个整数，满足条件的特殊城市对数。

样例输入

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

样例输出

1

提示

对于 20%的数据： 1≤N≤2,000； 对于 50%的数据： 1≤N≤25,000； 对于 100%的数据： 1≤N≤200,000；

来源 [USACO16DEC]Cities and States S

---

题目分析

这道题其实可以用map来做 （然而我不会） 当然也可以用二维数组。 先读取输入的两个字符串，然后选取他们各自的第一位和第二位组成一个数，然后通过判断数是否相等来判断是否符合要求。 这里还要判断城市名的第一位第二位与它的代码相同的情况。

---

code

#include<cstdio> #include<iostream> using namespace std; int n,ans,x,y,mp[2039][2039]; string a,b; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ cin>>a>>b; x=(a[0]-'A')*26+a[1]-'A';//转化为26进制数 y=(b[0]-'A')*26+b[1]-'A'; if(x!=y){//当城市名的第一位第二位与它的代码不同时便可以运算 mp[x][y]++; ans+=mp[y][x]; } //反之则不能 } printf("%d",ans); return 0; }