Tarjan
TarjanTarjan基于深搜,是一种离线算法
强连通分量连通块（有向图）tarjan+栈找点的集合
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include <bits/stdc++.h>using namespace std;typedef long long ll;const int M = 1e6 + 5;stack<int> k;vector<int> mp[M], ans[M];bool instack[M] = {0};int dfn[M] = {0}, low[M] = {0}, cnt = 0, t = 0;void tarjan(int x){ dfn[x] = low[x] = ++cnt; k.push(x); instack[x] = true; for (i ...
stl库
stl库vector头文件$#include $
常用用法
函数
含义
$name$.push_back($value$);
在$name$尾部接上一个元素$value$
$name$.pop_back($value$)
弹出$name$尾部元素
$name$.back()
获取$name$尾部元素
$name$.begin()
获取$name$的首元素地址
$name$.end()
$name$最后一个元素的后一位地址(为空)
$name$.rbegin()
获取$name$最后一位地址
$name$.rend()
$name$首元素地址的前一位(为空)
$name$.resize($len$)
给$name$开拓$len$个空间($name[0]$ ~ $name[len-1]$可用)
$name$.size()
返回$name$大小(长度)
$name$.empty()
检查$name$是否为空,为空返回$true$
queue头文件$#include $
常用用法
函数
含义
$name$.push($value$ ...
最小生成树
最小生成树本文采用kruskal算法实现
什么是最小生成树原图中边的权值最小的生成树
最小是指指的是所有边权值之和小于或者等于其它生成树的边的权值之和
这也就意味着图中不存在环
实现算法kruskal和prim算法
其中kruskal是针对边(优先队列+并查集),常用于稀疏图
prim算法则是针对点(dfs),常用于稠密图
原理用优先队列将所有的边都存入,按照从小到大的顺序排列,依次取出最小的边进行链接,同时用并查集检查是否形成了回路,如果形成了回路则不要这条边,否则加入这条边
代码实现123456789101112131415161718192021222324252627282930// 并查集int fa[M];void init() { for (int i = 0; i <= n; i++) { fa[i] = i; }}int fd(int x) { return fa[x] = fa[x] == x ? x : fd(fa[x]);}void un(int x, int y ...
优先队列
优先队列什么是优先队列优先队列,有着队列的性质,即从尾部插入,在头部取出,由于它的底层是二叉堆,所以它可以在插入元素的时候将其根据优先级进行排列
时间复杂度由于底层是二叉堆,将元素从堆底推到堆顶时间复杂度为O(logn),故优先队列插入时间复杂度为O(logn)
用法跟队列唯一不同的地方在于,队列的头部用front来访问,但是优先队列底层是堆,所以用top来访问头部(顶部)
其他用法基本与队列一样
定义12queue<int> q1; //队列priority_queue<int> q2; //优先队列
自定义优先级单元素123priority_queue<int> q; //递增//等同于priority_queue<int, vector<int>, less<int>> q;
1priority_queue<int, vector<int>, greater<int>> q; //递减
多元素用结构体存储元素,排序方法跟sort有异曲同工之处
12345678 ...
线段树
线段树建立节点信息123struct book{ int l, r, sum = 0, lazy = 0;//区间[l, r], 区间和, 懒标记}tree[M];
初始化12345678910111213//递归建树void build(int k, int l, int r){ tree[k].l = l; tree[k].r = r; if(l == r){ tree[k].sum = Number[i]; return; } int mid = (l + r) >> 1; build(k << 1, l, mid); build(k << 1 | 1, mid + 1, r); update(k);}
更新123void update(int k){ tree[k].sum = tree[k << 1].sum + tree[k << 1 | 1].sum; ...
数论
数论多边形面积公式$sum = \frac{1}{2}\abs{\sum^n_{i=1}x_iy_{i+1}-x_{i+1}y_i}\$
其中$x_{n+1}=x_1,y_{n+1}=y_1$
前缀和与差分
前缀和与差分前缀和什么是前缀和前缀和是一个数组的某项下标之前(包括此项元素)的所有数组元素之和
前缀和有什么用前缀和是一种预处理,用于降低查询的时间复杂度
例如:给定n个整数,进行m次询问,每次询问给出左端点和右端点,问这两个端点之间所有元素之和是多少.
如果对于每次询问都用for循环一个个相加,那么时间复杂度将高达O(m*n),但是如果用前缀和来处理那么时间复杂度将是O(m)
原理给定一个数组,命名为a数组
value
10
20
30
40
50
60
index
0
1
2
3
4
5
求出他的前缀和数组,命名为sum数组,为了方便起见我们对sum数组进行一个错位处理
value
0
10
30
60
100
150
210
index
0
1
2
3
4
5
6
如果我想求区间[2,5)之和,即
ans=a2+a3+a4
对于sum数组则有
sum2=a0+a1
sum5=a0+a1+a2+a3+a4
此时我们可以发现:
sum5-sum2=a2+a3+a4=ans
代码123456int a[N ...
快速幂
快速幂快速幂例题:P1226 【模板】快速幂||取余运算 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
问题:对于一个数a,我们如何求出他的b次方?由于数可能比较大我们需要对结果对p取模
一般做法是a*a*a*…*a,一共有b个a相乘,如果b足够大,那么时间复杂度将为O(b),那么有没有什么方法可以快速运算呢?
例如:求2^10
我们需要先进行一个降幂操作,先使最终结果为sum,sum初始化为1
base
2
4
4
16
32
32
power
10
5
4
2
1
0
now
2^10
4^5
4^4
16^2
32^1
32^0
sum
1
1
1*4=4
4
4
4*32=128=2^10
times
0
1
1
2
3
3
由上表可以看出,当power为奇数的时候,我们需要让sum*=base,同时power-=1
当power==0时,此时sum就是最终结果
由例子可以看出,如果用暴力算法,需要运算10次,但是如果用快速幂只需要运算3次,故时间复杂度为O(l ...
快速乘
[[快速幂]]
快速乘问题:
对于两个大数相乘取模有可能在乘完之后发生溢出
两数相乘由于底层原因导致时间不是最优
前置知识快速幂
代码123456789101112typedef long long ll;ll getMul(ll x, ll y, ll mod){ ll res = 0; while(y){ if(y & 1){ res = (res + x) % mod; } x = (x << 1) % mod; y >>= 1; } return res;}
二叉搜索树
二叉搜索树什么是二叉搜索树二叉搜索树简称为BST,又称二叉排序树,二叉查找树
二叉搜索树规定:左孩子的值小于根节点的值,右孩子的值大于等于根节点的值
建树本文采取结构体建树,使用先序遍历建树
思路:
令先序序列为front
list序列的第一项为当前树的根节点,记第一项为root,用双指针的方法对后面的序列进行查找,指针定义为left和right,让left从第二项开始自左向右进行查找,right从最后一项开始自右向左开始查找,我们需要找到:
list[left] >= list[root]
list[right] < list[root]
如果此时right + 1 != left则说明无法构成二叉搜索树
代码123456789101112131415161718192021const int M = 1e6 + 7;int front[M];int n; //有n个节点struct Tree { int l = -1, r = -1, val;} tree[M];int build(int l, int r) ...
