快速排序
思想
快排利用了分治算法，分治算法通常包含三步：
- 分成子问题
- 递归处理子问题
- 子问题合并
快排的操作是选取一个基准数 x，保证该数在数组中左边都比它小，右边都比它大。利用两个指针 i，j 分别放在首尾，当 i 走到第一个比 x 大的数停下，j 找到第一个比 x 小的数停下，交换位置。直到 i >= j 时，x 左边都是比它小的数，右边都是比它大的数。然后分治，将区间换成两个小区间继续操作。
模板展示
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N];
void quick_sort(int a[], int l, int r) {
if (l >= r) return;
int i = l - 1, j = r + 1;
int x = a[(l + r) >> 1];
while (i < j) {
do i++; while (a[i] < x);
do j--; while (a[j] > x);
if (i < j) swap(a[i], a[j]);
}
quick_sort(a, l, j);
quick_sort(a, j + 1, r);
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
quick_sort(a, 0, n - 1);
for (int i = 0; i < n; i++) printf("%d ", a[i]);
return 0;
}
注意
需要注意 x 的取值以及递归的划分区域 quick_sort(a, l, j) 和 quick_sort(a, j + 1, r)。
这里区域取的是 l, j 和 j + 1。如果 x 取 a[r]，右边的第一个元素可能直接停止，导致 j 停在 r 位置。若左边元素都比 a[r] 小，i 移动到 r 结束循环，此时 i = r, j = r。递归区域为 l, r 和 r+1，r 区域为空直接 return，而 l, r 依旧没变，会导致死循环。
所以当用 j 进行划分区域时不能选用 a[r]，反之用 i 划分就不能用 a[l]。
建议背下这个模板，理解算法思想后手敲代码 3-5 次来记忆。
归并排序
思想
将区间分为两部分进行排序，依旧利用分治，递归之后进行合并。
模板展示
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N], tmp[N];
void merge_sort(int a[], int l, int r) {
if (l >= r) return;
int mid = (l + r) >> 1;
merge_sort(a, l, mid);
merge_sort(a, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r) {
if (a[i] < a[j]) tmp[k++] = a[i++];
else tmp[k++] = a[j++];
}
while (i <= mid) tmp[k++] = a[i++];
while (j <= r) tmp[k++] = a[j++];
for (k = 0, i = l; i <= r; i++, k++) a[i] = tmp[k];
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
merge_sort(a, 0, n - 1);
for (int i = 0; i < n; i++) printf("%d ", a[i]);
;
}
二分
分为整数二分和浮点数二分。
详解
二分需要有单调性，本质是寻找满足某性质的边界点。我们将 [l, r] 区间一分为二，绿色和红色分别代表两个性质。中间有空隙是因为这是整数二分。我们要找的是某个性质的边界。
第一个模板，找绿色的边界。取 mid = (l + r) / 2，如果满足绿色性质说明 mid 在绿色区域，则 l = mid；如果不满足说明 mid 在红色区域，则 r = mid - 1。注意如果是 l = mid，mid 应该等于 (l + r + 1) / 2，防止 l = r - 1 时下取整导致死循环。
第二个模板，找红色的边界。取 mid = (l + r) / 2，如果满足红色性质说明 mid 在红色区域，则 r = mid；如果不满足说明 mid 在绿色区域，则 l = mid + 1。
所谓的性质其实就是二分答案写的 check 函数。
示例
以 AcWing 789 数的范围为例，找一个数组中某个数的起始位置和终止位置。
找起始位置，性质是 >= x。如果 mid >= x，r = mid，否则 l = mid + 1。 找终止位置，性质是 <= x。如果 mid <= x，l = mid，否则 r = mid - 1。
代码展示
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int n, q, a[N];
int main() {
cin >> n >> q;
for (int i = 0; i < n; i++) cin >> a[i];
while (q--) {
int x;
cin >> x;
int l = 0, r = n - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (a[mid] < x) l = mid + 1;
else r = mid;
}
if (a[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 (a[mid] <= x) l = mid;
else r = mid - 1;
}
cout << l << endl;
}
}
return 0;
}
高精度
遇到很大的数加减乘除时用到高精度，让数存进数组，用代码实现算术运算。
高精度加法
#include <iostream>
#include <vector>
using namespace std;
vector<int> add(vector<int> &A, vector<int> &B) {
vector<int> C;
int t = 0;
for (int i = 0; i < A.size() || i < B.size(); i++) {
if (i < A.size()) t += A[i];
if (i < B.size()) t += B[i];
C.push_back(t % 10);
t /= 10;
}
if (t) C.push_back(1);
return C;
}
int main() {
string a, b;
vector<int> A, B;
cin >> a >> b;
for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
auto C = add(A, B);
for ( i = C.() - ; i >= ; i--) (, C[i]);
;
}
数字存入数组后，小位放小索引（如 123456 变成 6 5 4 3 2 1）。加法进位逻辑同上。
高精度减法
重点是判断两个数谁大，因为要判断答案是否为负数。
先写 cmp 函数判断大小。如果长度不一样，直接返回 A.size() > B.size()。如果长度相同，倒着判断找到第一个不一样的高位，返回 A[i] > B[i]。最后如果都一样说明一样大，返回 true。
减法操作让 A 作为大数，t = A[i] - t（t 是被借走的位数），当前 a[i] 减去 t。同时利用 t 记录值，看 B 是否遍历结束，让 t -= B[i]。操作结束后 (t + 10) % 10，如果相减是负数说明借了一位，t = 1，反之为 0。
#include <iostream>
#include <vector>
using namespace std;
bool cmp(vector<int> &A, vector<int> &B) {
if (A.size() != B.size()) return A.size() > B.size();
for (int i = A.size() - 1; i >= 0; i--) {
if (A[i] != B[i]) return A[i] > B[i];
}
return true;
}
vector<int> sub(vector<int> &A, vector<int> &B) {
vector<int> C;
for (int i = 0, t = 0; i < A.size() || i < B.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.back() == 0 && C.size() > ) C.();
C;
}
{
string a, b;
vector<> A, B;
cin >> a >> b;
( i = a.() - ; i >= ; i--) A.(a[i] - );
( i = b.() - ; i >= ; i--) B.(b[i] - );
((A, B)) {
C = (A, B);
( i = C.() - ; i >= ; i--) (, C[i]);
} {
C = (B, A);
();
( i = C.() - ; i >= ; i--) (, C[i]);
}
;
}
高精度乘法
讲一个大数乘一个小数。用 t 表示值，重点是循环条件和前导零。
循环条件为 i < A.size() || t，因为 t 最后如果有进位还要继续操作。 乘法结束后如果答案是 0000，要去掉前导零变为 0。
#include <iostream>
#include <vector>
using namespace std;
vector<int> mul(vector<int>& A, int b) {
vector<int> C;
for (int i = 0, t = 0; i < A.size() || t; i++) {
if (i < A.size()) t = A[i] * b + t;
C.push_back(t % 10);
t /= 10;
}
while (C.back() == 0 && C.size() > 1) C.pop_back();
return C;
}
int main() {
string a;
int b;
cin >> a >> b;
vector<int> A;
for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
auto C = mul(A, b);
for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
return 0;
}
高精度除法
大数除以一个小数。用 r 作为余数，去掉前导零。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> div(vector<int>& A, int b, int &r) {
r = 0;
vector<int> C;
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.back() == 0 && C.size() > 1) C.pop_back();
return C;
}
int main() {
string a;
int b;
cin >> a >> b;
vector<int> A;
for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
int r;
auto C = div(A, b, r);
for (int i = C.size() - ; i >= ; i--) (, C[i]);
cout << << r;
;
}
双指针
双指针优化 O(n^2) 算法成 O(n)。
一般形式：
for (int i = 0, j = 0; i < n; i++) {
while (j < i && check(i, j)) j++;
// 剩下的操作就是看题目要求了
}
例子：找到一段序列最长的不包含重复数字的序列。 朴素算法 O(n^2)，check 判断是否有重复，i 指向序列末端，j 指向起始位置。 双指针算法：j 指向起始位置，当发现 i 位置的值出现次数 > 1，j 就移动直到 i 位置不大于 1。
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, a[N], s[N], res;
int main() {
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;
}
位运算
常见用法： (l + r) >> 1 相当于除以 2。 if (x & 1) 判断奇偶，奇数为 1，偶数为 0。
判断二进制中 1 的个数：一直拿第一位看，if(x & 1) num++，然后 x 右移一位。
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
int num = 0;
while (x) {
if (x & 1) num++;
x >>= 1;
}
cout << num << ' ';
}
return 0;
}
使用 lowbit 操作，每次截取最后一个 1 后面的所有位，减去 lowbit 得到的数字，直到减到 0。 lowbit 原理：根据补码特点，x & (-x) 得到最低位的 1。
#include <iostream>
using namespace std;
int lowbit(int x) {
return x & (-x);
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
int res = 0;
while (x) {
x -= lowbit(x);
res++;
}
cout << res << ' ';
}
return 0;
}
离散化
离散化用于值域很大但数据量较小的情况。例如值域 0 到 1e9，数据长度 1e5，无法开大数组，可将这 1e5 个数映射到从 0 开始的数组。
例题：求区间和，但在 x 位置加 c，x 范围达 1e9。将所有涉及的 x、l、r 都 push_back 进容器 alls，排序去重。遍历 add 数组，利用二分查找找到映射后的位置，对前缀和数组操作。最后遍历查询区间，找到 l、r 映射位置，计算前缀和差值。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 3e5;
int n, m, 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) l = mid + 1;
else r = mid;
}
return l + 1;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
int x, c;
scanf("%d%d", &x, &c);
add.push_back({x, c});
alls.push_back(x);
}
for (int i = 0; i < m; i++) {
int l, r;
scanf(, &l, &r);
query.({l, r});
alls.(l);
alls.(r);
}
(alls.(), alls.());
alls.((alls.(), alls.()), alls.());
( item : add) {
x = (item.first);
a[x] += item.second;
}
( i = ; i <= alls.(); i++) s[i] = s[i - ] + a[i];
( item : query) {
l = (item.first), r = (item.second);
cout << s[r] - s[l - ] << endl;
}
;
}
区间合并
这类问题较常见，把代码看懂即可。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
typedef pair<int, int> Pii;
vector<Pii> segs;
int n;
void merge() {
vector<Pii> res;
int st = -0x3f3f3f3f, ed = -0x3f3f3f3f;
for (auto seg : segs) {
if (ed < seg.first) {
if (ed != -0x3f3f3f3f) res.push_back({st, ed});
st = seg.first, ed = seg.second;
} else {
ed = max(ed, seg.second);
}
}
if (st != -0x3f3f3f3f) res.push_back({st, ed});
segs = res;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
int l, r;
cin >> l >> r;
segs.push_back({l, r});
}
sort(segs.begin(), segs.end());
merge();
cout << segs.size();
return ;
}
