算法模板

发表于 | 分类于 |

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

搜索

深度优先搜索

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

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++)
            {
                e[j][k]=min(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
36
#include <algorithm>
#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]=min(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
#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
36
#include <algorithm>
#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]=min(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
#include <vector>

using namespace std;

int n;  //n以内的数
vector<bool> is;
vector<int> prime;

void shai(int n)
{
    is=vector<int>(n+1,true);
	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]<=n;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
41
#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));
    return ;
}

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
26
27
28
29
30
#include <algorithm>
#include <vector>

using namespace std;

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;
}

字符串

KMP

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

using namespace std;

vector<int> getn(string s)
{
    vector<int> v(1,0);
    for (int i=1,j=0;i<s.size();i++)
    {
        while(j>0&&s[i]!=s[j])
        {
            j=v[j-1];
        }
        if(s[i]==s[j])
        {
            j++;
        }
        v.push_back(j);
    }
    return v;
}

int kmp(string s,string ss)
{
    int t=0;
    vector<int> next=getn(ss);
    for (int i=0,j=0;i<s.size();i++)
    {
        while(j>0&&s[i]!=ss[j])
        {
            j=next[j-1];
        }
        if(s[i]==ss[j])
        {
            j++;
        }
        if(j==ss.size())
        {
            return i-j-1;
        }
    }
    return -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
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
#include <vector>

using namespace std;

vector<int> a,ans;

void build(int l, int r, int o)
{
    if(l==r)
    {
        ans[o] = a[l];
        return;
    }
    int m=(l+r)/2;
    build(l,m,o*2);
    build(m+1,r,o*2+1);
    ans[o]=ans[o*2]+ans[o*2+1];
}

int query(int ql,int qr,int l,int r,int o)
{
    int m=(l+r)/2,s=0;
    if(ql<=l&&qr>=r)
    {
        return ans[o];
    }
    if(ql<=m)
    {
        s+=query(ql,qr,l,m,o*2);
    }
    if(qr>m)
    {
        s+=query(ql,qr,m+1,r,o*2+1);
    }
    return s;
}

void update(int p,int v,int l,int r,int o)
{
    int m=(l+r)/2;
    if(l==r)
    {
        ans[o]+=v;
    }
    else
    {
        if(p<=m)
        {
            update(p,v,l,m,o*2);
        }
        else
        {
            update(p,v,m+1,r,o*2+1);
        }
        ans[o]=ans[o*2]+ans[o*2+1];
    }
    return;
}