算法模板

数据结构

并查集

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%