1.线性筛模板
void get_primes(int n)
{
for(int i = 2; i <= n; i++)
{
if(!st[i]) primes[cnt++] = i;
for(int j = 0; primes[j] <= n / i; j ++)
{
st[primes[j]*i] = true;
if(i % primes[j] == 0) break;
}
}
}
2.二分模板
版本1
当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1;，计算mid时不需要加1。(右边满足的最小值)
C++ 代码模板：
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
版本2
当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid;，此时为了防止死循环，计算mid时需要加1。(左边满足的最大值)
C++ 代码模板：
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
3.并查集
(1)朴素并查集：
int p[N]; //存储每个点的祖宗节点
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ ) p[i] = i;
// 合并a和b所在的两个集合：
p[find(a)] = find(b);
(2)维护size的并查集：
int p[N], size[N];
//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
size[i] = 1;
}
// 合并a和b所在的两个集合，顺序不能反，保证新加入后祖宗不变，节点数对应：
size[find(b)] += size[find(a)];
p[find(a)] = find(b);
(3)维护到祖宗节点距离的并查集：
int p[N], d[N];
//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离
// 返回x的祖宗节点，带权并查集
int find(int x)
{
if (p[x] != x)
{
int u = find(p[x]);
d[x] += d[p[x]];
p[x] = u;
}
return p[x];
}
// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
d[i] = 0;
}
// 合并a和b所在的两个集合
p[find(a)] = find(b);
d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量c
4.字符串哈希
核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果
typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
h[i] = h[i - 1] * P + str[i];
p[i] = p[i - 1] * P;
}
// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
return h[r] - h[l - 1] * p[r - l + 1];
}
5.堆
// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;
// 交换两个点，及其映射关系
void heap_swap(int a, int b)
{
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a], hp[b]);
swap(h[a], h[b]);
}
void down(int u)
{
int t = u;
if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (u != t)
{
heap_swap(u, t);
down(t);
}
}
void up(int u)
{
while (u / 2 && h[u] < h[u / 2])
{
heap_swap(u, u / 2);
u >>= 1;
}
}
// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);
6.KMP
// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{
while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j ++ ;
ne[i] = j;
}
// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j ++ ;
if (j == m)
{
j = ne[j];
// 匹配成功后的逻辑
}
}
7.djikstra优化版
时间复杂度 O(mlogn), n 表示点数，m 表示边数
typedef pair<int, int> PII;
int n; // 点的数量
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储所有点到1号点的距离
bool st[N]; // 存储每个点的最短距离是否已确定
int dij()
{
memset(dis,0x3f,sizeof dis);
dis[1]=0;
priority_queue<PII,vector<PII>,greater<PII>>q;
q.push({dis[1],1});
while(q.size())
{
PII t=q.top();
q.pop();
int tt=t.second;
if(st[tt]) continue;
st[tt]=true;
for(int i=h[tt];i!=-1;i=ne[i])
{
int j=e[i];
if(dis[j]>dis[tt]+w[i])
{
dis[j]=dis[tt]+w[i];
q.push({dis[j],j});
}
}
}
return dis[n];
}
8.spfa
时间复杂度 平均情况下 O(m)，最坏情况下 O(nm), n 表示点数，m 表示边数
int n; // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储每个点到1号点的最短距离
bool st[N]; // 存储每个点是否在队列中
void add(int a,int b,int c)
{
w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int spfa()
{
memset(dis,0x3f,sizeof dis);
dis[1]=0;
queue<pair<int,int>>q;
q.push({dis[1],1});
st[1]=true;
while(q.size())
{
auto t=q.front();
q.pop();
int tt=t.second;
st[tt]=false;
for(int i=h[tt];i!=-1;i=ne[i])
{
int j=e[i];
if(dis[j]>dis[tt]+w[i])
{
dis[j]=dis[tt]+w[i];
if(!st[j])
{
st[j]=true;
q.push({dis[j],j});
}
}
}
}
return dis[n];
}
9.kruskal
时间复杂度是 O(mlogm), n 表示点数，m 表示边数
点的成本可以看作是点到某个某个特别点的边权
int n, m; // n是点数，m是边数
int p[N]; // 并查集的父节点数组
struct Edge // 存储边
{
int a, b, w;
bool operator< (const Edge &W)const
{
return w < W.w;
}
}edges[M];
int find(int x) // 并查集核心操作
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int kruskal()
{
sort(edges, edges + m);
for (int i = 1; i <= n; i ++ ) p[i] = i; // 初始化并查集
int res = 0, cnt = 0;
for (int i = 0; i < m; i ++ )
{
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
a = find(a), b = find(b);
if (a != b) // 如果两个连通块不连通，则将这两个连通块合并
{
p[a] = b;
res += w;
cnt ++ ;
}
}
if (cnt < n - 1) return INF;
return res;
}
10.有向图的拓扑序列
序列保存在orz中
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool top()
{
for(int i=1;i<=n;i++)
{
if(d[i]==0) q.push(i);
}
while(q.size())
{
int t=q.front();
//cout<<t<<endl;
orz[cnt++]=t;
q.pop();
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
d[j]--;
if(d[j]==0) q.push(j);
}
}
if(cnt<n) return 0;
else return 1;
}
11.floyd算法
时间复杂度是 O(n3), n 表示点数
初始化：
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if (i == j) d[i][j] = 0;
else d[i][j] = INF;
// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
12.Bellman-Ford算法
时间复杂度 O(nm), n 表示点数，m 表示边数
注意在模板题中需要对下面的模板稍作修改，加上备份数组，详情见模板题。
int n, m; // n表示点数，m表示边数
int dist[N]; // dist[x]存储1到x的最短路距离
struct Edge // 边，a表示出点，b表示入点，w表示边的权重
{
int a, b, w;
}edges[M];
// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
// 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
for (int i = 0; i < n; i ++ )
{
for (int j = 0; j < m; j ++ )
{
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
if (dist[b] > dist[a] + w)
dist[b] = dist[a] + w;
}
}
if (dist[n] > 0x3f3f3f3f / 2) return -1;
return dist[n];
}
13.RMQ(ST表)--区间最值查询
区间查询用到st表,只能操作静态表，需要修改时，需要额外操作
首先定义dp[i,j]为以第i个数为起点，长度为2^j的一段区间中的最大值，显然状态转移为
dp[i,j] = max(dp[i,j-1],[i+2^(j-1),j-1]);
查询时把区间分成前后都为长度为len=r-l+1的区间，/*k为区间的最大倍增数*/,左边是(l,2^k),右边是(r-2^k+1,r)
结果为 max(dp[l][k],dp[r-(1<<j)+1],[k])
换底公式：k=log2(n)=log(n)/log(2); math里的函数
初始化
for(int j=0;j<M;j++)
for(int i=1;i+(1<<j)-1<=n;i++)//中间是区间边界
if(!j) dp[i][j] = w[i];
else dp[i][j] = max(dp[i][j-1],dp[i+(1<<j-1)][j-1]);
查询
return max(dp[l][k],[r-(1<<k)+1][k]);
14.线段树
结构体储存数的信息，比起数组，在操作传参时避免传参时过多而出错
struct Segment_Tree
{
int l,r;
LL sum; //这里可以维护任何满足区间加法的信息，这里就用区间求和了
//根据情况tag标记
}tr[4 * N]; //要开四倍空间
函数1———build
void build (int u,int l,int r) //当前正在下标为u的点，这个点表示的区间是[l,r]
{
if (l == r)
{
tr[u] = {l,r,a[l]};/a[i]为各个点的信息
return ;
}
tr[u] = {l,r}; //记得存储当前点表示的区间，否则你会调上一整天
int mid = l + r >> 1;
build (u << 1,l,mid),build (u << 1 | 1,mid + 1,r); //u << 1就是u * 2，u << 1 | 1就是u * 2 + 1
push_up (u); //push_up函数的意思是把某一个节点的信息有他的子节点算出来
}
函数2.push_up
void push_up (int u) //这里只有区间和，区间和就是由一个点的左右子节点的和相加
{
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;//向下递归更新
}
函数3.modify
1.单点修改
思路: 我们通过二分查找的形式找到要修改的点，然后把找的过程上的链都修改一下。时间复杂度 O(logn)
void modify (int u,int x,int d) //当前这个点是下标为u的点，要把第x个数修改成d
{
if (tr[u].l == tr[u].r)
{
tr[u].sum = d; //如果当前区间只有一个数，那么这个数一定是要修改的。
return ;
}
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify (u << 1,x,d); //如果在左边就递归修改左半边区间
else modify (u << 1 | 1,x,d); //如果在右边就递归修改右半边区间
push_up (u) //记得更新信息
}
2.区间修改
思路： lazy标记法用它统一记录区间的修改，而不是一个个修改区间内的值
void push_down (int u) //下传标记函数
{
auto &root = tr[u],&left = tr[u << 1],&right = tr[u << 1 | 1]; //加了引用符号只要修改这个变量就会修改他被赋值的变量
if (root.sum_tag) //有懒标记才下传
{
left.tag += root.tag,left.sum += (LL)(left.r - left.l + 1) * root.tag; //这里的子节点要加上懒标记，因为这里懒标记的意思是不包括当前节点
right.tag += root.tag,right.sum += (LL)(right.r - right.l + 1) * root.tag; //同理
root.tag = 0; //懒标记记得清零
}
}
void modify (int u,int l,int r,int d) //当前遍历到的点下标是u，要将区间[l,r]增加d
{
if (l <= tr[u].l && tr[u].r <= r)
{
tr[u].sum += (LL)(tr[u].r - tr[u].l + 1) * d;
tr[u].sum_tag += d; //这里我才用了y总的懒标记的意思，一个点所有的子节点都加上d，而前一行时加上根节点的数，因为不包括根节点。
return ;
}
push_down (u); //一定要分裂，只要记牢在递归左右区间之前，就要分裂
int mid = tr[u].l + tr[u].r >> 1; //注意时tr[u].l和tr[u].r
if (l <= mid) modify (u << 1,l,r,d); //左边有修改区间，就递归左半边
if (r >= mid + 1) modify (u << 1 | 1,l,r,d); //右边有修改区间，就递归右半边
push_up (u); //要记得要把这个点的信息更新一下
}
15.LCA--最近公共祖先
(1).向上标记法（ O(n) )
(2).倍增
fa[i,j]标识从i开始，向上跳2^j步所能走到的节点，0<=j<=logn
depth[i]表示深度
步骤：
[1].先让两个点跳到同一层
[2].让两个点同时往上跳，一直跳到它们公共祖先的下一层
预处理O(nlogn)
查询O(logn)(3).tarjan( O(n + m) )
在深度优先遍历的同时， 将所有点分成三类
[1].已经遍历过的点， 且回溯过的点
[2].正在搜索的分支
[3].还未搜索到的点
倍增法
//倍增处理
void bfs()
{
//memset(dis, 0x3f, sizeof dis);
memset(depth, 0x3f, sizeof depth);
queue<int> q;
depth[0] = 0, depth[1]=1;//并非是1，是root
//dis[1] = 0;
q.push(1);
while(q.size())
{
int u = q.front();
q.pop();
for(auto &[v, w] : g[u])
{
if(depth[v]>depth[u] + 1)
{
depth[v] = depth[u] + 1;
q.push(v);
fa[v][0] = u;
for(int k = 1; k <= 13; k ++)
fa[v][k]=fa[fa[v][k-1]][k-1];
dis[v] = dis[u] + w;//权值， 到公共祖先的距离
}
}
}
}
//倍增查询
int lca(int a, int b)
{
if(depth[a] < depth[b]) swap(a, b); //a在下面
for(int k = 13; k >= 0; k --)
if(depth[fa[a][k]] >= depth[b])
a=fa[a][k]；//跳到同一层
if(a == b) return a;
for(int k = 13; k >=0 ; k --)
if(fa[a][k] != fa[b][k])
a = fa[a][k], b = fa[b][k];//一起向上跳，跳到公共祖先的下一层
return fa[a][0];
}
tarjan
int find(int x)//合并祖先节点
{
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
void tarjan(int u)//st[u]等于1，2可以直接合在一起，因为每次遍历时都会先对子节点进行标记
{
//cout << u << endl;
st[u] = 1;
for(auto &[v, w] : g[u])
{
if(!st[v])
{
dis[v] = dis[u] + w;
tarjan(v);
p[v] = u;
}
}
for(auto &[v, id] : query[u])//离线做法的体现
if(st[v] == 2)
res[id] = dis[u] + dis[v] - dis[find(v)] * 2;
//cout << id << ' ' << dis[u] << ' ' << dis[v] << ' ' << res[id] << endl;
st[u] = 2;
}
16.树状数组
1.快速求前缀和O(log n)————可以和差分数组联系起来(区间和的查询) //(a1+a2+……+an)=(b1+b2+……+bn)*(n+1)-(1*b1+2*b2+……nbn)
2.修改某一个数O(log n) 树状数组不能求区间最值
主要函数 :int lowbit(int x) { return x & - x；}
修改：增加、建树
void add(int x, int c)
{
for (int i = x; i <= n; i += lowbit(i)) //lowbit(i)是i后需要修改的前缀和区间
tr[i] += c;
}
查询：
LL query(int x)
{
LL res = 0;
for (int i = x; i; i -= lowbit(i))
res += c[i];
return res;//返回前缀和
}
17.匈牙利算法
时间复杂度O(nm),实际远小于
int n1, n2; // n1表示第一个集合中的点数，n2表示第二个集合中的点数
int h[N], e[M], ne[M], idx; // 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边
int match[N]; // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
bool st[N]; // 表示第二个集合中的每个点是否已经被遍历过
bool find(int u)
{
for (auto v : g[u])
{
if (!st[v])
{
st[v] = true;
if (match[v] == 0 || find(match[v]))
{
match[v] = u;
return true;
}
}
}
return false;
}
// 求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点
int res = 0;
for (int i = 1; i <= n1; i ++ )
{
memset(st, false, sizeof st);
if (find(i)) res ++ ;
}
18.染色法判断二分图
int n; // n表示点数
int h[N], e[M], ne[M], idx; // 邻接表存储图
int color[N]; // 表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色
// 参数：u表示当前节点，c表示当前点的颜色
bool dfs(int u, int c)
{
color[u] = c;
for(auto v : g[u])
{
if (color[v] == -1)
{
if (!dfs(v, !c)) return false;
}
else if (color[v] == c) return false;
}
return true;
}
bool check()
{
memset(color, -1, sizeof color);
bool flag = true;
for (int i = 1; i <= n; i ++ )
if (color[i] == -1)
if (!dfs(i, 0))
{
flag = false;
break;
}
return flag;
}
19.欧拉函数
int phi(int x)
{
int res = x;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
{
res = res / i * (i - 1);
while (x % i == 0) x /= i;
}
if (x > 1) res = res / x * (x - 1);
return res;
}
20.试除法求所有约数
vector<int> get_divisors(int x)
{
vector<int> res;
for (int i = 1; i <= x / i; i ++ )
if (x % i == 0)
{
res.push_back(i);
if (i != x / i) res.push_back(x / i);
}
sort(res.begin(), res.end());
return res;
}