Map

· · 个人记录

MAP

目录

  1. 什么是 map
  2. map 的用法
  3. map 应用
  4. map 再应用
  5. map 水题

1. 什么是 map

map 中的键值对是 key-value 的形式，比如：每个身份证号对应一个人名（反过来不成立），其中，身份证号就是 key，人名便是 value，是单项的关系，可以与 hash 作类比。

2. map 的用法

头文件

需使用头文件：

#include<map>

定义

map 的定义格式如下：

map<key,value>m;

即定义了一个下标 key 类型，存储着 value 类型的map m。

调用

直接调用m[key]，会返回 key 所对应的 value。

遍历

代码如下：

map<key,value>::iterator i;
for(i=m.begin();i!=m.end;i++)
{
}

此时调用变为i->second。

3. map 应用

题目描述

每个人都有一个电话号码（例如XXX的电话为10086），现在给定 n 个人的名字和电话号码，以及 q 次询问，问你XXX的电话是多少。

样例输入

3
xiaoZ 11111111111
xiaoA 12222222222
xiaoPig 11451419198
1
xiaoPig

样例输出

11451419198

数据范围

### 正解 定义map：`map<string,long long>m;`。 每一次输入名字和电话，直接写成`m[name]=phonenumber`。 最后询问时直接调用便可。 ## 4. map 再应用 ### 题目 [题目传送门](https://www.luogu.com.cn/problem/CF637B) ### 正解 看着很恐怖，其实水的很。 前面出现，再后面出现，其实前面的没用。 queue 不支持在中间删除插入，且循环复杂度为 $O(n)$。 考虑从后往前推。 越靠后面出现，输出也会越早。 那么推的时候，只要后面没出现，输出便可以。 AC code： ```cpp #include<bits/stdc++.h> using namespace std; map<string,bool>m; string a[200001]; signed main() { int n; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=n;i>=1;i--) { if(m[a[i]]==1) continue; else cout<<a[i]<<endl; m[a[i]]=1; } return 0; } ``` ## 5. map 水题 0. [【模板】字符串哈希](https://www.luogu.com.cn/problem/P3370)（因为是哈希的模板，所以是第 $0$ 个） 1. [贪婪的送礼者](https://www.luogu.com.cn/problem/P1201) 2. [密文搜索](https://www.luogu.com.cn/problem/P8630)