此笔记由我在学习过程中编写，不保证准确性和完整性，如有错误请指出。 另外，该笔记的分类和样式有部分很奇怪，我正在尽力处理此事情，请见谅。

  • 线性筛 & 埃氏筛

    埃氏筛（伪代码）：

    1
    2
    遍历：
        若为没被标记，则从其本身开始标记其的整数倍；

    线性筛（伪代码）:

    1
    2
    3
    4
    5
    遍历：
        1. 若为没被标记，放入质数表；
        2. 枚举质数表中的数：
            2.1 标记(枚举到的数*枚举到的质数)
            2.2 若枚举到的数为枚举到的质数的整数倍，则退出循环

  • 分治

    • 概念： 将一大任务分成两个近似的较小任务解决，最后再合并（类似递归）。若平均分后仍无法解决，则继续分。
    • 典型例子：
      1. 快速排序（伪代码）：
      1
      2
      3
      1. 先随机找一个参照值，去应为小的那边找比其大的（反之则找比其小的），并标记
      2. 将标记过的比其大的和比其小的交换
      3. 再将数组分成两半，两半分别重复所有动作，直至仅剩一个元素
      1. 归并排序（伪代码）：
      1
      2
      3
      1. 将数组分成两半，直至操作的那个数组仅剩一个元素
      2. 跳回上一步，与上一步分出的另一个数组有序地合并（若另一个数组已执行了相同步骤，即其有序。若无序，则让另一个数组执行1. ）
      3. 重复执行2. ，直至有序

  • 链表

    ：

  • 二分

    找最前面的该数代码：

    1
    2
    3
    4
    5
    6
    while (l <= r) {
    	int mid = (r - l) / 2 + l;
    	if (a_y[mid] >= a_x[i]) r = mid - 1;
    	else l = mid + 1;
    }
    注意：l为这个数

    找最后面的该数代码：

    1
    2
    3
    4
    5
    6
    while (l <= r) {
    	int mid = (r - l) / 2 + l;
    	if (a_y[mid] > a_x[i]) r = mid - 1;
    	else l = mid + 1;
    }
    注意：l为其下表+1的数

    **重点注意：**若没找到，r和l分别为其左右最接近的数

  • sizeof()

    sizeof(对象)可以求一个对象所占的字节数

  • memset()

    memset( 对象 , 要成初始化的数 , 初始化的字节数 )可以初始化一个对象的几个字节为同一个数

  • 指针

    1
    2
    3
    4
    int a;
    int *p=&a;//指针变量p存储变量a的地址
    *p//解引用：在这是表示指针变量p所存的地址的值
    int b=&a;//引用：在这是将变量b本身的地址设为变量a本身的地址（他们用同一个地址）

  • 结构体

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    struct a{
    	int x;
    	int y;
      friend bool operator<(Node a,Node b){//该结构体的朋友函数
    //“operator<”为重定义运算符“<”
    		return a.dis>b.dis;
    	}
    	//该做法可用于在优先队列中使用结构体的情况。
    }x;//可直接在这此这样定义
    a x;//也可这样定义
    &x//为该结构体第一项的地址（数组也同样）
    &x+n//为该结构体第1+n项的地址（数组也同样）
    x//该结构体的第一项（数组也同样）
    x+n//为该结构体第1+n项的地址（数组也同样）

  • const

    const是常量修饰符，被它修饰的变量在初始化后无法被修改

  • DFS（深度优先搜索）模板

1
2
3
4
5
6
7
8
9
10
void dfs( int pos ){
	判断终点
		处理数据
		返回
	枚举pos位置的所有可能情况:
		判断
		给pos位置赋值
		dfs()搜索下一个位置
	返回
}

  • BFS（广度优先搜索）模板

1
2
3
4
5
6
7
8
9
while(队列判空){
	取队头
	删队头
	标记
	枚举位置的所有可能情况{
		判断
		入队
	}
}

  • strcmp()

    strcmp(S1,S2)可以判断两个字符串（在这是S1和S2）是否一致

  • map

    概念： map以<key,value>键值对的形式存储，且map的内部自建一个红黑树，使得其可以自动排序。

    特点：

    • 第一个可以称为关键字(key)，每个关键字只能在map中出现一次；

    • 第二个可以称为该关键字的值(value)；

    • key既不能重复也不能被修改

    用处： map在做数据映射的时候能够非常简便的完成代码构建，并且保持查询高效。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <map>
#include <iostream>
using namespace std;

int main(){
	map<string,int> a; //第一个表示key数据类型，第二个表示value数据类型
    a["one"] = 1; 
    a["tow"] = 2;
    a["one"] = 3;
    //赋值时，key值作为下标，后面的数据作为对应key的value元素，在map中新添加一对数据
    //赋值时，如果key值已经存在，表示将此key值对应的value元素修改为新的数据
    cout << a["one"] << endl;
    //key值可以作为下标，直接输出对应的元素
    cout << a["three"] << endl;
    //注意：下标访问不会做下标检查，如上语句不会报错，但打印结果为空，因为下标访问会插入不存在的key，对应的value为默认值
    a.insert({"three",3}); //将指定键值对插入到map中，插入元素会自动插入到合适的位置，使整个map有序，默认是按照key从小到大排序
    a.erase("one"); //删除指定key值的键值对
    cout << a.count("three") << endl; //查询指定key值是否出现
    cout << a.empty() << endl; //判断是否为空，非空为0，空为1 
    cout << a.size() << endl; //获取map长度
    
    map<string,int>::iterator it = a.begin(); //创建一个map类型迭代器  
    for(;it!=a.end();it++){
    	cout << it->first << " " << it->second << endl;
	} //遍历并输出，因为是类结构体指针，每个键值对通过first访问key，second访问value
    return 0;
}

  • set

    概念： set里面每个元素只存有一个key，它支持高效的关键字查询操作。

    特点：

    • 储存同一类型的数据元素（这点和vector、queue等其他容器相同）

    • 每个元素的值都唯一（没有重复的元素）

    • 根据元素的值自动排列大小（有序性）

    • 无法直接修改元素

    • 高效的插入删除操作

    用处： set就是关键字的简单集合。当只是想知道一个值是否存在时，set是最有用的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <set>
#include <iostream>

using namespace std;

int main(){
	set<int> a; //定义一个集合
    int arr[5]= {0,5,13,19};
    set<int> b(arr,arr+5); //定义并初始化集合元素从数组arr中获取
    set<int>::iterator it = b.begin(); //创建一个set类型迭代器
	for(;it!=b.end();it++){
		cout << *it << endl;
	} //遍历并输出
    cout << b.empty() << endl; //判断是否为空，非空为0，空为1 
    cout << b.size() << endl; //获取集合长度
    cout << b.count(13) << endl; //统计集合中指定元素出现的次数 
    b.insert(8); //将指定元素插入到集合中，插入元素会自动插入到合适的位置，使整个集合有序
    b.erase(13);//删除指定的元素
    return 0;
}

  • 栈

1
2
3
4
5
6
7
8
9
10
#include<stack>

//栈:1、先进后出
//2、只能从一端进出，另一端封闭

push();//往栈里添加一个元素 (进栈、入栈、压栈) 
pop();//从栈顶删除一个元素 (出栈、弹栈)
top();//访问栈顶元素
empty();//判断栈是否为空，如果为空 1
size();//获取栈中元素的个数

  • 队列（所有）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<queue>//头文件
#include<deque>//双端队列头文件
using namespace std;

//队列:1、先进先出
//2、从一端进，另一端出
//进数据的一端：队尾
//出数据的一端：队首
//双端队列除外

queue<int> q;//正常队列
priority_queue<int> q;//优先队列，默认优先级从大到小，用法见栈
priority_queue<int,vector<int>,greater<int> > q;//优先级从小到大
priority_queue<int,vector<int>,less<int> > q;//优先级从大到小
deque<int> que;//双端队列

push();//从队尾添加一个元素 (入队)
push_front();//从队首添加一个元素 (入队)。（对于双端队列）
push_back();//从队尾添加一个元素 (入队)。（对于双端队列）
que[1];//下标访问（并不会检查是否越界）。（对于双端队列）
pop();//从队首删除一个元素 （）出队）。
pop_front();//删除队首元素（出队）。（对于双端队列）
pop_back();//删除队尾元素（出队）。（对于双端队列）
front();//访问队首元素。
back();//访问队尾元素。
empty();//判断栈是否为空，如果为空 1。
size();//获取栈中元素的个数。
que.clear();//清空所有元素。

  • 快读快写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
inline int read(){  //快读，用getchar()来代替输入
	int x=0;
	bool w=1;
	char ch=getchar();
	while(ch<48||ch>57){
		if(ch==45) w=0;
		ch=getchar();
	}while(ch>47&&ch<58){
		x=(x<<3)+(x<<1)+(ch^48);
		ch=getchar();
	}
	return w?x:(-x);
}

inline void write(int x){  //快写，用putchar()
	if(x<0){
		putchar(45);
		x=-x;
	}
	if(x>9) write(x/10);
	putchar(x%10+48);
}

int main(){
   int k = read(); //输入
   write(k); //输出
	return 0;
}

  • freopen()

作用： 重定向标准输入或输出

1
freopen("文件名","读或写（r或w）",重定向标准输入还是输出（stdin还是stdout）);

  • vecotor（动态数组）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<vector>
vector<int> v1;//创建一个空的动态数组
vector<int> v2(10);//创建一个空间为10的动态数组，元素默认值为0
vector<int> v3(5,3);//创建一个空间为5的动态数组，元素默认值为3
vector<int> v4(v3);//创建一个动态数组，其内容拷贝v3
int a[100] = {1,2,3,4,5,6,7,8,9,10};
vector<int> v5(a, a+5);//拷贝数组a[0]~a[4]的元素到动态数组v5中

v1.push_back(x);//在动态数组v1最后添加一个元素x
v1.pop_back();//删除动态数组v1最后一个元素
v1.front();//访问(获取)动态数组v1第一个元素
v1.back();//访问(获取)动态数组v1最后一个元素
v1.erase(x);//删除指定位置的元素，x是一个迭代器
v1.begin();//获取动态数组第一个元素的迭代器
v1.end()-1;//获取动态数组最后一个元素的迭代器
v1.size();//获取动态数组中的元素个数
v1.empty();//判空
v1.clear();//清空动态数组

  • pair

1
2
#include<utility>
pair<int,int>//pair有且只有2个元素

  • dijkstra最短路径（图）算法

    时间复杂度： O(n2)O(n^2)
    限制： 只能解决无负权、单源（单一源头）的图的问题
    特点： dis数组中的最小值一定为最短路
    tips： 堆优化版本时间复杂度更小，特点、限制一样

    伪代码：

1
2
3
4
5
6
7
8
void dj(){
	dis初始化为inf，dis[起点] 设为0
	vis初始化为0
	循环顶点次数：
		1. 循环查找dis数组中 *未被标记的* 最小值及其位置 pos
		2. 用vis标记pos点
		3. 枚举pos为起点的所有边，更新总起点到这些边的终点的dis值
}
**代码：**

1
2
3
4
5
6
7
8
9
10
11
12
void dj(){
	for(int i=0;i<=n;++i) dis[i]=1e8;
	dis[a]=0;
	for(int i=1;i<=n;++i){
		int pos=0;
		for(int j=1;j<=n;++j)
			if(!(vis[j])) pos=(dis[pos]<dis[j]?pos:j);
		vis[pos]=1;
		for(pair<int,int> x : gh[pos])
			dis[x.first]=min(dis[x.first],dis[pos]+x.second);
	}
}

  • dijkstra最短路径（图）算法（堆优化）

    时间复杂度： O((m+n)× log(n))
    限制 & 特点： 同优化前

    伪代码：

1
2
3
4
5
6
7
8
9
10
void dj(){
	dis初始化为inf，dis[起点] 设为0
	vis初始化为0，并起点入队
	循环顶点次数：
		1. 出队找最小值
		2. 如果tmp.pos被标记 continue
		3. 用vis标记pos点
		4. 枚举pos为起点的所有边，更新总起点到这些边的终点的dis值
			特别注意判断终点是否有被标记
}
**代码：**

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
struct Node{
	int pos,dis;
	friend bool operator<(Node a,Node b){
		return a.dis>b.dis;
	}
};
               
vector< pair<int,int> > gh[100005];
int n,m,a,dis[100005];
bool vis[100005];
priority_queue<Node> q;

void dj(){
	for(int i=0;i<=n;++i) dis[i]=1e9+5;
	dis[a]=0,q.push({a,0});
	while(q.size()){
		Node tmp=q.top();
		q.pop();
		if(vis[tmp.pos]) continue;
		vis[tmp.pos]=1;
		for(pair<int,int> x : gh[tmp.pos]){
			dis[x.first]=min(dis[x.first],dis[tmp.pos]+x.second);
			q.push({x.first,dis[x.first]});
		}
	}
}

  • top（拓扑排序）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
#include<stack>
#include<vector>
using namespace std;

vector<int> mp[100005], tp;

bool top( int n, int m, int* du ){
	stack<int> st;
	int cnt = 0;
	for( int i=1; i<=n; ++i ) if(du[i]==0) st.push(i);
	while( st.size() ){
		int tmp = st.top();
		tp.push_back(tmp);
		st.pop();
		for( int node : mp[tmp] ){
			if(--du[node]==0) st.push(node);
		}
		cnt++;
	}
	return cnt==n;
}

int main(){
	int n, m, du[100005]={},v1,v2;
	cin >> n >> m;
	for( int i=1; i<=m; ++i ){
		cin >> v1 >> v2;
		du[v2]++;
		mp[v1].push_back(v2);
	}
	if( top(n,m,du) )
		for( int x:tp ) cout << x << " ";
	else cout << " has cicle";
	return 0;
}

  • Floyd最短路径（图）算法

    时间复杂度： O(n3)O(n^3)
    限制： 可解决有负权、多源（多源头）的图的问题
    特征： dp数组（没错，是动态规划）中的最小值一定为最短路

    伪代码：

1
2
3
4
5
6
7
for (中转点 k) {
	for (起点 i) {
		for (终点 j) {
			dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
		}
	}
}
**代码：**

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;

int dp[105][105], n, m;

int main() {
	scanf("%d%d", &n, &m);
	memset(dp, 0x3f, sizeof(dp));//dp数组每个字节填充0x3f
	for (int i = 0; i <= n; i++) dp[i][i] = 0;//dp数组对角线（i=j）填充0
	for (int i = 1; i <= m; i++) {
		int v1, v2, w;
		scanf("%d%d%d", &v1, &v2, &w);
		//赋值并避免重边
		if (dp[v1][v2] > w) dp[v1][v2] = dp[v2][v1] = w;
	}
	//动规
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
	//输出
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) printf("%d ", dp[i][j]);
		printf("\n");
	}
	return 0;
}