基础算法¶
一、快速排序¶
1、快速排序¶
- 找到分界点x，
arr[(l+r)/2] - 左边所有数
Left <= x，右边所有数Right >= x - 递归排序
Left，递归排序Right
/**
* @Date 2022/11/26 16:38
*/
#include "iostream"
using namespace std;
int arr[100005];
int n;
void sort(int l, int r) {
if (l >= r) return;
int ll = l, rr = r;
int m = arr[(l + r) / 2];
while (l < r) {
while (arr[l] < m) l++;
while (arr[r] > m) r--;
if (l > r) break;
swap(arr[l], arr[r]);
l++, r--;
}
sort(ll, r);
sort(l, rr);
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
sort(0, n - 1);
for (int i = 0; i < n; i++) {
if (i != n - 1) cout << arr[i] << " ";
else cout << arr[i] << endl;
}
return 0;
}
2、快速查找第K个数¶
- \(k <= 分界点\)：递归左边
- \(k > 分界点\)：递归右边
时间复杂度\(O(n)\)
/**
* @Date 2022/11/26 16:38
*/
#include "iostream"
using namespace std;
int arr[100005];
int n, k;
void sort(int l, int r) {
if (l >= r) return;
int ll = l, rr = r;
int m = arr[(l + r) / 2];
while (l < r) {
while (arr[l] < m) l++;
while (arr[r] > m) r--;
if (l > r) break;
swap(arr[l], arr[r]);
l++, r--;
}
// 选择一边递归
if (k <= r) sort(ll, r);
else sort(l, rr);
}
int main() {
cin >> n >> k;
k--;
for (int i = 0; i < n; i++) cin >> arr[i];
sort(0, n - 1);
cout << arr[k] << endl;
return 0;
}
二、归并排序¶
1、归并排序¶
- 确定分界点：
mid = (l + r) / 2 - 递归排序
- 归并合二为一：双指针
/**
* @Date 2022/12/14 22:05
*/
#include "iostream"
using namespace std;
const int N = 100005;
int arr[N], temp[N];
void merge_sort(int arr[], int l, int r) {
if (l >= r) return;
int mid = (l + r) >> 1;
merge_sort(arr, l, mid);
merge_sort(arr, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r) {
if (arr[i] < arr[j]) temp[k++] = arr[i++];
else temp[k++] = arr[j++];
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= r) temp[k++] = arr[j++];
for (k = 0, i = l; i <= r; k++, i++) arr[i] = temp[k];
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> arr[i];
merge_sort(arr, 0, n - 1);
for (int i = 0; i < n; i++) cout << arr[i] << " ";
return 0;
}
2、逆序对的个数¶
/**
* @Date 2023/4/17 20:12
*/
#include "iostream"
using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
int q[N];
int temp[N];
LL merge_sort(int l, int r) {
if (l >= r) return 0;
int mid = l + r >> 1;
LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);
// 归并排序
int x = l, y = mid + 1, z = 0;
while (x <= mid && y <= r) {
if (q[x] <= q[y]) temp[z++] = q[x++];
else {
temp[z++] = q[y++];
res += mid - x + 1;
}
}
while (x <= mid) temp[z++] = q[x++];
while (y <= r) temp[z++] = q[y++];
// 复制数组
for (int i = l, j = 0; i <= r; i++, j++) q[i] = temp[j];
return res;
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> q[i];
cout << merge_sort(0, n - 1) << endl;
return 0;
}
三、二分¶
1、数的范围¶
\(map\)的做法
/**
* @Date 2023/4/21 17:14
*/
#include <iostream>
#include <map>
using namespace std;
typedef pair<int, int> PII;
const int N = 100010;
int a[N];
map<int, PII> m;
int main() {
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
int t, num;
for (int i = 1; i <= n + 1; i++) {
if (a[i] != a[i - 1]) {
if (i != 1) m[num] = {i - t - 1, i - 2};
t = 0;
num = a[i];
}
t++;
}
for (int i = 0; i < q; i++) {
int temp, x = -1, y = -1;
cin >> temp;
if (m.count(temp)) {
x = m[temp].first;
y = m[temp].second;
}
cout << x << " " << y << endl;
}
return 0;
}
2、数的三次方根¶
/**
* @Date 2023/4/21 17:25
*/
#include <iostream>
using namespace std;
int main() {
double n;
scanf("%lf", &n);
double l = -10000, r = 10000, mid = 0;
while (1) {
mid = (l + r) / 2;
if (r - l < 1e-8) break;
if (mid * mid * mid > n) r = mid;
else l = mid;
}
printf("%.6lf\n", mid);
return 0;
}
五、前缀和与差分¶
1、前缀和¶
/**
* @Date 2023/4/17 21:42
*/
#include "iostream"
using namespace std;
const int N = 1e5 + 5;
int q[N];
int s[N];
int main() {
int m, n;
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> q[i];
for (int i = 1; i <= n; i++) s[i] = s[i - 1] + q[i];
while (m--) {
int l, r;
cin >> l >> r;
cout << s[r] - s[l - 1] << endl;
}
}
2、子矩阵的和¶
/**
* @Date 2023/4/18 10:53
*/
#include <iostream>
using namespace std;
const int N = 1005;
int q[N][N];
int s[N][N];
int main() {
int n,m,qq;
cin >> n >> m >> qq;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
cin >> q[i][j], s[i][j] = s[i - 1][j] + s[i][j - 1] + q[i][j] - s[i - 1][j - 1]; ;
while ( qq-- ) {
int x1,x2,y1,y2;
cin >> x1 >> y1 >> x2 >> y2;
x1--,y1--;
cout << s[x2][y2] - s[x1][y2] - s[x2][y1] + s[x1][y1] << endl;
}
return 0;
}
3、差分¶
/**
* @Date 2023/4/18 11:05
*/
#include <iostream>
using namespace std;
const int N = 1e5+5;
int q[N],b[N];
int main() {
int n,m;
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> q[i];
while (m --) {
int l,r,c;
cin >> l >> r >> c;
b[l] += c, b[r + 1] += -c;
}
for (int i = 1; i <= n; i ++ ) b[i] += b[i - 1];
for (int i = 1; i <= n; i ++ ) cout << q[i] + b[i] << " ";
return 0;
}
4、差分矩阵¶
b[x1][y1] += c：对应图1 ,让整个a数组中蓝色矩形面积的元素都加上了c。b[x1][y2 + 1] -= c：对应图2 ，让整个a数组中绿色矩形面积的元素再减去c，使其内元素不发生改变。b[x2 + 1][y1] -= c：对应图3 ，让整个a数组中紫色矩形面积的元素再减去c，使其内元素不发生改变。b[x2 + 1][y2 + 1] += c：对应图4，让整个a数组中红色矩形面积的元素再加上c，红色内的相当于被减了两次，再加上一次c，才能使其恢复。
/**
* @Date 2023/4/18 11:29
*/
#include <iostream>
using namespace std;
const int N = 1e3 + 5;
int ma[N][N], b[N][N];
int main() {
int m, n, q;
cin >> n >> m >> q;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> ma[i][j];
while (q--) {
int x1, y1, x2, y2, c;
cin >> x1 >> y1 >> x2 >> y2 >> c;
b[x1][y1] += c;
b[x1][y2 + 1] -= c;
b[x2 + 1][y1] -= c;
b[x2 + 1][y2 + 1] += 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++) {
cout << ma[i][j] + b[i][j] << " ";
}
cout << endl;
}
return 0;
}
六、双指针算法¶
1、最长连续不重复子序列¶
/**
* @Date 2023/4/20 19:55
*/
#include <iostream>
using namespace std;
const int N = 1e5 + 3;
int a[N], s[N];
int res;
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0, j = 0; i < n; i++) {
s[a[i]]++;
while (s[a[i]] > 1) s[a[j]]--, j++;
res = max(res, i - j + 1);
}
cout << res;
return 0;
}
2、数组元素的目标和¶
/**
* @Date 2023/4/20 19:33
*/
#include <iostream>
using namespace std;
const int N = 1e5 + 5;
int a[N], b[N];
int main() {
int n, m, x;
scanf("%d%d%d", &n, &m, &x);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int i = 0; i < m; i++) scanf("%d", &b[i]);
int xx = 0, yy = m - 1;
while (1) {
if (a[xx] + b[yy] == x) {
cout << xx << " " << yy << endl;
break;
} else if (a[xx] + b[yy] > x) {
yy--;
} else {
// a[xx] + b[yy] < x
xx++;
}
}
return 0;
}
3、判断子序列¶
/**
* @Date 2023/4/18 19:04
*/
#include <iostream>
using namespace std;
const int N = 1e5 + 3;
int n, m;
int a[N], b[N];
bool solve() {
int x = 0, y = 0;
while (1) {
if (x == n) return true;
if (y == m) return false;
if (a[x] == b[y]) x++;
y++;
}
}
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];
if (solve()) cout << "Yes";
else cout << "No";
return 0;
}
七、位运算¶
1、二进制中1的个数¶
/**
* @Date 2023/4/18 15:01
*/
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
while (n--) {
int x;
cin >> x;
int ans = 0;
while (x) {
if (x & 1) ans++;
x = x >> 1;
}
cout << ans << " ";
}
return 0;
}
八、离散化¶
1、区间和¶
#include <iostream>
#include <algorithm>
#include <vector>
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;
}
// 因为要求前缀和，故下标从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());
/*
* 1）erase(pos, n); 删除从pos开始的n个字符，例如erase( 0, 1)，
* 删除0位置的一个字符，即删除第一个字符
*
* 2）erase(position);
* 删除position处的一个字符（position是个string类型的迭代器）
*
* 3）erase(first, last）; 删除从first到last之间的字符，
* (first和last都是迭代器) last 不能是x.end()
* unique 使用 必须要先过一遍sort排序。再者，unique函数返的返回值是
* 一个迭代器，它指向的是去重后容器中不重复序列的最后一个元素的
* 下一个元素。所以如果 想要得到不重复元素的个数就需要用返回值-开始地址。
*
* */
// 先对添加里的元素映射 赋值
for (auto item: add) {
// 找到x的映射值 往原数组中加c
int x = find(item.first);
// 处理插入
a[x] += item.second;
}
// for(auto a:b)中b为一个容器，效果是利用a遍历并获得b容器中的每一个值，
// 但是a无法影响到b容器中的元素。
// 前缀和
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;
}
// 每个元素都对应一组{first, first}键值对（pair），
// 键值对中的第一个成员称为first，第二个成员称为second.
return 0;
}
九、区间合并¶
1、区间合并¶
/**
* @Date 2023/4/21 17:44
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
vector<PII> v;
int ans;
int main() {
int n, l, r;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> l >> r;
v.push_back({l, r});
}
sort(v.begin(), v.end());
for (int i = 0; i < n; i++) {
PII p = v[i];
if (i == 0) {
l = p.x;
r = p.y;
} else {
if (p.x > r) {
l = p.x, r = p.y;
ans++;
} else if (p.y > r) {
r = p.y;
}
}
}
cout << ans + 1 << endl;
return 0;
}
补y总模板¶
作者：yxc 链接：https://www.acwing.com/blog/content/277/ 来源：AcWing 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
快速排序算法模板¶
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);
}
归并排序算法模板¶
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];
}
整数二分算法模板¶
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;
}
浮点数二分算法模板¶
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;
}
高精度加法¶
// 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;
}
高精度减法¶
// 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;
}
高精度乘低精度¶
// 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;
}
高精度除以低精度¶
// 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;
}
一维前缀和¶
S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]
二维前缀和¶
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]
一维差分¶
给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c
二维差分¶
给以(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
位运算¶
求n的第k位数字：n >> k & 1
返回n的最后一位1：lowbit(n) = n & -n
双指针算法¶
1. 对于一个序列，用两个指针维护一段区间 2. 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作离散化¶
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
}
区间合并¶
// 将所有存在交集的区间合并
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;
}