P3405 [USACO16DEC] Cities and States S-Toy模板网

这篇具有很好参考价值的文章主要介绍了P3405 [USACO16DEC] Cities and States S。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

每日一题Day7

题目描述

Farmer John 有若干头奶牛。为了训练奶牛们的智力，Farmer John 在谷仓的墙上放了一张美国地图。地图上表明了每个城市及其所在州的代码（前两位大写字母）。

由于奶牛在谷仓里花了很多时间看这张地图，他们开始注意到一些奇怪的关系。例如，FLINT 的前两个字母就是 MIAMI 所在的 FL 州，MIAMI 的前两个字母则是 FLINT 所在的 MI 州。
确切地说，对于两个城市，它们的前两个字母互为对方所在州的名称。

我们称两个城市是一个一对「特殊」的城市，如果他们具有上面的特性，并且来自不同的州。对于总共 �N 座城市，奶牛想知道有多少对「特殊」的城市存在。请帮助他们解决这个有趣的地理难题！

输入格式

输入共 �+1N+1 行。

第一行一个正整数 �N，表示地图上的城市的个数。
接下来 �N 行，每行两个字符串，分别表示一个城市的名称（2∼102∼10 个大写字母）和所在州的代码（22 个大写字母）。同一个州内不会有两个同名的城市。

输出格式

输出共一行一个整数，代表特殊的城市对数。

输入输出样例

输入 #1复制
6
MIAMI FL
DALLAS TX
FLINT MI
CLEMSON SC
BOSTON MA
ORLANDO FL
输出 #1复制
1
说明/提示

数据规模与约定

对于 100%100% 的数据，1≤�≤2×1051≤N≤2×105，城市名称长度不超过 1010。

因为题目中运用到STL中的map，所以先学习一下map的用法。

一、定义：

“第一个”称为关键字key，别名是first，每个关键字只能在map中出现一次。如果重复，后一个value的值会替换下一个value的值。

“第二个”称为关键字的值value，别名是second

二、例子：

例如：想要建立一个朋友数据表，保存多个“姓名-电话号码”的对应关系，并保存在某种数据结构中

P3405 [USACO16DEC] Cities and States S,每日一题加剑指offer,java,数据库,linux

//可以定义一个map对象
map<string,string> friends;

//把朋友-电话号码保存在friends中：
friends.insert("Alice","13824611111");
friends.insert("Bob","13902382222");
friends.insert("Tom","13002500333");
friends.insert("Jack","18011114444");

map以模板（泛型）方式实现，可以存储任意类型的数据，包括使用者自定义的数据类型

如：

map<int,int> mp;
map<int,String> m2;
map<String,String> m3;
map<float,int> m4;
map<double,long> m5;
map<person,int> m6;
//创建一个key为person型，value为int类型的map对象。

在map内部所有的数据都是有序的，map由一棵红黑树实现，这棵树具有对数据自动排序的功能。

红黑树的具体在下一章进行详解。

三、用法：

插入元素

map<int,String> student;

方式一：用insert函数插入pair

student.insert(pair<int,string>(0,"Zhangsan"));

查找元素

find()返回一个迭代器，指向查找的元素，找不到则返回map::end()位置（NULL）

iter = student.find(123);

练手题：P5266 【深基17.例6】学籍管理

代码：文章来源地址https://www.toymoban.com/news/detail-841936.html

#include<bits/stdc++.h>
using namespace std;
map<string,int> stu;
int n;

int main(){
	scanf("%d",&n);
	while(n--){
		int ope;
		scanf("%d",&ope);
		if(ope==1){
			string name;
			int score;
			cin>>name>>score;
			stu[name] = score;
			cout<<"OK"<<endl;
		}
		else if(ope==2){
			//查询 
			string name;
			cin>>name;
			if(!stu.count(name)){
				cout<<"Not found"<<endl;
			}
			else{
				cout<<stu[name]<<endl;
			}
			
		}
		else if(ope==3){
			string name;
			cin>>name;
			if(!stu.count(name)){
				cout<<"Not found"<<endl;
			}
			else{
				stu.erase(name);
				cout<<"Deleted successfully"<<endl;
			}
		}
		else if(ope == 4){
			cout<<stu.size()<<endl;
		}
	}
	return 0;
}

到了这里，关于P3405 [USACO16DEC] Cities and States S的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！