常用C++算法，OIer必备

算法模板

目录

算法模板...............................................................................................................................................................1

一． 基础算法....................................................................................................................................2

1. 排序.............................................................................................................................................2

2. 二分.............................................................................................................................................5

3. 高精度 ........................................................................................................................................6

1. 链表 ..........................................................................................................................................18

2. 栈...............................................................................................................................................20

3. 队列 ..........................................................................................................................................23

4. KMP...........................................................................................................................................25

5. Trie 树.......................................................................................................................................26

6. 并查集......................................................................................................................................27

7. 堆...............................................................................................................................................28

8. 哈希表......................................................................................................................................32

9. STL 使用技巧 .........................................................................................................................35

10. 树状数组.............................................................................................................................38

5. 广度优先遍历 ........................................................................................................................57

6. 拓扑排序 .................................................................................................................................58

7. 欧拉回路和欧拉路径 ..........................................................................................................60

8. 最短路问题.............................................................................................................................66

9. 最小生成树.............................................................................................................................73

10. 树的基础算法....................................................................................................................77

11. 最近公共祖先问题 ..........................................................................................................80

12. 二分图 .................................................................................................................................92

13. 差分约束系统....................................................................................................................94

四． 数学知识 .................................................................................................................................97

7. 高斯消元...............................................................................................................................115

8. 求组合数...............................................................................................................................118

9. 容斥原理...............................................................................................................................122

10. 博弈论...............................................................................................................................124

五． 动态规划...............................................................................................................................127

1. 背包问题...............................................................................................................................128

2. 线性 DP .................................................................................................................................143

3. 区间 DP .................................................................................................................................150

4. 计数 DP .................................................................................................................................151

5. 数位统计 DP........................................................................................................................152

3. 排序不等式 ..........................................................................................................................167

4. 绝对值不等式......................................................................................................................167

5. 推公式 ...................................................................................................................................168

七． 时空复杂度分析 .................................................................................................................169

1. 时间复杂度 ..........................................................................................................................169

2. 空间复杂度 ..........................................................................................................................171

一．基础算法

1. 排序

① 快速排序：

#include<iostream>

void quick_sort(int q[],int l,int r){

i++;

}while (q[i]<x);

do{

j--;

}while (q[j]>x);

if (i<j){

swap(q[i],q[j]);

}

}

quick_sort(q,l,j);

}

quick_sort(q,0,n-1);

for (int i=0;i<n;i++){

printf("%d ",q[i]);

}

return 0;

② 归并排序

#include<iostream>

#include<cstdio>

#define _for(i,a,b) for (int i=(a);i<=(b);i++)

using namespace std;

const int N=1e5+5;

int a[N],b[N];

inline void c_plus(){

ios::sync_with_stdio(false);

cin.tie(0);

return;

b[++p]=a[p1++];

}else{

b[++p]=a[p2++];

}

}

_for(i,1,p){

a[l+i-1]=b[i];

}

}

int main(){

merge_sort(1,n);

_for(i,1,n){

cout<<a[i]<<' ';

}

return 0;

}

左加右减

#include<iostream>

#include<cstdio>

using namespace std;

const int N=100010;

int n,q,a[N];

int main(){

scanf("%d%d",&n,&q);

for (int i=0;i<n;i++){

scanf("%d",&a[i]);

int mid=l+r>>1;

if (a[mid]>=k){//check：[l, mid]和[mid + 1, r]

r=mid;

}else{

l=mid+1;

}

}

if (a[l]!=k){

puts("-1 -1");

}else{

}else{

r=mid-1;

}

}

printf("%d\n",l);

}

}

return 0;