算法模板

发表于 | 更新于: | 分类于 | 阅读次数:
字数统计: 3,033 | 阅读时长 ≈ 18

数据结构

并查集

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
#define MAXN 1000
int par[MAXN];
int u_rank[MAXN];

int n = 500;
void init()
{
    for(int i=0; i<n; i++)
    {
        par[i] = i;
        u_rank[i] = 0;
    }
}

int u_find(int x)
{
    if(par[x] == x)
        return x;
    else
        return par[x] = u_find(par[x]);
}

void unite(int x, int y)
{
    x = u_find(x);
    y = u_find(y);
    if(x == y)
        return;
    if(u_rank[x] < u_rank[y])
        par[x] = y;
    else
    {
        par[y] = x;
        u_rank[x]++;
    }
}

bool same(int x, int y)
{
    return u_find(x) == u_find(y);
}

BIT(树状数组)

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
/*
	计算前i项和需要从i开始，不断把当前位置i的值加入到结果中，并从i中减去i的二进制最低非0位对应的幂，直到i变为0为止。i的二进制最后一个1可以通过 i&-i 得到。
*/
int sum(int i)
{
    int s = 0;
    while(i>0)
    {
        s += BIT[i];
        i -= i&-i;
    }
    return s;
}

/*
	使第i项的值增加x需要从i开始，不断把当前位置i的值增加x，并把i的二进制最低非0位对应的幂加到i上。
*/
void add(int i, int x)
{
    while(i<=n)
    {
        BIT[i] += x;
        i += i&-i;
    }
}

线段树

单点的更新维护

敌军布阵

题目：求区间和

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include<cstdio>
#include<iostream>
#include<cstring>

//#define LOCAL
//#define DEBUG
#define MAXN 50005
using namespace std;

int T, n;
int kiss = 1;
int a[MAXN];
char ope[10];
int op1, op2;
struct Tree
{
    int val;
}SegTree[MAXN<<2];

void init()
{
    memset(a, 0, sizeof a);
    memset(SegTree, 0, sizeof SegTree);
}
void PushUp(int root)
{
    SegTree[root].val = SegTree[root<<1].val + SegTree[root<<1|1].val;
}

void build(int root, int l, int r)
{
    if(l==r)
    {
        scanf("%d", &a[l]);
        SegTree[root].val = a[l];
    }
    else
    {
        int mid = l+r>>1;
        build(root<<1, l, mid);
        build(root<<1|1, mid+1, r);
        PushUp(root);
    }
}

int query(int root, int l, int r, int a, int b)
{
    if(a>r || b<l)
        return 0;
    if(a<=l && b>=r)
        return SegTree[root].val;

    int mid = l+r>>1;
    return query(root<<1, l, mid, a, b)+query(root<<1|1, mid+1, r, a, b);
}

void update(int root, int l, int r, int ind, int modifyVal)
{
    if(l==r)
    {
        SegTree[root].val += modifyVal;
        return;
    }
    int mid = l+r>>1;
    if(ind <= mid)
        update(root<<1, l, mid, ind, modifyVal);
    else
        update(root<<1|1, mid+1, r, ind, modifyVal);
    PushUp(root);
}

int main()
{
    #ifdef LOCAL
        freopen("C:\\Users\\Administrator\\Desktop\\in.txt", "r", stdin);
    #endif

    scanf("%d", &T);
    while(T--)
    {
        init();
        scanf("%d", &n);
        build(1, 1, n);
        printf("Case %d:\n", kiss++);
        while(scanf("%s",ope))
        {
            if(ope[0] =='E')
                break;
            scanf("%d%d",&op1, &op2);
            if(ope[0] == 'Q')
                printf("%d\n", query(1,1,n,op1,op2));
            else if(ope[0] == 'A')
                update(1, 1, n, op1, op2);
            else if(ope[0] == 'S')
                update(1, 1, n, op1, -op2);
        }

        #ifdef DEBUG
        for(int i=1; i<=40; i++)
            printf("%2d:%5d\n", i, SegTree[i].val);
        for(int i=1; i<=n; i++)
            printf("%d: %d\n",i, a[i]);
        int ans = query(1,1,n,1,8);
        printf("%d", ans);
        #endif

    }

    return 0;
}

区间的更新维护

Train Seats Reservation

题目：求区间最大值

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <utility>
#include <algorithm>
#define MAXN 100010
#define INF 0x3f3f3f3f
//#define DEBUG
#define DataIn
typedef long long LL;

using namespace std;

int n;
int start, endd, num;

struct Tree
{
    int val;
    int modify;
} SegTree[MAXN<<2];

void PushUp(int root)
{
    SegTree[root].val = max(SegTree[root<<1].val, SegTree[root<<1|1].val);
}

void PushDown(int root, int l, int r)
{
    if(SegTree[root].modify)
    {
        SegTree[root<<1].val += SegTree[root].modify;
        SegTree[root<<1|1].val += SegTree[root].modify;

        SegTree[root<<1].modify += SegTree[root].modify;
        SegTree[root<<1|1].modify += SegTree[root].modify;

        SegTree[root].modify = 0;
    }
}

void build(int root, int l, int r)
{
    if(l==r)
        SegTree[root].val = SegTree[root].modify = 0;
    else
    {
        int mid = l+r>>1;
        build(root<<1, l, mid);
        build(root<<1|1, mid+1, r);
        PushUp(root);
    }
}

void update(int root, int l, int r, int a, int b, int modify)
{
    if(a>r || b<l)
        return;
    if(a<=l && b>=r)
    {
        SegTree[root].val += modify;
        SegTree[root].modify += modify;
        return;
    }
    PushDown(root, l, r);
    int mid = l+r>>1;
    update(root<<1, l, mid, a, b, modify);
    update(root<<1|1, mid+1, r, a, b, modify);
    PushUp(root);
}

int query(int root, int l, int r, int a, int b)
{
    if(a>r || b<l)
        return 0;
    if(a<=l && b>=r)
        return SegTree[root].val;
    PushDown(root, l, r);
    int mid = l+r>>1;
    return max(query(root<<1, l, mid, a, b), query(root<<1|1, mid+1, r, a, b));
}

void init()
{
    memset(SegTree, 0, sizeof(SegTree));
}
int main()
{
#ifdef DataIn
    freopen("C:\\Users\\Administrator\\Desktop\\in.txt", "r", stdin);
#endif

    while(scanf("%d", &n) == 1 && n)
    {
        init();
        //build(1, 1, 100);


        for(int i=1; i<=n; i++)
        {
            scanf("%d%d%d",&start, &endd, &num);
            update(1, 1, 100, start, endd-1, num);
#ifdef DEBUG
            for(int i = 1; i<=100; i++)
            {
                printf("%-4d", SegTree[i].val);
            }
#endif // DEBUG
        }
        printf("%d\n", SegTree[1].val);
    }

    puts("*");
    return 0;
}

单调队列

1
2
3
4
5
6
7
8
9
10
11
12
for(int i=0; i<(n<<1); i++)
{
    // l<r表示队列非空
    while(l<r && sum[i] < sum[que[r-1]])	//入队操作，参照引用中的1
        r--;
    que[r++] = i;

    if(i>=n && sum[que[l]] - sum[i-n] >= 0)
        ans++;
    while(l<r && que[l] <= i-n+1)	//出队操作，将超出区间的出队
        l++;
}

数论

组合数初始化

1
2
3
4
5
6
C[0][0] = 1;
for(int i=1; i<MAXN; i++)
    C[i][0] = 1;
for(int i=1; i<MAXN; i++)
    for(int j=1; j<MAXN; j++)
        C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;

矩阵快速冪

取模(数组实现)

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
const int MOD = 998244353;

typedef struct
{
    long long m[2][2];
}matrix;
matrix I={1,0,0,1};
matrix P={0,1,1,1};
matrix mul(matrix a,matrix b)
{
    int i,j,k;
    matrix c;
    for(i=0;i<2;i++)
      for(j=0;j<2;j++)
      {
          c.m[i][j]=0;
          for(k=0;k<2;k++)
            c.m[i][j]+=(a.m[i][k]*b.m[k][j])%MOD;
          c.m[i][j]%=MOD;
      }
    return c;
}

matrix qpow_MOD(int n)
{
    matrix a=P,b=I;
    while(n>0)
    {
        if(n&1)
          b=mul(b,a);
        n=n>>1;
        a=mul(a,a);
    }
    return b;
}

不取模(Vector实现)

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
typedef vector<int> vec;
typedef vector<vec> mat;

const int MOD = 1e9+7;
mat mul(mat &A, mat &B)
{
    mat C( A.size(),  vec( B[0].size() ) );
    for(int i=0; i<A.size(); i++)
        for(int k=0; k<B.size(); k++)
            for(int j=0; j<B[0].size(); j++)
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;

    return C;

}


mat qpowmod(mat A, LL n)
{
    mat B( A.size(), vec( A.size() ) );
    for(int i=0; i<A.size(); i++)
        B[i][i] = 1;

    while(n)
    {
        if(n & 1)
            B = mul(B, A);
        A = mul(A, A);
        n >>= 1;
    }

    return B;
}

Lucas定理

代码未曾用过，正确性与否待测试

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
#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;
typedef long long LL;

LL n,m,p=1e9+7;

LL quick_mod(LL a, LL b)
{
    LL ans = 1;
    a %= p;
    while(b)
    {
        if(b & 1)
        {
            ans = ans * a % p;
            b--;
        }
        b >>= 1;
        a = a * a % p;
    }
    return ans;
}

LL C(LL n, LL m)
{
    if(m > n) return 0;
    LL ans = 1;
    for(int i=1; i<=m; i++)
    {
        LL a = (n + i - m) % p;
        LL b = i % p;
        ans = ans * (a * quick_mod(b, p-2) % p) % p;
    }
    return ans;
}

LL Lucas(LL n, LL m)
{
    if(m == 0) return 1;
    return C(n % p, m % p) * Lucas(n / p, m / p) % p;
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%I64d%I64d", &n, &m);
        printf("%I64d\n", 2*Lucas(n-1,m)%p);
    }
    return 0;
}
//Lucas定理，解决C(n,m)%p问题

图论

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
30
31
32
33
34
35
36
37
38
39
40
struct edge
{
    int to, cost;
};

int V;
int d[MAXN];
vector<edge> G[MAXN];
typedef pair<int, int> P;

void Dijkstra()
{
    fill(d, d+V, INF);

    priority_queue<P, vector<P>, greater<P> > que;

    d[s] = 0;
    que.push( P(0, s) );

    while(!que.empty())
    {
        P p = que.top();
        que.pop();

        int v = p.second;
        if(d[v] < p.first)
            continue;

        for(int i=0; i<G[v].size(); i++)
        {
            edge e = G[v][i];

            if(d[e.to] > d[v] + e.cost)
            {
                d[e.to] = d[v]+e.cost;
                que.push( P(d[e.to], e.to));
            }
        }
    }
}

Prim算法

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
int cost[MAX_V][MAX_V];
int mincost[MAX_V];
bool used[MAX_V];
int V;

int prim()
{
	for(int i=0; i<V; i++)
    {
        mincost[i] = INF;
        used[i] = false;
    }
    
    mincost[0] = 0;
    int res = 0;
    
    while(true)
    {
        int v = -1;
        //从不属于X的顶点中选取从X到其权值最小的点
        for(int u=0; u<V; u++)
        {
			if( !used[u] && (v==-1 || mincost[u] < mincost[v]) )
                v = u;
        }
        
        if(v == -1)
            break;
        used[v] = true;
        res += mincost[v];
        
        for(int u=0; u<V; u++)
			mincoust[u] = min(mincost[u], cost[v][u]);
    }
    
    return res;
}

Kruskal算法

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

bool cmp(const edge& e1, const edge& e2)
{
    return e1.cost < e2.cost;
}

edge es[MAX_E];
int V, E;

int kruskal()
{
	sort(es, es+E, cmp);
    init_ufs(V);
    int res = 0;
    for(int i=0; i<E; i++)
    {
        edge e = es[i];
        if( !same(e.u, e.v) )
        {
            unite(e.u, e.v);
            res += e.cost;
        }
    }
    
    return res;
}

常用

离散化

1
2


数位dp

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
int dfs(int pos, int state, bool lead, bool limit)
{
    if(pos == -1)
        return 1;	//按题目返回
    if(!limit && !lead && ~dp[pos][state])
        return dp[pos][state];
    
    int up = limit ? a[pos] : 9;
    int ans = 0;
    
    for(int i=0; i<=up; i++)
    {
    	if()
            ans += dfs(pos-1, /*状态表示*/, lead && i==0, limit && i==up);
        else
            ans += dfs.....
    }
    
    if(!limit && !lead)
        dp[pos][state] = ans;
    return ans;
}

int go(int x)
{
    int pos = 0;
    while(x)
    {
        a[pos++] = x%10;
        x /= 10;
    }
    return dfs(pos-1, /*状态*/, true, true);
}

黑科技

杜教BM

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for(int i=a;i<n;i++)
namespace linear
{
    ll mo=1000000009;
    vector<ll> v;
    double a[105][105],del;
    int k;
    struct matrix
    {
        int n;
        ll a[50][50];
        matrix operator * (const matrix & b)const
        {
            matrix c;
            c.n=n;
            rep(i,0,n)rep(j,0,n)c.a[i][j]=0;
            rep(i,0,n)rep(j,0,n)rep(k,0,n)
            c.a[i][j]=(c.a[i][j]+a[i][k]*b.a[k][j]%mo)%mo;
            return c;
        }
    }A;
    bool solve(int n)
    {
        rep(i,1,n+1)
        {
            int t=i;
            rep(j,i+1,n+1)if(fabs(a[j][i])>fabs(a[t][i]))t=j;
            if(fabs(del=a[t][i])<1e-6)return false;
            rep(j,i,n+2)swap(a[i][j],a[t][j]);
            rep(j,i,n+2)a[i][j]/=del;
            rep(t,1,n+1)if(t!=i)
            {
                del=a[t][i];
                rep(j,i,n+2)a[t][j]-=a[i][j]*del;
            }
        }
        return true;
    }
    void build(vector<ll> V)
    {
        v=V;
        int n=(v.size()-1)/2;
        k=n;
        while(1)
        {
            rep(i,0,k+1)
            {
                rep(j,0,k)a[i+1][j+1]=v[n-1+i-j];
                a[i+1][k+1]=1;
                a[i+1][k+2]=v[n+i];
            }
            if(solve(n+1))break;
            n--;k--;
        }
        A.n=k+1;
        rep(i,0,A.n)rep(j,0,A.n)A.a[i][j]=0;
        rep(i,0,A.n)A.a[i][0]=(int)round(a[i+1][A.n+1]);
        rep(i,0,A.n-2)A.a[i][i+1]=1;
        A.a[A.n-1][A.n-1]=1;
    }
    void formula()
    {
        printf("f(n) =");
        rep(i,0,A.n-1)printf(" (%lld)*f(n-%d) +",A.a[i][0],i+1);
        printf(" (%lld)\n",A.a[A.n-1][0]);
    }
    ll cal(ll n)
    {
        if(n<v.size())return v[n];
        n=n-k+1;
        matrix B,T=A;
        B.n=A.n;
        rep(i,0,B.n)rep(j,0,B.n)B.a[i][j]=i==j?1:0;
        while(n)
        {
            if(n&1)B=B*T;
            n>>=1;
            T=T*T;
        }
        ll ans=0;
        rep(i,0,B.n-1)ans=(ans+v[B.n-2-i]*B.a[i][0]%mo)%mo;
        ans=(ans+B.a[B.n-1][0])%mo;
        while(ans<0)ans+=mo;
        return ans;
    }
}

int main()
{
    int abcdefg[] = {3,9,20,46,106,244,560,1286,2956,6794,15610,35866,82416,189384};
    vector<ll> V(abcdefg, abcdefg+14);//<-----
    linear::build(V);
    linear::formula();
    ll n;
    while(~scanf("%lld",&n))
    {
        printf("%lld\n",linear::cal(n-1));
    }
    return 0;
}
❤采之欲遗谁，所思在远道。❤
0%