算法模板

关于板子,其实之前我是很抵触的,认为这种不理解原理而直接套模板的行为并不能使人进步;
后来发现,光靠脑子去想,很多地方理解起来还是比较费劲的,在略知大概之后抄几遍板子,反而是更容易帮助我们理解算法的原理,就像是小时候背古诗,明明很多都不懂,却一定要死记硬背下来,练得多了,自然也能体会到其中的奥妙;
这大概也算是“纸上得来终觉浅,绝知此事要躬行”吧;

搜索

深度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int m,n;    //m*n的图
int vis[m][n];
int go[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

void dfs(int x,int y)
{
if(x<0||x>m||y<0||y>n)
{
return ;
}
if(vis[x][y])
{
return ;
}
vis[x][y]=true;
for(int i=0;i<4;i++)
{
int nx,ny;
nx=x+go[i][0];
ny=y+go[i][1];
dfs(nx,ny);
}
return ;
}

广度优先搜索

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
#include <queue>

using namespace std;

struct data
{
int x,y;
};

int m,n; //m*n的图
int vis[m][n];
int go[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

queue<data> q;

void bfs()
{
while(!q.empty)
{
data f=q.front();
for(int i=0;i<4;i++)
{
int nx,ny;
nx=f.x+go[i][0];
ny=f.y+go[i][1];
if(nx<0||nx>m||ny<0||ny>n)
{
continue;
}
if(vis[nx][ny])
{
continue;
}
vis[nx][ny]=true;
q.push({nx,ny});
}
q.pop();
}
return ;
}

最短路

弗洛伊德

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int n;  //n个点
int e[n][n];

void floyd()
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
for(int k=0;k<n;k++)
{
if(e[j][k]>e[j][i]+e[i][k])
{
e[j][k]=e[j][i]+e[i][k];
}
}
}
}
return ;
}

迪杰斯特拉

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
#include <climits>

int n; //n个点
bool vis[n];
int e[n][n],dis[n];

void dijkstra()
{
for(int i=0;i<n;i++)
{
dis[i]=e[0][i];
}
vis[0]=true;
for(int i=1;i<n;i++)
{
int m=INT_MAX,u;
for(int j=0;j<n;j++)
{
if(vis[j]==false&&dis[j]<m)
{
m=dis[j];
u=j;
}
}
vis[u]=true;
for(int v=0;v<n;v++)
{
if(e[u][v]!=INT_MAX&&dis[v]>dis[u]+e[u][v])
{
dis[v]=dis[u]+e[u][v];
}
}
}
return ;
}

贝尔曼

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
#include <climits>

int n,m; //n个点 m条边

int dis[n],u[m],v[m],w[m];

bool bellman()
{
dis[0]=0;
for(int i=1;i<n;i++)
{
dis[i]=INT_MAX;
}
for(int i=1;i<n;i++)
{
bool check=false;
for(int j=0;j<m;j++)
{
if(dis[u[j]]!=INT_MAX&&dis[v[j]]>dis[u[j]]+w[j])
{
dis[v[j]]=dis[u[j]]+w[j];
check=true;
}
}
if(!check)
{
break;
}
}
for(int i=0;i<m;i++)
{
if(dis[v[i]]>dis[u[i]]+w[i])
{
return true;
}
}
return false;
}

并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int n;  //n个点
int f[n];

int getf(int a)
{
if(f[a]==a)
{
return a;
}
else
{
return f[a]=getf(f[a]);
}
}

void uni(int a,int b)
{
int fa,fb;
fa=getf(a);
fb=getf(b);
f[fb]=fa;
return ;
}

最小生成树

克鲁斯卡尔

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
struct edge
{
int u,v,w;
};

int n,m; //n个点 m条边
int f[n];
edge e[m];

bool cmp(edge a,edge b)
{
return a.w<b.w;
}

int getf(int a)
{
if(f[a]==a)
{
return a;
}
else
{
return f[a]=getf(f[a]);
}
}

bool uni(int a,int b)
{
int fa,fb;
fa=getf(a);
fb=getf(b);
if(fa!=fb)
{
f[fb]=fa;
return true;
}
return false;
}

int kruskal()
{
sort(e,e+m,cmp);
int count=0,sum=0;
for(int i=0;i<m;i++)
{
if(uni(e[i].u,e[i].v))
{
count++;
sum+=e[i].w;
}
if(count==n-1)
{
break;
}
}
return sum;
}

普里姆

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
#include <climits>

int n; //n个点
int e[n][n],dis[n];
bool book[n];

int prim()
{
book[0]=true;
int count=1,sum=0;
while(count<n)
{
int m=INT_MAX;
int j;
for(int i=0;i<n;i++)
{
if(book[i]==false&&dis[i]<m)
{
m=dis[i];
j=i;
}
}
book[j]=true;
count++;
sum+=dis[j];
for(int i=0;i<n;i++)
{
if(book[i]==false&&dis[i]>e[j][i])
{
dis[i]=e[j][i];
}
}
}
return sum;
}

数论

欧几里得定理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int gcd(int a,int b)
{
if(b==0)
{
return a;
}
else
{
return gcd(b,a%b);
}
}

int lcm(int a,int b)
{
return a*b/gcd(a,b);
}

线性筛素数

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
#include <cstring>
#include <vector>

using namespace std;

int n; //n以内的数
bool is[n+1];
vector<int> prime;

void shai()
{
memset(is,true,sizeof(is));
is[0]=is[1]=false;
for(int i=2;i<=n;i++)
{
if(is[i])
{
prime.push_back(i);
}
for(int j=0;j<prime.size()&&i*prime[j]<=MAX;j++)
{
is[i*prime[j]]=false;
if(i%prime[j]==0)
{
break;
}
}
}
return ;
}

快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int qpow(int a,int b)
{
int ans=1;
while(b)
{
if(b%2)
{
ans*=a;
}
a*=a;
b/=2;
}
return ans;
}

矩阵快速幂

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
#include <cstring>

int n; //n*n的矩阵
int ans[n][n],base[n][n];

void multi(int a[n][n],int b[n][n])
{
int t[n][n];
memset(t,0,sizeof(t));
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
for(int k=0;k<n;k++)
{
t[i][j]+=a[i][k]*b[k][j];
}
}
}
memcpy(a,t,sizeof(t));
}

void mpow(int m)
{
memset(ans,0,sizeof(ans));
for(int i=0;i<n;i++)
{
ans[i][i]=1;
}
while(m)
{
if(m%2)
{
multi(ans,base);
}
multi(base,base);
m/=2;
}
return ;
}

动态规划

最长上升子序列(nlogn)

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
int n;  //总长为n的序列
int a[n],dp[n];

int lis()
{
int t=0;
dp[0]=a[0];
for(int i=1;i<n;i++)
{
if(a[i]>dp[t])
{
dp[++t]=a[i];
}
else if(a[i]<=dp[1])
{
dp[0]=a[i];
}
else
{
int k=lower_bound(dp,dp+t,a[i])-dp;
dp[k]=a[i];
}
}
return t+1;
}