我的算法模板
ACM竞赛模板——旧忆
基础
语法基础
匿名函数
1 | function<int(int, int)> add = [&](int a, int b) -> int { |
算法基础
排序
快速排序
1 | void quick_sort(int q[],int l,int r) |
快速排序求区间第k小数
1 | //得到q[l~r]中第k小的数 |
归并排序
1 | void merge_sort(int q[],int l,int r){ |
求区间逆序对数量
应用:把一个无序的序列变成有序的序列,每次操作可以交换相邻两个数,最少需要的操作次数是这个序列的逆序对数量
1 | LL merge_sort(vector<int> &q,int l,int r){ |
二分
1 | int bsearch_l(int q[],int l,int r){ |
位运算
1 | // 获取 a 的第 b 位,最低位编号为 0 |
去掉最后一位 | (101101->10110) | x >> 1
在最后加一个0 | (101101->1011010) | x < < 1
在最后加一个1 | (101101->1011011) | x < < 1+1
把最后一位变成1 | (101100->101101) | x | 1
把最后一位变成0 | (101101->101100) | x | 1-1
最后一位取反 | (101101->101100) | x ^ 1
把右数第k位变成1 | (101001->101101,k=3) | x | (1 < < (k-1))
把右数第k位变成0 | (101101->101001,k=3) | x & ~ (1 < < (k-1))
右数第k位取反 | (101001->101101,k=3) | x ^ (1 < < (k-1))
取末三位 | (1101101->101) | x & 7
取末k位 | (1101101->1101,k=5) | x & ((1 < < k)-1)
取右数第k位 | (1101101->1,k=4) | x >> (k-1) & 1
把末k位变成1 | (101001->101111,k=4) | x | (1 < < k-1)
末k位取反 | (101001->100110,k=4) | x ^ (1 < < k-1)
把右边连续的1变成0 | (100101111->100100000) | x & (x+1)
把右起第一个0变成1 | (100101111->100111111) | x | (x+1)
把右边连续的0变成1 | (11011000->11011111) | x | (x-1)
取右边连续的1 | (100101111->1111) | (x ^ (x+1)) >> 1
去掉右起第一个1的左边 | (100101000->1000) | x & (x ^ (x-1))
判断奇数 (x&1)==1
判断偶数 (x&1)==0
取右边第一个1所在位置 x&-x
十进制a、b,判断是否存在a的第i位为0,b的第i位为1
1
2if ((a&b)<b) 存在a的第i位为0,b的第i位为1
else 不存在异或性质:
与加法的关系:$a+b≡a\oplus(mod\ 2)$
注意奇偶性
数据结构
队列
单调队列
1 | //b[i]表示以i为右端点的连续k个数的最小值 |
栈
单调栈
1 | //lmin[i]表示a[i]左边第一个比它小的数 |
并查集
并查集基础
1 | struct DSU { |
带权并查集
1 | struct DSU { |
分块
莫队算法
例题:HH的项链
题意:n个数,多次询问区间不同数的个数
1 |
|
CDQ分治
给定 $n$ 个元素(编号 $1 \sim n$),其中第 $i$ 个元素具有 $a_i,b_i,c_i$ 三种属性。 设 $f(i)$ 表示满足以下 $4$ 个条件: 1. $a_j \le a_i$ 2. $b_j \le b_i$ 3. $c_j \le c_i$ 4. $j \neq i$ 的 $j$ 的数量。 对于 $d \in [0,n)$,求满足 $f(i) = d$ 的 $i$ 的数量。
1 |
|
树
树的基础
树的重心
概念:以树的重心为整棵树的根时,它的最大子树最小(也就是删除该点后最大联通块最小)
1 | vector<vector<int>> v; |
树的直径
树的直径,是指树上最长的一条链。
1 | vector<vector<PII>> v; |
树的中心
概念:以树的中心为整棵树的根时,从该根到每个叶子节点的最长路径最短
该点到树中其他结点的最远距离最近
1 | // Problem: 树的中心 |
LCA(最近公共祖先)
- 倍增法:祖孙询问
1 | //N为结点数量,M=log2(N),一般多开2个,开成log2(N)+2 |
Tarjan算法求多次询问树上任意两点的最短距离(离线)
时间复杂度O(n+q)
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56//N为结点个数,M为询问个数
int res[M],dist[N],p[N],st[N];
//res[i]为第i-1个询问的结果,dist[i]为结点i到根节点距离,p[i]为并查集数组
//st[i]为0表示还没被搜索过,为1表示正在被搜索,为2表示已经被搜索过
vector<PII> query[M];//存储每个询问
vector<vector<PII>> edge;//存储边
int find(int x){//缩点
if(p[x]!=x) return p[x]=find(p[x]);
return p[x];
}
void dfs(int u,int fa){//预处理每个点到根节点距离
for(auto it:edge[u]){
int v=it.first,w=it.second;
if(v==fa) continue;
dist[v]=dist[u]+w;
dfs(v,u);
}
}
void tarjan(int u){
st[u]=1;
for(auto it:edge[u]){
int v=it.first,w=it.second;
if(!st[v]){
tarjan(v);
p[v]=u;
}
}
for(auto it:query[u]){
int v=it.first,id=it.second;
if(st[v]==2){
int ans=find(v);
res[id]=dist[u]+dist[v]-2*dist[ans];
}
}
st[u]=2;
}
void solve(){
int n,m;cin>>n>>m;
edge.resize(n+1);
for(int i=0;i<n-1;i++){
int x,y,k;cin>>x>>y>>k;
edge[x].push_back({y,k});
edge[y].push_back({x,k});
}
for(int i=0;i<m;i++){
int a,b;cin>>a>>b;
if(a!=b){
query[a].push_back({b,i});//离线处理询问
query[b].push_back({a,i});
}
}
for(int i=1;i<=n;i++) p[i]=i;
dfs(1,-1);
tarjan(1);
for(int i=0;i<m;i++) cout<<res[i]<<endl;
}
虚树
虚树的构建
1.先预处理原树的lca和dfs序,然后用栈维护关键点,构造虚树。
2. 对k个查询点按dfs序排序,先加入根节点,再按顺序加入查询点。3.栈维护从根向下的一条链上的关键点,按深度从小到大存储。
当加入a[x]后,满足s[1]= root,s[top] = a[x], s[x]为s[x 一1]的后代。4.现在考虑加入查询点a[i],设lca= LCA(s[top],a[i]),分两类讨论:
(1) lca = s[top],即a[i]是s[top]子树内的节点。直接把a[i]入栈。
(2) lca ≠ s[top],即a[i]不是 s[top]子树内的节点(如图)。
lca下面路径上的关键点都应出栈, 出栈时从s[top -1]向s[top]连边。注意:当dep[s[top-1]]<dep[lca]时,停止出栈。此时,
①如果lca = s[top],说明lca已在栈中,那么直接把a[i]入栈。
②如果lca ≠ s[top],说明lca不在栈中, s[top]依然在lca的下面。
先从lca向s[top]连一条边,再把 s[top]出栈,把lca入栈,把a[i]入栈。
枚举结束后,还要把最后一条链上的关键点连边,出栈。
例题:
给定一个树,q次询问:
每个询问包括点的个数k,接下来是k个点。
从这棵树中选一点使得到这k个点的最大距离最小,求这个最小值。
1 |
|
树状数组
一维树状数组
单点修改区间查询(树状数组的基本功能)
1 | //N为维护的数列长度 |
区间修改单点查询
1 | //N为维护的数列长度 |
区间修改区间查询
1 | template<class T> |
权值树状数组查询第k小
1 | // 权值树状数组查询第 k 小 |
二维树状数组
1 | const int N = 2050; |
线段树
不带懒标记的线段树
模板(区间最大子段和)
1 | template<class Info> |
带懒标记的线段树
模板(区间修改区间加减区间求最值)
1 | template<class Info, class Tag> |
区间加减区间求和
1 |
|
区间赋值区间求和
1 |
|
1 | struct Tag { |
区间乘区间加区间求和
1 |
|
区间整体query的例子
1 | Node query(int u,int l,int r){ |
线段树合并
1 |
|
可持久化线段树(主席树)
求区间第k小数(静态)
1 |
|
线段树套线段树
矩阵查最值
封装
1 | struct SegmentTree2d{ |
1 |
|
splay
1 |
|
树链剖分
树剖+线段树
给定一棵树,树中包含 n 个节点(编号 1∼n),其中第 i 个节点的权值为 ai。
初始时,11 号节点为树的根节点。
现在要对该树进行 m 次操作,操作分为以下 44 种类型:
1 u v k
,修改路径上节点权值,将节点 u 和节点 v 之间路径上的所有节点(包括这两个节点)的权值增加 k。2 u k
,修改子树上节点权值,将以节点 u 为根的子树上的所有节点的权值增加 k。3 u v
,询问路径,询问节点 u 和节点 v 之间路径上的所有节点(包括这两个节点)的权值和。4 u
,询问子树,询问以节点 u 为根的子树上的所有节点的权值和。
1 |
|
珂朵莉树(ODT)
1 | struct ODT{ |
树上启发式合并(dsu on tree)
例题:Lomsat gelral
树的节点有颜色$c_i$,一种颜色占领了一个子树,当且仅当没有其他颜色在这个子树中出现得比它多(可能有多个)。求占领每个子树的所有颜色之和。
核心:先求每个轻儿子所在子树的信息每次求完清空,最后求重儿子所在子树求完不清空回溯到当前结点时保留这个重儿子所在子树的颜色信息,然后再累加上每个轻儿子所在子树的信息。
时间复杂度$O(nlogn)$
1 | #include<bits/stdc++.h> |
ST表(RMQ问题)
求区间最大/ 小数
时间复杂度:预处理O($nlogn$) 在线查找O($1$)
1 | //N为原数组个数,M为log2(N),一般多开2个,开成log2(N)+2 |
维护区间最大次大值
1 |
|
扫描线
矩形面积并
- 线段树(时间复杂度)
1 |
|
- 计算几何(时间复杂度)
1 |
|
二维数点
二位前缀和思想+树状数组(离线)
1 | int tr[N], ans[N]; |
图论
建图优化
线段树建图优化
例题:n个点,m条边,s是起点,问点s到点1~n的最短距离
有三种边:接下来的 q 行表示 q 种方案。
- 输入
1 v u w
表示第一种方案,从v向u连边,权值为w - 输入
2 v l r w
表示第二种方案,从v向$[l,r]$区间连边,权值为w - 输入
3 v l r w
表示第三种方案,从$[l,r]$区间向v连边,权值为w
这里的线段树实际上有两个,分别为u和u+D,左树从上往下,右数从下往上,区间向点连边从右树结点连出,点向区间连入到左树结点。
1 | // Problem: B. Legacy |
前后缀建图优化
例题:以2-SAT为背景。你有 n 张卡片,第 i 张卡片正面写着一个数字 ai,反面写着一个数字 bi,现在你可以摆放卡片(规定每张卡片朝上的面),询问是否存在一种摆放方式,使得任意两张不同的卡片朝上面所写的数字都是互质的。
1 | // Problem: F - Coprime Solitaire |
树链剖分+线段树优化建图
1 |
|
tarjan
有向图的强连通分量
1 | int n,m; |
无向图的双连通分量
边的双连通分量
边的双连通分量:图中任意两不同点之间都有至少两条边不重复的路径。
求将无向图转化为边的双连通分量需要连接的最少边数
1 | l |
点的双连通分量
点的双连通分量:图中任意两不同点之间都有至少两条点不重复的路径。
求将无向图转化为点的双连通分量需要连接的最少边数
1 |
|
拓扑序
1 | vector<vector<int>> edge; |
传递闭包
floyd算法
1 | for(int i = 1; i <= n; i ++)//初始化 |
最短路
Dijkstra(仅有正权边)
- *朴素版本O($n^{2}$)
- 稠密图常用
1 | int g[N][N],dist[N];// |
堆优化版O($mlogn$)
稀疏图常用
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
28vector<vector<pair<int,int>>> edge;
int dist[N];
int dijkstra(){
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 1});
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
while(heap.size()){
auto t=heap.top();
heap.pop();
int u = t.second, distance = t.first;
if(dist[u]<distance) continue;
for(auto it:edge[u]){
int v=it.first,w=it.second;
if(dist[v] > dist[u] + w){
dist[v] = dist[u] + w;
heap.push({dist[v], v});
}
}
}
if(dist[n] == 0x3f3f3f3f3f3f3f3f){
return -1;
}else{
return dist[n];
}
}
edge[a].push_back({b,c});
cout<<disjkstra()<<endl;
Bellman-ford(存在负权边,有边数限制)
时间复杂度O(nm)
1 | int n,m,k; |
Spfa(存在负权边,可判断负环)
时间复杂度最好O(n),最坏O(nm)
- spfa求最短路
1 | int dist[N]; |
判断负环
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
31int dist[N],cnt[N];//注意把dist[0]建成超级源点,
bool st[N];
bool spfa(){
queue<int> q;//如果被数据卡TLE,可尝试换成stack
//这步相当于建了一个分别连向1~n,边权为0的虚拟源点0
for(int i=1;i<=n;i++){
st[i]=true;
q.push(i);
}
while(q.size()){
int u=q.front();
q.pop();
st[u]=false;
for(auto it:edge[u]){
int v=it.first,w=it.second;
if(dist[j]>dist[u]+w[i]){
dist[j]=dist[u]+w[i];
cnt[j]=cnt[u]+1;
if(cnt[j]>=n) return true;
if(!st[j]){
q.push(j);
st[j]=true;
}
}
}
}
return false;
}
注意:建边
if(spfa()) 存在负环
else 不存在负环
Floyd(预处理出任意两边距离)
时间复杂度O($n^3$)
1 | int d[N][N]; |
无向图求最小环(Floyd)
注意这里INF不能取0x3f3f3f3f3f3f3f3f,因为3*INF会爆long long。
1 |
|
最小生成树
Prim算法
时间复杂度O($n^2$)
1 | int g[N][N]; |
Kruskal算法
时间复杂度O($mlogm$)
1 | //N为最大结点数,M为最大边数 |
Kruskal重构树
性质:原图中的两点u、v在Kruskal重构树上的LCA的点权是原图中u到v的所有路径中最大边的最小值(从小到大排序边)(最小边的最大值,从大到小排序边)。
1 |
|
1 | // Problem: G. Vlad and the Mountains |
二分图
二分图判定(染色法)
1 | int color[N]; |
匈牙利算法(二分图的最大匹配)
必须从1开始计数
1 | int match[N];//match[i]表示左半部第i个结点匹配的右半部结点 |
网络流
最大流
Dinic算法求最大流
1 | const int N = , M = , INF = 1e8; |
无源汇上下界可行流
1 |
|
有源汇上下界最大流
1 | const int N = 210, M = (N + 10000) * 2, INF = 1e8; |
有源汇上下界最小流
1 | const int N = 50010, M = (N + 125003) * 2, INF = 2147483647; |
多源汇最大流
1 | void solve(){ |
关键边
定义:只给其扩大容量之后整个流网络的最大流能够变大,对于这样的边我们称之为关键边。
求关键边的数量:
1 | void dfs(int u, bool st[], int t) |
最小割
Dinic算法求最小割
代码与Dinic算法求最大流相同,因为最大流=最小割。
最大权闭合子图
定义:所有闭合子图中点权之和最大的图,闭合图指图中所有点沿着边能到达的所有点都必须在该点集中。
建图:源点S向所有正权边连一条容量为该点权的边,所有负权边向汇点连一条容量为该点权相反数的边,图中原有边容量为正无穷。正权点点权和减去最小割即为最大权闭合子图的最大权值。
最大密度子图
定义:给定无向图$G=(V,E)$,其子图记为$G’=(V’,E’)$,在所有子图构成的集合中,密度$D=\frac {E’} {V’}$最大的元素称为最大密度子图。
最小点权覆盖集
定义:图中所有边的两个端点至少有一个在点集中所构成的点权之和最小的点的集合。
这个问题是NP完全问题,只能通过爆搜完成,而最小割模型的最小点权覆盖集是对于一个二分图而言的。
建图:首先该图是个二分图,分成左右两部分点集,只有左右两个点集之间右边。从源点向所有左部结点连一条容量为该点权值的边,从右部结点向汇点连一条容量为该点权值的边,中间的边容量为正无穷。求出的最小割即为最小权点覆盖。
如何找方案:从源点沿着残留网络容量大于0的边搜到的点记为集合S,剩下的点记为集合T,若边E(根据割边的定义,这里只枚举正向边)的两点a,b分别在S,T集合,则该边为割边。
最大点权独立集
定义:任意两点中间不存在边的点权之和最大的点的集合。
同“最小点权覆盖集”,也是NP完全问题,这里的最小割模型同样对于二分图而言。
最大点权独立集= 所有点的权值之和 - 最小点权覆盖集(同上)
费用流
EK+spfa求最小费用最大流
求最小费用最大流转为最大费用最大流时:
可以将spfa中的memset(d, 0x3f, sizeof d);改为memset(d, -0x3f, sizeof d);,以及松弛操作符号取反即可。
或者直接将费用取反。
1 |
|
二分图最优匹配
例题:有 $n$ 件工作要分配给 $n $个人做。第 $i$ 个人做第 $j$件工作产生的效益为 $c[i][j]$试设计一个将 $n$ 件工作分配给 $n$ 个人做的分配方案。对于给定的 $n$ 件工作和 $n$ 个人,计算最优分配方案和最差分配方案。
1 | const int N = 110, M = 5210, INF = 1e8; |
最大权不相交路径
用容量控制经过该点(拆点)或该边的次数,用费用表示经过该点累加的权值,求最大费用最大流。
网格图模型
对于某个点可以走无限次次但只有一次能获得价值可以采用拆点,然后分成两个边,其中一个边容量为1,费用为该点价值;另一条边容量为正无穷,费用为0。
网络流模型的常用技巧
拆点技巧
对于限制点的经过次数,我们可以把一个点拆成入点和出点,从入点向出点连一条容量为能经过该点的次数。
还原流网络
1 | for (int k = 0; k < idx; k += 2) |
欧拉回路
输入第一行包含一个整数,t=1为无向图,t=2为有向图。
1 |
|
2-SAT
时间复杂度:O(n+m)
建图:当u被选择时,v一定被选择,则u向v连边。
第一行包含两个整数 n,m。接下来 m 行,每行包含四个整数 i,a,j,b,用来描述一个条件,表示 “xi 为 a 或 xj 为 b”。输出任意一组解或报告无解。
1 |
|
差分约束
存在负环时无解
记得建立一个超级源点,连向所有点
最长路:
求最小差值(至少)
A-B<=W$\Longrightarrow$连一条由B->A,边权为W的边
A>=C$\Longrightarrow$连一条0->A,边权为C的边最短路:
求最大差值(最多)
A-B<=W$\Longrightarrow$连一条由B->A,边权为W的边
A<=C$\Longrightarrow$连一条0->A,边权为C的边
1 | int cnt[N],dist[N];; |
仙人掌
给一个N个点M条边的仙人掌。仙人掌定义如下:
任意一条边至多只出现在一条简单回路的无向连通图称为仙人掌。
有 Q 组询问,每次询问两点之间的最短路径。
第一行包含三个整数,分别表示 N,M,Q。
下接 M 行,每行三个整数 v,u,w 表示一条无向边 v−u,长度为 w。
最后 Q 行,每行两个整数 v,u 表示一组询问。
1 |
|
数学
数论
龟速乘
1 | int Mul(int a, int b, int p){ |
快速幂
1 | //a ^ b mod p |
矩阵快速幂加速递推
1 | struct matrix{ |
逆元
快速幂
求$a^{-1}$%p
1 | qpow(a,p-2,p); |
扩展欧几里得求逆元
1 | struct INV{ |
欧拉函数
1 | //返回1~x中与x互质的数的个数 |
筛法求欧拉函数
1 | int primes[N],cnt,int euler[N]; |
质数
试除法判断质数
1 | bool is_prime(int x){ |
分解质因数
1 | vector<pair<int,int>> divide(int x){ |
筛质数
1.朴素做法O(nlogn)
1 | bool st[N]; |
2.诶氏筛法 O(nloglogn)
1 | bool st[N]; |
3.线性筛O(n)
1 | bool st[N]; |
约数
试除法求约数
1 | vector<int> get_divisors(int n){ |
gcd/lcm
1 | gcd: |
扩展欧几里得算法
定理引入:
裴蜀定理:设a, b是不全为零的整数,则存在整数x, y使得ax+by=gcd(a,b) ——OIWIKI
扩展欧几里得算法
求$ax+by=gcd(a,b)$的一组可行解
1 | //返回gcd(a,b) |
求解更一般的方程$ax+by=c$
设$d=gcd(a,b)$,当且仅当$d|c$时有解 $c\bmod gcd(a,mb)$
通解=特解+齐次解
特解:
$x_1=x_0c/d,y_1=y_0c/d$
1
2
3
4
5
6
7
8int exgcd(int a,int b,int &x,int &y);//函数同上
int a,b,x0,y0,x,y;cin>>a>>b;
int d=exgcd(a,b,x0,y0);
//x0和y0为ax+by=gcd(a,b)的一组解
//x1和y1为ax+by=c的一组特解
通解:
x=x1+k*b/d,y=y1-k*a/d,k∈z齐次解:
即$ax+by=0$的解
通解:
通解=特解+齐次解
$x=x_1+kb/d,y=y_1-ka/d,k∈z$
令$t=b/d(x=x’+kt)$,则对于x的最小非负整数解为$(x’\bmod t+t)\bmod t$
求解一次线性同余方程$ax≡b(\bmod m)$
等价于求:$ax+my=b$
1
2
3
4int exgcd(int a,int b,int &x,int &y);//函数同上
int a,b,m,x,y;cin>>a>>b>>m;
exgcd(a,m,x,y);
x*a/b即为一组合法解
同余方程组
中国剩余定理(孙子定理)
求解同余方程组形如:
$x \equiv a_1 (\mod m_1)$
$x \equiv a_2 (\mod m_2)$
$\dots$
$x \equiv a_k (\mod m_k)$
条件:$m_1,m_2,\dots,m_k$两两互质.
令$M=\prod_{i=1}^k m_i$,$M_i=\frac M{m_i}$
$t_i$是$M_i$关于$m_i$的逆元,即$M_i\times t_i\equiv 1(\mod m_i)$
$x=\sum_{i=1}^n a_iM_it_i + Mi * k, k∈Z$
1 | // Problem: 曹冲养猪 |
扩展中国剩余定理
中国剩余定理的扩展版,不需要满足$m_1,m_2,\dots,m_k$两两互质。
1 | // Problem: 表达整数的奇怪方式 |
BSGS
条件:$a,p$互质
求$a^x \equiv b(\mod p)$
时间复杂度:O($\sqrt p$)
1 | // Problem: BSGS |
扩展BSGS
求$a^x \equiv b(\mod p)$
不需要满足$a,p$互质的条件
1 | // Problem: 扩展BSGS |
Pollard rho
1 | using i64 = long long; |
数论函数
莫比乌斯函数
1 | int primes[N],cnt; |
线性代数
线性基
模板
1 | struct lb{ |
贪心法求线性基
1 |
|
高斯消元求线性基
1 | void Gauss(int a[],int &n){ //高斯消元求线性基 |
求从n个整数序列选取一些(至少一个)数(每个数最多选一次)进行异或运算的所有结果中第k小的结果。
1 |
|
组合数学
求组合数
杨辉三角预处理所有组合数
c[a][b]表示$C_{a}^{b}$
1 | int c[N][N]; |
求单个组合数
1 | struct Comb{ |
Lucas定理求组合数
适用于p不固定的情况
1 | int qmi(int a,int k,int p){ |
求组合数(高精度)
1 | a,b=map(int,input().split()) |
1 |
|
博弈论
SG函数
例题:n堆石子,每次操作玩家从任意一堆拿去石子,每次拿取的石子数列必须包含于集合s,最后无法操作的人失败。
1 | int n,m; |
多项式
NTT
1 | // Problem: 多项式乘法 |
字符串
kmp
- 版本1
1 | char s[N],t[N];//s为主串,t为模式串 |
版本2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24int ne[N];//前后缀相等且长度最长
char p[N],s[M];//p是主串,s是模式串
vector<int> res;
//求ne的过程
int i=0,j=0;
for(i=2,j=0;i<=n;i++){
while(j&&p[i]!=p[j+1]){
j=ne[j];
}
if(p[i]==p[j+1]) j++;
ne[i]=j;
}
//kmp的匹配过程,将所有模式串在主串出现位置的起始下标保存在res中
for(i=1,j=0;i<=m;i++){
while(j&&s[i]!=p[j+1]){
j=ne[j];
}
if(s[i]==p[j+1]) j++;
if(j==n){
res.push_back(i-n);
j=ne[j];//为了观察其后续是否还能跟S数组后面的数配对成功
}
}
字符串哈希(双模正反向哈希)
1 | const pair<long long, long long> P(131, 13331); |
1 | struct strHash{ |
1 | long long mod1, mod2; |
Trie树
字符串插入与询问
- N指结点总数
1 | //注意:此处的N指的是输入字符串的字符数量总和 |
最大异或对(存储二进制)
如:
1 | N=1e5+10,M=N*31;//M为结点总数,最多可能为数的个数*每个数有31位 |
ac自动机
1 |
|
manacher
时间复杂度:
1 | char b[N]; |
最小表示法
1 | //获得字符串s的最小表示法 |
计算几何
计算几何基础
1 | /*----------计算几何模板----------*/ |
自适应辛普森积分
模板
1 | namespace SIMPSON{ |
圆面积并
1 |
|
动态规划
Nim
定义$dp[u][m1][m2][m3][l1][l2][p1][p2][p3]$为取到第$u$位,取模$a1,a2,a3$的余数分别为$m1,m2,m3$,三个数是否受限($l1, l2, l3$), 三个数是否取过1,因为这题答案为0满足但不在题意范围内。
1 |
|
恨7不成妻
1 |
|
杂项
预备板
1 |
|
对拍
duipai.bat
1 | g++ baoli.cpp -o baoli |
make.cpp
1 |
|
自动取模
1 | template<class T> |
高精度
1 | const int base = 1000000000; |
离散化
1 | vector<int> nums; |
随机
爬山法
模拟退火
二维平面上给定n个点,求这个平面上任选一点到这个n个点的最小距离和。
1 |
|
读写相关
__int128读写
1 | inline __int128 read() |
快读快写
版本1
1 | struct read { |
版本2
1 | inline int read() { |
10进制转x进制
1 | string dict = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; |