- 红黑树
1.1 set 自带去重机制的有序集合
自带去重机制的有序集合 | set< int> a |
---|---|
插入元素 | s.insert(a) |
第一个元素(最小值) | *a.begin() |
最后一个元素(最大值) | *a.rbegin() |
删除 | s.erase(2) |
#include <bits/stdc++.h>
using namespace std;
int s[5]={1,6,8,7,7};
int main(){
set<int> a;
for(auto g:a) s.insert(a);//插入元素
cout << *a.begin() <<endl;//第一个元素(最小值)
cout << *a.rbegin() <<endl;//最后一个元素(最大值)
s.erase(2);//删除
for(auto g:s) cout << g <<" ";//输出
}
1.2 map 高级数组
可以定义其他类型下标的数组
高级数组 | map<string,string> m |
---|---|
插入一个键值对 (id 相同 相当于修改 id 不同 相当于插入 ) | m[id] = name |
询问 | m.find(id) == m.end() |
#include<bits/stdc++.h>
using namespace std;
map<string,string> m;
int main()
{
// ID to 姓名
int n; cin >> n;
for (int i = 1 ; i <= n ; i++){
string id , name;
cin >> id >> name;
// 插入一个键值对
// id 相同 相当于修改
// id 不同 相当于插入
m[id] = name;
}
// 假设我们有q次询问.每次询问一个id,问他的姓名
int q; cin >> q;
for (int i = 1 ; i <= q ; i++){
string id ; cin >> id;
if (m.find(id) == m.end()){
cout << "没有此id" << endl;
continue;
}
cout << m[id] <<endl;
}
return 0;
}
1.3 pair
组合x,y为pair类型
组合x,y | pair<int,int> |
---|---|
赋值 | make_pair(x , y) |
访问第一维度 | a.first |
访问第二维度 | a.second |
#include<bits/stdc++.h>
using namespace std;
// pair
map<pair<int,int>,int> a;
int main()
{
int q; cin >>q;
for (int i = 1 ; i <= q ; i++){
int x , y , c;
cin >> x >> y >> c;
pair<int,int> b;
b = make_pair(x , y);
a[b] += c;
}
int m; cin >> m;
for (int i = 1 ; i <= m ; i++){
int x , y; cin >> x >> y;
cout << a[make_pair(x , y)] << endl;
}
return 0;
}
- 图
2.1 存图
1)点比较少 n<=1000
二维数组(邻接矩阵)
m[n][n]; m[i][j] =c;
2)点多,边少
矢量型邻接矩阵
vector<pair<int,int>> e[10005];
e[i].first
e[i].second
#include <bits/stdc++.h>
using namespace std;
vector<int> e[10005];
vector<pair<int,int>> e[10005];
int main(){
return 0 ;
}
3.访问—遍历
3.1 DFS
3.3.1 递归
1)干什么
2)递归出口:终止
3)转移