省选模板汇总

0. 写在前面

这里的内容是为即将到来的省选做准备,主要参考来源是OI-wiki、lydrainbowcat的《算法竞赛进阶指南》和hzwer的《OI省选算法汇总》,在此鸣谢

1. 基础算法

1.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 <bits/stdc++.h>

#define ll long long
#define sum(a, b, mod) (((a) + (b)) % mod)

bool check(int mid)
{
//do something
}

bool calc(double mid)
{
//do something in real number field
}

double find(double l, double r) // find answer in real number field
{
double L = l, R = r;
for(int i = 1; i <= 100; i++)
{
double mid = (L + R) / 2;
if(calc(mid)) r = mid;
else l = mid;
}
return l;
}

int getmin(int l, int r)
{
int L = l, R = r;
while(L < R)
{
int mid = (L + R) >> 1;
if(check(mid))
R = mid;
else L = mid + 1;
}
return L;
}

int getmax(int l, int r)
{
int L = l, R = r;
while(L < R)
{
int mid = (L + R + 1) >> 1;
if(check(mid))
L = mid;
else R = mid - 1;
}
return L;
}

int main()
{
//do something
return 0;
}

2. 搜索

2.1 A*算法

留坑待填

3.数据结构

3.1 树状数组

模板题 洛谷 P3374 【模板】树状数组 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 <bits/stdc++.h>

#define R register
#define ll long long
#define sum(a, b, mod) (((a) + (b)) % mod)

const int MaxN = 5e5 +10;

int n, m, a[MaxN];

struct BIT
{
int c[MaxN];
int lowbit(int x) { return x & (-x); }
void add(int pos, int val)
{
while(pos <= n)
c[pos] += val, pos += lowbit(pos);
}
int query(int pos)
{
int ret = 0;
while(pos)
ret += c[pos], pos -= lowbit(pos);
return ret;
}
int Query(int l, int r) {return query(r) - query(l - 1); }
}T;

inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch > '9' || ch < '0')
{
if(ch == '-')
f = 0;
ch = getchar();
}
while(ch <= '9' && ch >= '0')
x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return f ? x : (-x);
}

int main()
{
n = read(), m = read();
for(int i = 1; i <= n; i++)
a[i] = read(), T.add(i, a[i]);
while(m--)
{
int op = read(), x = read(), y = read();
if(op == 1)
T.add(x, y);
else printf("%d\n", T.Query(x, y));
}
return 0;
}

3.2 线段树

模板题 洛谷 P3372 【模板】线段树 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
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
#include <bits/stdc++.h>

#define R register
#define ll long long
#define sum(a, b, mod) (((a) + (b)) % mod)

const int MaxN = 1e5 + 10;

int n, m;
ll a[MaxN];

struct node
{
ll l, r;
ll sum, tag;
};

struct SegmentTree
{
node t[MaxN << 2];
void pushup(int id) { t[id].sum = t[id << 1].sum + t[id << 1 | 1].sum; }
void build(int id, ll l, ll r)
{
t[id].l = l, t[id].r = r;
if (l == r)
return (void)(t[id].sum = a[l]);
int mid = (l + r) >> 1;
build(id << 1, l, mid), build(id << 1 | 1, mid + 1, r), pushup(id);
};
void pushdown(int id)
{
if (t[id].tag)
{
ll tag = t[id].tag;
t[id << 1].tag += tag, t[id << 1 | 1].tag += tag;
t[id << 1 | 1].sum += tag * (t[id << 1 | 1].r - t[id << 1 | 1].l + 1);
t[id << 1].sum += tag * (t[id << 1].r - t[id << 1].l + 1), t[id].tag = 0;
}
}
void modify(int id, int l, int r, ll val)
{
if (t[id].l > r || l > t[id].r) return;
if (l <= t[id].l && t[id].r <= r)
{
t[id].tag += val;
t[id].sum += val * (t[id].r - t[id].l + 1);
return;
}
pushdown(id), modify(id << 1, l, r, val);
modify(id << 1 | 1, l, r, val), pushup(id);
}
ll query(int id, int l, int r)
{
if (t[id].l > r || l > t[id].r) return 0;
if (l <= t[id].l && t[id].r <= r) return t[id].sum;
pushdown(id);
return query(id << 1, l, r) + query(id << 1 | 1, l, r);
}
} T;

inline ll read()
{
ll x = 0, f = 1;
char ch = getchar();
while (ch > '9' || ch < '0')
{
if (ch == '-')
f = 0;
ch = getchar();
}
while (ch <= '9' && ch >= '0')
x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return f ? x : (-x);
}

int main()
{
n = read(), m = read();
for(int i = 1; i <= n; i++)
a[i] = read();
T.build(1, 1, n);
while(m--)
{
int op = read();
if(op == 1)
{
ll l = read(), r = read(), val = read();
T.modify(1, l, r, val);
}
else
{
ll l = read(), r = read();
printf("%lld\n", T.query(1, l, r));
}
}
return 0;
}
Your browser is out-of-date!

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

×