❤ 作者主页: 欢迎来到我的技术博客😎
❀ 个人介绍:大家好,本人热衷于 Java后端开发,欢迎来交流学习哦!( ̄▽ ̄)~*
🍊 如果文章对您有帮助,记得 关注、 点赞、 收藏、 评论⭐️⭐️⭐️
📣 您的支持将是我创作的动力,让我们一起加油进步吧!!!🎉🎉
前言
所有的模板题都可以在acwing题库中搜到。
一、快速排序
思路:基于分治思想
- 确定分界点(随机取任意一个数为分界点,一般取中点);
- 调整区间,把小于
x
的数移到左边,把大于x
的数移到右边,把区间分为[l, j]
、[j + 1, r]
; - 递归左右。
1. 快速排序算法模板
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
2. 快速排序模板题(1):快速排序
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int q[N];
void quick_sort(int q[], int l, int r)
{
if(l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while(i < j)
{
do i ++; while(q[i] < x);
do j --; while(q[j] > x);
if(i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i ++) cin >> q[i];
quick_sort(q, 0, n - 1);
for(int i = 0; i < n; i ++ ) printf("%d ", q[i]);
return 0;
}
3.快速排序算法模板题(2):第k个数
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int q[N];
int quick_sort(int q[], int l, int r, int k)
{
if(l >= r) return q[l];
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while(i < j)
{
do i ++; while(q[i] < x);
do j --; while(q[j] > x);
if(i < j) swap(q[i], q[j]);
}
if(j - l + 1 >= k) return quick_sort(q, l, j , k);
else return quick_sort(q, j + 1, r, k - (j - l + 1));
}
int main()
{
int n, k;
cin >> n >> k;
for(int i = 0; i < n; i ++ ) cin >> q[i];
cout << quick_sort(q, 0, n - 1, k) << endl;
return 0;
}
二、归并排序
思路:
- 取数组的中间数作为分界点;
- 将分界点左右两边分别排好序;
- 将左右两边进行合并。
1. 归并排序算法模板
void merge_sort(int q[], int l, int r)
{
if (l >= r) return;
int mid = l + r >> 1;
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
else tmp[k ++ ] = q[j ++ ];
while (i <= mid) tmp[k ++ ] = q[i ++ ];
while (j <= r) tmp[k ++ ] = q[j ++ ];
for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
2. 归并排序模板题(1):归并排序
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int q[N], tmp[N];
void memset_sort(int q[], int l, int r)
{
if(l >= r) return;
int mid = l + r >> 1;
memset_sort(q, l, mid), memset_sort(q, mid + 1, r);
int k = 0, i = l , j = mid + 1;
while(i <= mid && j <= r)
if(q[i] <= q[j]) tmp[k ++ ] = q[i ++];
else tmp[k ++ ] = q[j ++];
while(i <= mid) tmp[k ++ ] = q[i ++];
while(j <= r) tmp[k ++ ] = q[j ++];
for(int i = l, j = 0; i <= r; i ++ , j ++ ) q[i] = tmp[j];
}
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i ++ ) cin >> q[i];
memset_sort(q, 0, n - 1);
for(int i = 0; i < n; i ++ ) printf("%d ", q[i]);
return 0;
}
3. 归并排序模板题(2):逆序对的数量
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;
int q[N], tmp[N];
LL memset_sort(int q[], int l, int r)
{
if(l >= r) return 0;
int mid = l + r >> 1;
LL res = memset_sort(q, l, mid) + memset_sort(q, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while(i <= mid && j <= r)
if(q[i] <= q[j]) tmp[k ++ ] = q[i ++];
else
{
res += mid - i + 1;
tmp[k ++ ] = q[j ++];
}
while(i <= mid) tmp[k ++ ] = q[i ++];
while(j <= r) tmp[k ++ ]= q[j ++];
for(int i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
return res;
}
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i ++) cin >> q[i];
cout << memset_sort(q, 0, n - 1) << endl;
return 0;
}
三、二分
思路:
本质:可以划分为满足某种性质与不满足某种性质的两个区间,用二分法可以找到两区间边界的左右两个点。
1. 整数二分算法模板
bool check(int x) {/* ... */} // 检查x是否满足某种性质
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
2. 整数二分算法模板题:数的范围
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m;
int q[N];
int main()
{
cin >> n >> m;
for(int i = 0; i < n; i ++ ) cin >> q[i];
while(m -- )
{
int x;
cin >> x;
int l = 0, r = n - 1;
while(l < r)
{
int mid = l + r >> 1;
if(q[mid] >= x) r = mid;
else l = mid + 1;
}
if(q[l] != x) cout << "-1 -1" << endl;
else
{
cout << l << ' ';
int l = 0, r = n - 1;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(q[mid] <= x) l = mid;
else r = mid - 1;
}
cout << l << endl;
}
}
return 0;
}
3. 浮点数二分算法模板
bool check(double x) {/* ... */} // 检查x是否满足某种性质
double bsearch_3(double l, double r)
{
const double eps = 1e-6; // eps 表示精度,取决于题目对精度的要求
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}
4. 浮点数二分算法模板题: 数的三次方根
#include <bits/stdc++.h>
using namespace std;
int main()
{
double x;
cin >> x;
double l = -100, r = 100;
while(r - l > 1e-8)
{
double mid = (l + r) / 2;
if(mid * mid * mid >= x) r = mid;
else l = mid;
}
printf("%.6lf\n", l);
return 0;
}
四、高精度
1. 高精度加法模板
/ C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
if (A.size() < B.size()) return add(B, A);
vector<int> C;
int t = 0;
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;
}
2. 高精度减法模板
// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
vector<int> C;
for (int i = 0, t = 0; i < A.size(); i ++ )
{
t = A[i] - t;
if (i < B.size()) t -= B[i];
C.push_back((t + 10) % 10);
if (t < 0) t = 1;
else t = 0;
}
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
3. 高精度乘低精度模板
// C = A * b, A >= 0, b >= 0
vector<int> mul(vector<int> &A, int b)
{
vector<int> C;
int t = 0;
for (int i = 0; i < A.size() || t; i ++ )
{
if (i < A.size()) t += A[i] * b;
C.push_back(t % 10);
t /= 10;
}
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
4. 高精度除以低精度算法
// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &r)
{
vector<int> C;
r = 0;
for (int i = A.size() - 1; i >= 0; i -- )
{
r = r * 10 + A[i];
C.push_back(r / b);
r %= b;
}
reverse(C.begin(), C.end());
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
五、前缀和与差分
1. 一维前缀和模板
S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]
一维前缀和模板题:前缀和
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m;
int a[N], s[N];
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++ ) cin >> a[i];
for(int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i];
while(m -- )
{
int l, r;
cin >> l >> r;
printf("%d\n", s[r] - s[l - 1]);
}
return 0;
}
2. 二维前缀和模板
S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵的和为:
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]
二维前缀和模板题:子矩阵的和
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m, q;
int s[N][N];
int main()
{
cin >> n >> m >> q;
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= m; j ++ )
cin >> s[i][j];
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= m; j ++ )
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
while(q -- )
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 -1] + s[x1 - 1][y1 - 1]);
}
return 0;
}
3. 一维差分模板
给区间[l, r]中的每个数加上c:B[l] += c, B[r + 1] -= c
一维差分模板题:差分
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m;
int a[N], b[N];
void insert(int l, int r, int c)
{
b[l] += c;
b[r + 1] -= c;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++ ) cin >> a[i];
for(int i = 1; i <= n; i ++ ) insert(i, i, a[i]);
while(m -- )
{
int l, r, c;
cin >> l >> r >> c;
insert(l, r, c);
}
for(int i = 1; i <= n; i ++ ) b[i] += b[i - 1];
for(int i = 1; i <= n; i ++ ) printf("%d ", b[i]);
return 0;
}
4. 二维差分模板
给以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵中的所有元素加上c:
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c
二维差分模板题:差分矩阵
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m, q;
int a[N][N], b[N][N];
void insert(int x1, int y1, int x2, int y2, int c)
{
b[x1][y1] += c;
b[x2 + 1][y1] -= c;
b[x1][y2 + 1] -= c;
b[x2 + 1][y2 + 1] += c;
}
int main()
{
cin >> n >> m >> q;
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= m; j ++ )
cin >> a[i][j];
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= m; j ++ )
insert(i, j, i, j, a[i][j]);
while(q -- )
{
int x1, y1, x2, y2, c;
cin >> x1 >> y1 >> x2 >> y2 >> c;
insert(x1, y1, x2, y2, c);
}
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= m; j ++ )
b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
for(int i = 1; i <= n; i ++ )
{
for(int j = 1; j <= m; j ++ ) printf("%d ", b[i][j]);
puts("");
}
return 0;
}
六、双指针
常见问题分类:
- 对于一个序列,用两个指针维护一段区间
- 对于两个序列,维护某种次序,比如归并排序中合并两个有序序列的操作
1. 双指针算法模板
for (int i = 0, j = 0; i < n; i ++ )
{
while (j < i && check(i, j)) j ++ ;
// 具体问题的逻辑
}
2. 双指针算法模板题(1):最长连续不重复子序列
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
int q[N], s[N];
int main()
{
cin >> n;
for(int i = 0; i < n; i ++ ) cin >> q[i];
int res = 0;
for(int i = 0, j = 0; i < n; i ++ )
{
s[q[i]] ++;
while(j < i && s[q[i]] > 1) s[q[j ++ ]] --;
res = max(res, i - j + 1);
}
cout << res << endl;
return 0;
}
3. 双指针算法模板题(2):数组元素的目标和
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, x;
int a[N], b[N];
int main()
{
cin >> n >> m >> x;
for(int i = 0; i < n; i ++ ) cin >> a[i];
for(int i = 0; i < m; i ++ ) cin >> b[i];
for(int i = 0, j = m - 1; i < n; i ++ )
{
while(j >= 0 && a[i] + b[j] > x) j --;
if(j >= 0 && a[i] + b[j] == x) cout << i << ' ' << j << endl;
}
return 0;
}
4. 双指针算法模板题(3):判断子序列
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int a[N], b[N];
int main()
{
cin >> n >> m;
for(int i = 0; i < n; i ++ ) cin >> a[i];
for(int i = 0; i < m; i ++ ) cin >> b[i];
int i = 0, j = 0;
while(i < n && j < m)
{
if(a[i] == b[j]) i ++;
j ++;
}
if(i == n) puts("Yes");
else puts("No");
return 0;
}
七、位运算
1. 位运算算法模板
求n的第k位数字: n >> k & 1
返回n的最后一位1:lowbit(n) = n & -n,如101000得1000
2. 位运算模板题:二进制中1的个数
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
while(n -- )
{
int x, s = 0;
cin >> x;
for(int i = x; i; i -= i & -i) s ++;
printf("%d ", s);
}
return 0;
}
八、离散化
场景:目标数据稀疏的分散在大数组空间中,大部分元素为0。
思路:
- 首先取操作涉及的下标,即将要存数字的下标与求和范围两端的下标,存入小数组q中;
- 对数组q排序;
- 重新创建一个大小与q相同的数组s,从数组q中找到对应大数组要存入数据的位置映射,在s相同位置存入数据(q中找映射可以用二分法);
- 找大数组求和范围两端点在q中的映射位置,在数组s对应映射位置求和即可,可用前缀和.
1. 离散化算法模板
vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去掉重复元素
// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
int l = 0, r = alls.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (alls[mid] >= x) r = mid;
else l = mid + 1;
}
return r + 1; // 映射到1, 2, ...n
}
2. 离散化算法模板题:区间和
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 300010;
int n, m;
int a[N], s[N];
vector<int> alls;
vector<PII> add, query;
int find(int x)
{
int l = 0, r = alls.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (alls[mid] >= x) r = mid;
else l = mid + 1;
}
return r + 1;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++ )
{
int x, c;
cin >> x >> c;
add.push_back({x, c});
alls.push_back(x);
}
for (int i = 0; i < m; i ++ )
{
int l, r;
cin >> l >> r;
query.push_back({l, r});
alls.push_back(l);
alls.push_back(r);
}
// 去重
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
// 处理插入
for (auto item : add)
{
int x = find(item.first);
a[x] += item.second;
}
// 预处理前缀和
for (int i = 1; i <= alls.size(); i ++ ) s[i] = s[i - 1] + a[i];
// 处理询问
for (auto item : query)
{
int l = find(item.first), r = find(item.second);
cout << s[r] - s[l - 1] << endl;
}
return 0;
}
九、区间合并
场景:离散的区间,合并相交的区间
思路:
- 按区间的左端点排序;
- 从左到右扫描,维护一个当前区间(随着遍历,若相交则区间变长)
- 每次遍历的区间和当前区间有三种情况分类讨论:
(1)右端点小于当前区间右端点,当前区间不变;
(2)右端点大于当前区间右端点,当前区间变长;
(3)左端点大于当前区间右端点,将该区间置为当前区间;
1. 区间合并模板
// 将所有存在交集的区间合并
void merge(vector<PII> &segs)
{
vector<PII> res;
sort(segs.begin(), segs.end());
int st = -2e9, ed = -2e9;
for (auto seg : segs)
if (ed < seg.first)
{
if (st != -2e9) res.push_back({st, ed});
st = seg.first, ed = seg.second;
}
else ed = max(ed, seg.second);
if (st != -2e9) res.push_back({st, ed});
segs = res;
}
2. 区间合并模板题:区间合并
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
void merge(vector<PII> &segs)
{
vector<PII> res;
sort(segs.begin(), segs.end());
int st = -2e9, ed = -2e9;
for (auto seg : segs)
if (ed < seg.first)
{
if (st != -2e9) res.push_back({st, ed});
st = seg.first, ed = seg.second;
}
else ed = max(ed, seg.second);
if (st != -2e9) res.push_back({st, ed});
segs = res;
}
int main()
{
int n;
scanf("%d", &n);
vector<PII> segs;
for (int i = 0; i < n; i ++ )
{
int l, r;
scanf("%d%d", &l, &r);
segs.push_back({l, r});
}
merge(segs);
cout << segs.size() << endl;
return 0;
}
内容持续更新中,关注博主不迷路。