2021-5-22-PM学习笔记

  1. 红黑树
    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;
}



  1. 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)转移

上一篇:IIS服务部署页面


下一篇:Ajax请求中的async:false/true的作用