CC45.【C++ Cont】STL中的哈希表及练习
目录
1.unordered_set和unordered_multiset
2.unordered_set
3.unordered_map
4.例题:P5266 【深基17.例6】学籍管理
分析
代码
提交结果
5.练习题:P1102 A-B 数对
分析
方法1:暴力求解
方法2:哈希表或者红黑树
哈希表解法
提交结果
红黑树解法
提交结果
6.练习题:P3405 [USACO16DEC] Cities and States S
分析
一对「特殊」的城市的含义
细节处理
代码
红黑树写法
写法1和2的区别
提交结果
写法3
提交结果
哈希表写法
提交结果
1.unordered_set和unordered_multiset
对比之前在CC42.【C++ Cont】STL库的红黑树set的使用文章讲过的set,set底层用的红黑树,而unordered_set和unordered_multiset的底层用的哈希表,使用方法完全一样
set存的是有序的,unordered_set和unordered_multiset存的是无序的(unordered)
这里以unordered_set为例
2.unordered_set
参见CC42.【C++ Cont】STL库的红黑树set的使用文章,除了没有lower_bound和upper_bound接口,其余使用方法完全一样
注意使用前要先包含<unordered_set>头文件
3.unordered_map
参见CC42.【C++ Cont】STL库的红黑树set的使用文章,除了没有lower_bound和upper_bound接口,其余使用方法完全一样
注意使用前要先包含<unordered_map>头文件
4.例题:P5266 【深基17.例6】学籍管理
https://www.luogu.com.cn/problem/P5266
分析
属于正常的增删查改的问题,考察最基本的接口调用问题,对不同情况判断做出相应的操作即可
代码
#include <iostream>
#include <unordered_map>
#include <string>
#define endl "\n"
using namespace std;
int op,score,times;
string name;
unordered_map<string,int> mp;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>times;
while (times--)
{
cin>>op;
if (op==1)
{
cin>>name>>score;
if (mp.count(name))
mp[name]=score;
else
mp.insert({name,score});
cout<<"OK"<<endl;
}
else if (op==2)
{
cin>>name;
if (mp.count(name))
cout<<mp[name]<<endl;
else
cout<<"Not found"<<endl;
}
else if (op==3)
{
cin>>name;
if (mp.count(name))
{
mp.erase(name);
cout<<"Deleted successfully"<<endl;
}
else
cout<<"Not found"<<endl;
}
else//op==4
cout<<mp.size()<<endl;
}
}注:存储的方式选择unordered_map<string,int>或map<string,int>都可以,但不能用set,set只能存储单关键字
提交结果
5.练习题:P1102 A-B 数对
https://www.luogu.com.cn/problem/P1102
分析
方法1:暴力求解
将n个数用数组arr存储,使用两层循环,判断arr[i]-arr[j]是否等于c,如果等于,计数器+1,时间复杂度为,读题发现
N最大为
,显然超时,此方法不通
方法2:哈希表或者红黑树
A-B==C转换为A==B+C,C是已知的,先遍历一次数组得出B的值,再查询B+C==A中哈希表或红黑树统计的A的出现次数
注意:本题C最大可以取到,因此int不可以,使用unsigned long long(题目限定是正整数)
哈希表解法
#include <iostream>
#include <unordered_map>
using namespace std;
typedef unsigned long long ull;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
unordered_map<ull,ull> mp;
const int N=2e5+10;
ull n,c,count=0;
ull arr[N];
cin>>n>>c;
for (ull i=0;i<n;i++)
{
cin>>arr[i];
mp[arr[i]]++;
}
for (ull j=0;j<n;j++)
{
count+=mp[c+arr[j]];
}
cout<<count;
return 0;
}
提交结果
红黑树解法
只要把上方代码的unordered_map改成map就行了
#include <iostream>
#include <map>
using namespace std;
typedef unsigned long long ull;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
map<ull,ull> mp;
const int N=2e5+10;
ull n,c,count=0;
ull arr[N];
cin>>n>>c;
for (ull i=0;i<n;i++)
{
cin>>arr[i];
mp[arr[i]]++;
}
for (ull j=0;j<n;j++)
{
count+=mp[c+arr[j]];
}
cout<<count;
return 0;
}
提交结果
6.练习题:P3405 [USACO16DEC] Cities and States S
https://www.luogu.com.cn/problem/P3405
分析
一对「特殊」的城市的含义
如下图:
在存储城市和州(州可以理解为省) 的对应关系时,可以使用pair<string,string>,因为题目要求"对于两个城市，它们的前两个字母互为对方所在州的名称"则在存储时只保留城市的前两个字母(即MIAMI的MI,FLINT的FL).
细节处理
"如果他们具有上面的特性，并且来自不同的州"
即对于城市名称的前两个字符串如果和州名相同的,是不能统计的,例如
城市abc 州:ab 城市abd 州:ab 城市abc和abd都来自ab州,也符合"对于两个城市，它们的前两个字母互为对方所在州的名称"条件,但不能统计进去
代码
红黑树写法
使用红黑树map存储双关键字: map<pair<string, string>, int> mp;
注:如果要按城市和州的对应关系去做,是不能用unordered_map去做的,没有pair<?,?>对应的哈希函数!
//写法1
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;
typedef unsigned long long ull;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
vector<pair<string, string>> arr;
string tmp1, tmp2;
map<pair<string, string>, int> mp;
int n, cnt = 0;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> tmp1;
cin >> tmp2;
tmp1 = tmp1.substr(0, 2);
arr.push_back({ tmp1,tmp2 });
mp[{tmp1, tmp2}]++;
}
for (int j = 0; j < n; j++)
{
if (mp.count({ arr[j].second, arr[j].first })&&arr[j].first!=arr[j].second)
cnt += mp[{arr[j].second, arr[j].first}];
}
cout << cnt / 2;//cnt一定是偶数,必须/2才可以得到结果
return 0;
}
//写法2
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;
typedef unsigned long long ull;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
vector<pair<string, string>> arr;
string tmp1, tmp2;
map<pair<string, string>, int> mp;
int n, cnt = 0;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> tmp1;
cin >> tmp2;
tmp1 = tmp1.substr(0, 2);
if (tmp1!=tmp2)
arr.push_back({ tmp1,tmp2 });
mp[{tmp1, tmp2}]++;
}
for (int j = 0; j < n; j++)
{
if (mp.count({arr[j].second, arr[j].first}))
cnt += mp[{arr[j].second, arr[j].first}];
}
cout << cnt/2 ;
return 0;
}写法1和2的区别
写法1:一开始可以记录"城市名称的前两个字符串如果和州名相同的"情况到红黑树map,但在统计时不能计入cnt,即:
if (mp.count({ arr[j].second, arr[j].first })&&arr[j].first!=arr[j].second)写法2:或者可以这样做:一开始在录入map时不记录"城市名称的前两个字符串如果和州名相同的"情况,即
if (tmp1!=tmp2)
arr.push_back({ tmp1,tmp2 });这样之后计入cnt时的条件改成这样:
if (mp.count({ arr[j].second, arr[j].first }))推荐写法2,因为只存储了有效的输入对,减少了arr的大小,空间复杂度比较低
提交结果
写法3
可以在写法2的基础上继续优化,不使用arr数组,而且cnt不用除以2
#include <iostream>
#include <map>
#include <string>
using namespace std;
typedef unsigned long long ull;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string tmp1, tmp2;
map<pair<string, string>, int> mp;
int n, cnt = 0;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> tmp1;
cin >> tmp2;
tmp1 = tmp1.substr(0, 2);
if (tmp1==tmp2)
continue;
mp[{tmp1, tmp2}]++;
cnt+=mp[{tmp2, tmp1}];
}
cout << cnt ;
return 0;
}提交结果
哈希表写法
如果强行使用哈希表也是可以的,但不能存储城市和州的对应关系,算法如下:
第一个关键字:存储城市的前两个字母和州拼接后的字符串
第二个关键字:出现的次数
例如MIAMI FL-->存储"MIFL"字符串,其mp["MIFL"]++
#include <iostream>
#include <unordered_map>
#include <string>
#include <vector>
using namespace std;
typedef unsigned long long ull;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string tmp1, tmp2;
unordered_map<string, int> mp;
int n, cnt = 0;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> tmp1;
cin >> tmp2;
tmp1 = tmp1.substr(0, 2);
if (tmp1==tmp2)
continue;
mp[tmp1+tmp2]++;
cnt+=mp[tmp2+tmp1];
}
cout<<cnt;
return 0;
}提交结果
