共计 3306 个字符，预计需要花费 9 分钟才能阅读完成。
内容目录
排序
- 快速排序
- 归并排序
快速排序
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]) temp[k++] = q[i++];
else temp[k++] = q[j++];
while(i <= mid) temp[k++] = q[i++];
while(j <= r) temp[k++] = q[j++];
for(int i=l,j=0;i<=r;i++,j++) q[i] = temp[j];
}二分
- 整数二分
- 浮点数二分
整数二分
bool check(int x) {
// 检查x是否满足某种性质
}
// 区间[l,r]被划分成[1,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){
// eps表示精度，取决于题目的要求
const double eps = 1e-8;
while(r - l > eps){
double mid = (l + r) /2;
if(check(mid)) r = mid;
else l = mid;
}
return l;
}高精度运算
- 高精度加法
- 高精度减法
- 高精度乘法
- 高精度除法
高精度加法
vector<int> add(vector<int>& A,vector<int>& B){
int t = 0;
vector<int> C;
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;
}高精度减法
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);
if(t < 0){
t = 1;
}else{
t = 0;
}
}
while(C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}高精度乘法
// A * b : A是大数，b是小数
vector<int> mul(vector<int> &A,int b){
int t = 0;
vector<int> C;
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 : A是大数，b是小数，C为商，r为余数
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.size() > 1 && C.back() == 0) C.pop_back();
return C;
}前缀和
- 一维前缀和
- 二维前缀和
一维前缀和
// 求数组a中[l,r]区间的元素和
// 为方便处理，下标从1开始进行处理
s[i] = a[1] + a[2] + ... + a[i]
a[l] + ... + a[r] = s[r] - s[l-1]二维前缀和
// 给定二维数组a[i][j],求以(x1,y1)为左上角,(x2,y2)为右下角的子矩阵和
// 下标从1开始处理
s[i][j] = 坐标(i,j)的左上部分的所有元素和
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[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
b[x1][y1] += c;
b[x2 + 1][y1] -= c;
b[x1][y2 + 1] -= c;
b[x2 + 1][y2 + 1] += c;双指针
for(int i = 0, j = 0; i < n; i++){
while( j <= i && check(i,j) ) j++;
/*
* 对于题目的具体逻辑处理
*/
}
常见问题分类：
(1) 对于一个序列，用两个指针维护一段区间
(2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作位运算
x的二进制第k位
// 1. 将二进制数x右移k位：res = x >> k
// 2. 将结果对1进行取与运算: res = res & 1
// 合起来：
res = x >> k & 1;lowbit(x) 运算
// lowbit(x)：返回x的最后一位1及其之后的数据
// x = 42(十进制) = 101010(二进制)
// lowbit(x) = 10(二进制) = 2(十进制)
res = x & -x;可以使用$lowbit(x)$运算求$x$二进制表示中有几个1：
// ans: x的二进制表示中1的个数
int ans = 0;
while(x){
x -= lowbit(x);
ans++;
}
离散化
// 将alls数组中的元素映射到[1 , ... , alls.size()]
// 去重
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());
// return: x的映射后的值
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 l + 1;
}区间合并
void merge(vector<PII> &segs){
vector<PII> res;
// 依据左端点进行排序
sort(segs.begin(),segs.end());
// 起始区间为负无穷
int st = -2e9, ed = -2e9;
for(auto seg: segs){
if(seg.first > ed){
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;
}正文完
