OI模板梳理

OI模板梳理

明天自招考试!
花点时间把一些老博客上的一些板子转移过来,顺便也复习一下。
不要问我为什么有封面……

图片来自unsplash.com

一 基础模板

1 高精度计算

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
const int C=0x3f3f;
int a[C],b[C],c[C]; // 数字
int la,lb,lc; // 长度

void plus(){ // a+b
lc = max(la, lb);
for(int i=0; i<lc; i++){
c[i] += a[i]+b[i];
if(c[i] >= 10){
c[i] %= 10;
c[i+1] += 1;
}
}
if(c[lc+1]) lc = lc+1;
}
void mul(){ // a*b
for(int i=0; i<la; i++){
int r=0;
for(int j=0; j<lb; j++){
c[i+j] = a[i]*b[j]+r;
r = c[i+j]/10;
c[i+j]%=10;
}
c[i+lb] = r;
}
lc = la+lb;
while(!c[lc] && lc) lc--; // 前导0
}

2 双向链表

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
57
58
59
60
61
62
63
64
65
66
67
68
template<class T>
class double_list{
public:
T value[MAX_S]; // 值 'k' 的编号
int next[MAX_S]; // 值 'k' 右边节点的下标
int last[MAX_S]; // 值 'k' 左边节点的下标
int key[MAX_S]; // 维护下标在value[]中的下标
int length; int head,tail; // 维护第一个元素和最后一个元素的下标
double_list(){
length=1;
memset(next,0,sizeof(next));
memset(last,0,sizeof(last));
memset(value,0,sizeof(value));
head=tail=value[length]=key[length]=1;
next[length]=last[length]=0;
}
/*在特定值 k 的左边或右边插入特定值 i */
void modify(int k,int i,int p){
value[++length]=i; // 存下标
key[i]=length;

if(p){ // 插入到右边
if(k==tail) tail=length;
int cur=next[k]; // right
next[k]=length; next[length]=cur;
if(last[next[length]]) last[next[length]]=length; // left
last[length]=k;
}
else{
if(k==head) head=length;
int cur=last[k]; // left
last[k]=length; last[length]=cur;
if(next[last[length]]) next[last[length]]=length; // right
next[length]=k;
}
}
/*在队尾接插入特定值 k */
void push_back(int k){
value[++length]=k;
next[tail]=length;
last[length]=tail;
tail=length;
}
/*删除特定值 k */
void pop(int k){
if(!key[k]) return;
k=key[k]; // 将编号转化为下标
key[k]=0; // 标记已经删除
int rit=next[k],lif=last[k];// 获取两边同学的下标
if(k==head) head=rit;
else if(k==tail) tail=lif;
/*更新两边同学*/
last[rit]=last[k];
next[lif]=next[k];
}
/*打印链表(从左到右)*/
void print(){
int p=head;
while(p) {printf("%d ",value[p]); p=next[p];}
}
/*打印链表(从右到左)*/
void re_print(){
int q=tail;
while(q) {printf("%d ",value[q]); q=next[q];}
}
/*询问特定值 k 下标*/
int query(int k) {return value[key[k]];}
};

看懂双向的单向其实很好想。

3 堆

大根

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
struct heap{
int val[100001],n,p,ls,rs,fa,maxs;
void build(){ // 读入数据并建堆
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&val[i]);
sort(val+1,val+n+1,cmp);
}
int _query() {return val[1];} // 返回堆顶元素
void _delete(){ // 删除堆顶元素
val[1]=val[n];
n--; // 模拟出队
p=1; // p永远指向原队尾元素
while(p<=n){
ls=p<<1; rs=(p<<1)|1;
if(ls<=n){ // 判断left_son存在
if(rs<=n) maxs=val[ls]>val[rs]?ls:rs; // rs不存在或ls大于父节点
else maxs=rs; // maxs指向较大儿子的下标
if(val[p]>val[maxs]) break;
/*交换并维护p指针*/
swap(val[p],val[maxs]); p=maxs;
}
else break;
}
}
void _insert(int v){ // 插入新元素
val[++n]=v; // 模拟入队
p=n; // p永远指向新节点坐标
while(p>1){
fa=p>>1;
if(val[fa]>val[p]) break; // 合法
else {swap(val[fa],val[p]); p=fa;} // 不合法,交换并维护
}
}
};

4 并查集

1
2
3
4
5
6
7
8
9
const int CN=1e3;
class dsu{
public:
int fa[CN];
ufs() {for(int i=1;i<CN;i++) fa[i]=i;}
int find(int x) {return fa[x]==x ? x : fa[x]=find(fa[x]);} // 找元素所在的树根
bool examine(int x,int y) {return find(x) != find(y);} // 检查x,y可不可以合并
void merge(int x,int y) {fa[find(x)] = find(y);} // 合并x,y两棵树
}

二 图论

1 最短路

1-1 Dijkstra

Dijkstra 认为:一个点只会被某些特定的点“松弛”,因为如果从其它点转移,最短路径要么变长,要么不变,而绝不可能变短;Dijkstra 每次在做的是就是找到这样的一个“特定的点”,即当前最短路径长度最小的那个点。

这是一个很贪心的策略,因此其成立是有条件的,即图上没有负权环。注意,一条无向的负权边也是负权环。

堆优化 Dijkstra :

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
#define LL long long
const int CN = 1e5+5;
const LL INF = 0x3f3f3f3f3f3f3f2f;

class fs {public: int to,nxt; LL di;} E[CN * 51];
int hd[CN];

class DJ{
public: int id; LL v;
bool operator < (const DJ& a)const {return v > a.v;}
};
priority_queue<DJ> Q;
LL d[CN]; bool vis[CN];
LL SP(int s,int t){
memset(vis, 0, sizeof(vis)); memset(d, 0x3f, sizeof(d));
Q.push((DJ){s, d[s] = 0});
while(!Q.empty()){
int u = Q.top().id; Q.pop();
if(vis[u]) continue; vis[u] = true; // 必须在此处标记访问
for(int k = hd[u]; k; k = E[k].nxt){
int v = E[k].to;
if(d[v] > d[u] + E[k].di){
d[v] = d[u] + E[k].di;
if(!vis[v]) Q.push((DJ){v, d[v]}); // 不能在此处标记访问,因为先入队时该点不一定达到最优
}
}
}
return d[t] < INF ? d[t] : -1;
}

1-2 Floyd

1
2
3
4
5
int f[][];
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
f[i][j] = min(f[i][j], f[i][k]+f[k][j]);

1-3 Bellman-Ford (SPFA)

它死了(费用流问题??)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool ins[CP]; //  是否在队列中
int times[CP]; // times[i] : 节点i被松弛的次数
int d[CP]; // 保存单源最短路
bool spfa(int s){ // 返回有解(true)或无解(false)
memset(d,0x3f,sizeof(d));
memset(ins,false,sizeof(ins));
memset(times,0,sizeof(times));
queue<int>Q; Q.push(s); d[s]=0;
while(!Q.empty()){
int u=Q.front(); Q.pop(); ins[u]=false;
for(int k=hd[u]; k; k=E[k].nxt){
fs e=E[k];
if(d[u]+e.dist < d[e.to]){ // 松弛
d[e.to]=d[u]+e.dist;
if(!ins[e.to]){ // 不在队列中就入队
Q.push(e.to); ins[e.to]=true;
if(++times[e.to] == n) // 松弛了超过n次,存在负环
return false;
}
}
}
}
return true;
}

2 最小生成树

2-1 Kruskal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class edge{...}; 
class ufs{...}; // 并查集
edge E[];
ufs s;
int mst(){
int cnt=0,cst=0;
sort(E+1,E+m+1);
for(int k=1; cnt!=n-1 && k<=m; k++){ // 枚举所有边
if(s.find(E[k].from) == s.find(E[k].to)) continue;
s.fa[find(E[k].from)] = s.find(E[k].to);
cnt+=1; cst+=E[k].c;
}
return cst;
}

2-2 Prim

有点像DJ。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class fs{...}; // 边表
fs E[];
int dis[]; // dis[i] : 1~i的所有边中边权最小的那一个
bool vis[];
int prim(){
memset(dis,0x3f,sizeof(dis));
for(re int i=hd[1];i;i=E[i].nxt)
dis[E[i].to] = min(dis[E[i].to], E[i].c);
int cur=1,cst=0;
for(int i=1; i<n; i++){
int mn=INF;
vis[cur]=1;
for(int i=1;i<=n;++i) // 挑出最小的一个
if(!vis[i] && mn>dis[i])
mn=dis[cur=i];
cst+=mn;
for(re int i=hd[cur]; i ;i=E[i].nxt) // update
if(!vis[E[i].to] && dis[E[i].to]>E[i].c)
dis[E[i].to] = E[i].c;
}
return cst;
}

3 DAG上的最长/最短路

图的最长路显然可以改一改上面最短路的代码来实现。但是对于DAG来说,因为它很特殊:当把节点作为状态的一维时,正好没有后效性,因为节点不可能回到自身;同时最长路问题具有最优子结构,就是当前节点的解可以由下一个节点的解推出来。所以可以DP。

1
2
3
4
5
6
7
8
9
10
11
const int CN=1e3;
class fs{...int ,to,nxt,dist;}E[CN*101]; // 边表略,仅给出关键变量的定义
int hd[CN];
int f[CN]; // f[i] : 从 i 出发的最长路
int dp(int u){
if(f[u]) return f[u]; // 记忆化
f[u] = 0;
for(int k=hd[u]; k; k=E[k].nxt)
f[u] = max(f[u], dp(E[k].to)+E[k].dist);
return f[u];
}

对于特殊数据(图上节点$1\text{~}n$的拓扑序恰好为$1,2,…,n$),甚至可以递推解决:

1
2
3
4
5
6
const int CN=1e3;
int dist[CN][CN];
int f[CN];
for(int i=n;i;i--) // 倒推,先处理拓扑序大的
for(int j=1;j<=n;j++) // 遍历 n 个点
if(dist[i][j]) f[i] = max(f[i], f[j]+dist[i][j]); // 有边相连

这样可以求出图上最长的路径(遍历一遍f[]数组),但对于某些问题(譬如)来说,它还是有局限性的。
DP的局限性在于:这个状态设计要么固定起点,要么就固定终点。如果要求固定起点的同时,到每个点的单源最短路,它就完蛋了。

DAG上最短路的DP也同理,稍改动即可(注意f[]要初始化成INF)。

其它

tips:以下内容请在本站搜索相应文章。

  • 树链剖分 \ LCA
  • 树的重心 \ 树的直径
  • 最大流 \ 最小费用最大流(二分图相关)
  • 强连通分量(缩点) \ 双连通分量
  • 倍增LCA
  • 二分图匹配(匈牙利)
  • k 短路问题(A* 寻路,请参阅这篇文章

三 数学

1 素数筛

Eratosthenes 筛法,此筛法非严格的线性。有关线性筛,请见另一篇博文

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define LL long long
const int CN = 1e7+7;

bool isp[CN]; // 判断素数
LL prime[CN]; // 保存素数

void GetPrime(LL n){
memset(isp,true,sizeof(isp));
for(LL i=2;i<=n;i++){
if(isp[i]){
prime[++prime[0]] = i;
for(int k=2;i*k<=n;k++)
isp[i*k] = false;
}
}
}

2 分解质因数

试除法,复杂度$O(\sqrt{x})$。
注:一个数的质因数数量是$\log$级别。

1
2
3
4
5
6
7
8
9
10
11
12
13
#define LL long long
const int CN = 101;

int cnt = 0; long long p[CN],a[CN];

void Div(LL x){
for(LL i = 2; i * i <= x; i++){
if(x % i) continue;
p[++cnt] = i;
while(!(x % i)) {a[cnt]++; x /= i;}
}
if(x > 1) p[++cnt] = x,a[cnt] = 1;
}

3 高斯-约旦消元

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
/*
解方程组:
a1x1 + a2x2 +...+ anxn = s1
b1x1 + b2x2 +...+ bnxn = s2
...
*/

#define DB double
const int CN = 110;

int n;
DB a[CN][CN];
/*
a[][] : 增广矩阵
a[][n+1] : 储存常数项
*/
DB dabs(DB x) {return x<0 ? x : -x;} // 绝对值

/*
高斯 - 约旦消元 :
通过加减消元,把原方程组化成
k1x1 = v1
k2x2 = v2
...
knxn = vn
的形式,再计算
*/
DB x[CN]; // 保存答案
bool gauss(){
for(int i=1;i<=n;i++){ // 枚举未知数
DB mx = a[i][i]; int p = i;
for(int j=i+1;j<=n;j++){ // 挑选未知数x[i]的最大系数
if(dabs(mx) < dabs(a[j][i]))
mx = a[p = j][i];
}
if(!mx) return false; // 无解
for(int j=1;j<=n+1;j++) // 行、行交换
swap(a[i][j], a[p][j]);
/*加减消元*/
for(int j=1;j<=n;j++){ // 枚举方程
if(j == i) continue;
for(int k=i+1;k<=n+1;k++){ // 枚举系数
a[j][k] -= a[i][k]*(a[j][i]/a[i][i]);
}
}
}
for(int i=1;i<=n;i++)
x[i] = a[i][n+1]/a[i][i]; // 保存解
return true;
}

其它

tips:以下内容请在本站搜索相应文章。

  • 矩阵快速幂(矩阵加速递推)
  • lucas(组合数取模)
  • gcd(最大公约数) \ exgcd(关于其求解不定方程的模板,请参阅CRT&exCRT
  • 逆元
  • CRT & exCRT(同余方程组)

$$ - - - - \mathcal{End} - - - - $$

最近更新: 2019-11-5 更改了试除法的代码,原来的代码复杂度接近O(n)。


评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×