每日一題Day7

題目描述

Farmer John 有若干頭奶牛。為了訓(xùn)練奶牛們的智力，F(xiàn)armer John 在谷倉的墻上放了一張美國(guó)地圖。地圖上表明了每個(gè)城市及其所在州的代碼（前兩位大寫字母）。

由于奶牛在谷倉里花了很多時(shí)間看這張地圖，他們開始注意到一些奇怪的關(guān)系。例如，F(xiàn)LINT 的前兩個(gè)字母就是 MIAMI 所在的?FL?州，MIAMI 的前兩個(gè)字母則是 FLINT 所在的?MI?州。
確切地說，對(duì)于兩個(gè)城市，它們的前兩個(gè)字母互為對(duì)方所在州的名稱。

我們稱兩個(gè)城市是一個(gè)一對(duì)「特殊」的城市，如果他們具有上面的特性，并且來自不同的州。對(duì)于總共??N?座城市，奶牛想知道有多少對(duì)「特殊」的城市存在。請(qǐng)幫助他們解決這個(gè)有趣的地理難題！

輸入格式

輸入共??+1N+1?行。

第一行一個(gè)正整數(shù)??N，表示地圖上的城市的個(gè)數(shù)。
接下來??N?行，每行兩個(gè)字符串，分別表示一個(gè)城市的名稱（2～102～10?個(gè)大寫字母）和所在州的代碼（22?個(gè)大寫字母）。同一個(gè)州內(nèi)不會(huì)有兩個(gè)同名的城市。

輸出格式

輸出共一行一個(gè)整數(shù)，代表特殊的城市對(duì)數(shù)。

輸入輸出樣例

輸入 #1復(fù)制

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

輸出 #1復(fù)制

1

說明/提示

數(shù)據(jù)規(guī)模與約定

對(duì)于?100%100%?的數(shù)據(jù)，1≤?≤2×1051≤N≤2×105，城市名稱長(zhǎng)度不超過?1010。

因?yàn)轭}目中運(yùn)用到STL中的map，所以先學(xué)習(xí)一下map的用法。

一、定義：

“第一個(gè)”稱為關(guān)鍵字key，別名是first，每個(gè)關(guān)鍵字只能在map中出現(xiàn)一次。如果重復(fù)，后一個(gè)value的值會(huì)替換下一個(gè)value的值。

“第二個(gè)”稱為關(guān)鍵字的值value，別名是second

二、例子：

例如：想要建立一個(gè)朋友數(shù)據(jù)表，保存多個(gè)“姓名-電話號(hào)碼”的對(duì)應(yīng)關(guān)系，并保存在某種數(shù)據(jù)結(jié)構(gòu)中

//可以定義一個(gè)map對(duì)象
map<string,string> friends;

//把朋友-電話號(hào)碼保存在friends中：
friends.insert("Alice","13824611111");
friends.insert("Bob","13902382222");
friends.insert("Tom","13002500333");
friends.insert("Jack","18011114444");

map以模板（泛型）方式實(shí)現(xiàn)，可以存儲(chǔ)任意類型的數(shù)據(jù)，包括使用者自定義的數(shù)據(jù)類型

如：

map<int,int> mp;
map<int,String> m2;
map<String,String> m3;
map<float,int> m4;
map<double,long> m5;
map<person,int> m6;
//創(chuàng)建一個(gè)key為person型，value為int類型的map對(duì)象。

在map內(nèi)部所有的數(shù)據(jù)都是有序的，map由一棵紅黑樹實(shí)現(xiàn)，這棵樹具有對(duì)數(shù)據(jù)自動(dòng)排序的功能。

紅黑樹的具體在下一章進(jìn)行詳解。

三、用法：

?插入元素

map<int,String> student;

方式一：用insert函數(shù)插入pair

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

?查找元素

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

iter = student.find(123);

練手題：P5266 【深基17.例6】學(xué)籍管理

代碼：文章來源地址http://www.zghlxwxcb.cn/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;
} 

到了這里，關(guān)于P3405 [USACO16DEC] Cities and States S的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！