算法模板整理
高精度运算
高精度加法
1
2
3
4
5
6
7
8
9
10
11
12
13
| vector<int> add(vector<int> &a, vector<int> &b) {
if(a.size() < b.size()) return add(b, a);
int t = 0;
vector<int> c;
for(int i = 0; i < a.size(); i++) {
t += a[i];
if(i < b.size()) t += b[i];
c.push_back(t % 10);
t /= 10;
}
if(t) c.push_back(t);
return c;
}
|
作用：实现两个大整数（用vector存储，低位在前）的加法运算
高精度减法
1
2
3
4
5
6
7
8
9
10
11
12
| vector<int> sub(vector<int> &a, vector<int> &b) {
int t = 0;
vector<int> c;
for(int i = 0; i < a.size(); i++) {
t = a[i] - t;
if(i < b.size()) t -= b[i];
c.push_back((t + 10) % 10);
t = t < 0 ? 1 : 0;
}
while(c.size() > 1 && c.back() == 0) c.pop_back();
return c;
}
|
作用：实现两个大整数（用vector存储，低位在前）的减法运算。
数论
欧拉筛法
1
2
3
4
5
6
7
8
9
10
11
| void euler(int n) {
vector<int> prime;
vis[0] = vis[1] = true;
for(int i = 2; i <= n; i++) {
if(!vis[i]) prime.push_back(i);
for(int j = 0; j < prime.size() && i * prime[j] <= n; j++) {
vis[i * prime[j]] = true;
if(i % prime[j] == 0) break;
}
}
}
|
作用：使用欧拉筛法（线性筛）求出1到n之间的所有质数，并标记合数。
快速幂
1
2
3
4
5
6
7
8
9
| int qmi(int a, int b, int p) {
int res = 1;
while(b) {
if(b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
|
作用：快速计算a的b次方模p的结果。
逆元
1
2
3
| int inv(int x, int p) {
return qmi(x, p - 2, p);
}
|
作用：利用费马小定理计算x在模p意义下的逆元（p必须是质数）
最大公约数 最小公倍数
1
2
3
4
5
6
7
| int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int lcm(int a, int b) {
return a / gcd(a, b) * b;
}
|
图论
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
| typedef pair<int, int> PII;
priority_queue<PII, vector<PII>, greater<PII>> pq;
vector<int> dijkstra(int n, vector<vector<int>>& edges, int start) {
vector<vector<PII>> adj(n);
for (auto& edge : edges) {
int u = edge[0], v = edge[1], w = edge[2];
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
vector<int> dist(n, INT_MAX);
dist[start] = 0;
priority_queue<PII, vector<PII>, greater<PII>> pq;
pq.emplace(0, start);
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u])continue;
for (auto& [v, weight] : adj[u]) {
int new_dist = d + weight;
if (new_dist < dist[v]) {
dist[v] = new_dist;
pq.emplace(new_dist, v);
}
}
}
return dist;
}
|
作用：使用优先队列优化的Dijkstra算法求解单源最短路径问题（适用于非负权图）。
链式前向星
1
2
3
4
5
6
7
8
9
10
11
| struct node {
int next, to, w;
} e[100000];
int head[1000], cnt = 0;
void add_edge(int u, int v, int w) {
e[cnt].to = v;
e[cnt].w = w;
e[cnt].next = head[u];
head[u] = cnt++;
}
|
作用：使用链式前向星存储图结构，适用于稀疏图
单调栈与单调队列
单调栈
1
2
3
4
5
6
7
8
9
10
11
12
| stack<int> s;
int f[N], a[N];
void compare() {
for(int i = n; i >= 1; i--) {
while(!s.empty() && a[s.top()] <= a[i]) {
s.pop();
}
f[i] = s.empty() ? 0 : s.top();
s.push(i);
}
}
|
作用：使用单调栈找到每个元素右边第一个比它大的元素的位置。
单调队列（滑动窗口）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| int que1[N], hh = 0, tt = 0;
int ans1[N];
void sliding_window() {
for(int i = 1; i <= k - 1; i++) {
while(hh < tt && a[que1[tt - 1]] <= a[i]) {
tt--;
}
que1[tt++] = i;
}
for(int l = 1, r = k; l <= n - k + 1; l++, r++) {
while(hh < tt && a[que1[tt - 1]] <= a[r]) {
tt--;
}
que1[tt++] = r;
ans1[l] = a[que1[hh]];
if(que1[hh] == l) {
hh++;
}
}
}
|
作用：使用单调队列解决滑动窗口最大值问题。
并查集
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| int father[N];
int find(int x) {
if(x != father[x]) {
father[x] = find(father[x]);
}
return father[x];
}
bool isSameSet(int x, int y) {
return find(x) == find(y);
}
void unionSet(int x, int y) {
father[find(x)] = find(y);
}
|
作用：实现并查集数据结构，支持查找和合并操作，用于处理不相交集合的合并与查询问题。
搜索算法
BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| PII q[N];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
bool check(int a, int b) {
if(a < 1 || a > n || b < 1 || b > m) {
return false;
}
return true;
}
void bfs() {
while(hh <= tt) {
auto t = q[hh++];
for(int i = 0; i < 4; i++) {
int a = t.first + dx[i];
int b = t.second + dy[i];
if(!check(a, b) || dis[a][b] >= 0) continue;
dis[a][b] = dis[t.first][t.second] + 1;
q[++tt] = {a, b};
}
}
}
|
作用：广度优先搜索算法，用于解决最短路径或连通性问题。
DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| int d[N], p1, p2;
void dfs(int x, int fa) {
if(d[p1] < d[x]) {
p1 = x;
}
for(auto y : point[x]) {
if(y == fa) continue;
d[y] = d[x] + 1;
dfs(y, x);
}
}
void dfs1(int x, int fa) {
if(d1[p2] < d1[x]) {
p2 = x;
}
for(auto y : point[x]) {
if(y == fa) continue;
d1[y] = d1[x] + 1;
dfs1(y, x);
}
}
|
作用：使用两次深度优先搜索求解树的直径（树中最长路径）。第一次DFS找到最远点p1，第二次从p1出发找到最远点p2，p1和p2之间的路径即为树的直径。