来自算法基础课
快速排序，$O(nlog(n))$
void quick_sort(int q[], int l, int r){
if(l >= r)
return;
int x = q[(l + r) >> 1], i = l - 1, j = r + 1; // 划分，将大于等于x的数放到左边，小于等于x的数放在右边
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); // 右边排序
}
用快速排序求出第k个数，$O(n)$
int quick_sort(int q[], int l, int r, int k){
if(l == r)
return q[l];
int x = q[l + r >> 1], i = l - 1, j = r + 1; // 划分，将大于等于x的数放到左边，小于等于x的数放在右边
while(i < j){
do i ++; while(q[i] < x);
do j --; while(q[j] > x);
if(i < j)
swap(q[i], q[j]);
}
int sl = j - l + 1; // 看左边还有多少个数
if(k <= sl) // k在左边
return quick_sort(q, l, j, k);
else // k在右边
return quick_sort(q, j + 1, r, k - sl);
}
归并排序，$O(nlog(n))$
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 i = l, j = mid + 1, k = l;
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 x = l; x <= r; x ++)
q[x] = tmp[x];
}
用归并排序求逆序对，$O(nlog(n))$
long long merge_sort(int q[], int l, int r){
if(l >= r)
return 0;
int mid = l + r >> 1;
long long res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r); // 左边和右边组内的逆序对个数
int i = l, j = mid + 1, k = l;
while(i <= mid && j <= r)
if(q[i] <= q[j])
tmp[k ++] = q[i ++];
else{
tmp[k ++] = q[j ++];
res += mid - i + 1; // 若q[i] > q[j]，则q[r] >= q[r - 1] >= … >= q[j] > q[i], 也就是说(i, r)， (i, r - 1), …, (i, j) 都能构成逆序对, 一共有 mid - i + 1 个逆序对
}
while(i <= mid)
tmp[k ++] = q[i ++];
while(j <= r)
tmp[k ++] = q[j ++];
for(int x = l; x <= r; x ++)
q[x] = tmp[x];
return res;
}
整数二分算法模板
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 表示精度，取决于题目对精度的要求， 一般取精度的1 / 100
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){
vector<int> C;
int t = 0;
for(int i = 0; i < A.size() || i < B.size(); i ++){
if(i < A.size()) // 如果A里面还有数
t += A[i];
if(i < B.size()) // 如果B里面还有数
t += B[i];
C.push_back(t % 10); // 取t的个位
t /= 10;
}
if(t) // 如果还有进位
C.push_back(t);
return C;
}
高精度减法
// C = A - B, 满足 A >= B, A >= 0, B >= 0
bool cmp(vector<int>& A, vector<int>& B){ // 判断A是否>=B
if(A.size() != B.size()) // 先比较A和B的位数
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;
int t = 0;
for(int i = 0; i < A.size(); i ++){
t = A[i] - t;
if(i < B.size()) // 如果B里面还有数
t -= B[i];
C.push_back((t + 10) % 10); // 若t < 0, 就应该取(t + 10), 否则，取t, 合并起来就是((t + 10) % 10)
if(t < 0) // 如果有借位
t = 1;
else
t = 0;
}
while(C.size() > 1 && C.back() == 0) // 处理前导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()) // 如果A还有数
t += A[i] * b; // t += 这一位的数 * b
C.push_back(t % 10);
t /= 10;
}
return C;
}
高精度除以低精度
// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int>& A, int& b, int& r){ // 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) // 去除前导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
双指针算法，将时间复杂度$ O(n ^ 2) $的暴力降低到$ O(n) $
for (int i = 0, j = 0; i < n; i ++ ){
while (j < i && check(i, j))
j ++ ; // 很重要的一句话，表明了单调性
// 具体问题的逻辑
}
常见问题分类：
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<pair<int, int> > &segs){ // 求出合并后共有多少个区间
vector<pair<int, int> > 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;
}
牛逼
orz
牛逼