常用代码模板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);
}
归并排序算法模板
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];
}
整数二分算法模板
二分问题：有单调性一定可以用二分法来做，没有也不一定不行
//check的确定：
//二分点本质上是使命题p(x)成立的最大（或最小）的x
//则check函数就设置为p(x)成立
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;
}
浮点数二分算法模板
//误差经验值：
//误差为1e-x，x比要保留的小数点位数多2
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;
}
三分法
三分法是二分法的变种，他最基本的用途是求单峰函数的极值点。
算法学习笔记(62): 三分法 - 知乎 (zhihu.com)
P3382 【模板】三分法 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
// 求极大值
const double eps = 1e-8; // 比要求的位数多两位
while (r - l > eps)
{
double mid = (l + r) / 2;
double fl = f(mid - eps), fr = f(mid + eps);
if (fl < fr) l = mid;
else r = mid;
}
printf("%lf", l);
// 斜率二分，函数左增右减，则导数左正右负，导数用极小偏移量dx得到的斜率代替
// 求极大值
const double eps = 1e-7;
double df(double x)
{
double dx = eps;
double dy = f(x + dx) - f(x);
return dy / dx;
}
while (r - l > eps)
{
double mid = (l + r) / 2;
if (df(mid) > 0) l = mid;
else r = mid;
}
printf("%.5lf", l);
秦九韶算法
// 秦九韶算法求一元多项式的值
// coe[]中从高到低依次存储该 N 次函数的N + 1项（包括常数项）系数
double f(double x)
{
double ans = 0;
// 由高次系数开始
for (int i = 0; i <= n; i ++ )
ans = ans * x + coe[i];
return ans;
}
高精度加法
// C = A + B, A >= 0, B >= 0
//一般len(A)=1e6, len(B)=1e6
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
//一般len(A)=1e6, len(B)=1e6
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); //t>=0 res=t t<0, res=t+10; 合并得res=(t+10)%10;
if (t < 0) t = 1; //t<0 则借了1
else t = 0; //否则没有借位
}
while (C.size() > 1 && C.back() == 0) C.pop_back(); //因为c的长度与a相同，可能有前导零，要去掉
return C;
}
高精度乘低精度
// C = A * b, A >= 0, b >= 0
//一般len(A)<=1e6, a<=1e9
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;
}
高精度乘高精度
vector<int> mul(vector<int> &a, vector<int> &b)
{
vector<int> c(a.size() + b.size() + 1);
int t = 0;
for (int i = 0; i < a.size(); i++)
for (int j = 0; j < b.size(); j++)
c[i + j] += a[i] * b[j];
for (int i = 0; i < c.size(); i++)
c[i + 1] += c[i] / 10, c[i] %= 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数组从下标1开始存，S[0]=0
S[i] = S[i-1] + a[i] //i从1开始。
//把数组变成自身的前缀和
S[i] += S[i-1] //i从1开始
//求[l, r]的元素的和
a[l] + ... + a[r] = S[r] - S[l - 1]
二维前缀和
//a数组从（1，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]
//把数组变成自身的前缀和
S[i, j] += S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1]
//以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]
一维差分
//数组从下标1开始存
//给区间[l, r]中的每个数加上c：
B[l] += c, B[r + 1] -= c
二维差分
//数组从（1，1）开始存
//给以(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位数字: (从右往左由0开始数)
n >> k & 1
//返回n的最后一位1:
lowbit(n) = n & -n
双指针算法
//运用：先考虑暴力做法，在考察i，j是否有单调性，若有则简化
//核心：运用某种单调性的性质，将O(n^2)优化成O(n)
for (int i = 0, j = 0; i < n; i ++ )
{
while (j < i && check(i, j)) j ++ ; //j不减小,单调
// 具体问题的逻辑
}
/*常见问题分类：
(1) 对于一个序列，用两个指针维护一段区间(该区间满足某种性质)
(2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作*/
离散化
//一种特殊的哈希方式，要求保序（需要先排序去重），find()单调
//离散化处理的问题：下标范围有负数，或者下标范围超过1e6以上，下标个数小于下标范围，并且题目还要求按照下标的顺序做题
//离散化的本质就是不使用原来的绝对坐标，而是以每一个绝对坐标在所有坐标中的排位作为坐标使用，由于绝对坐标的范围大但个数少，就可以达到缩小坐标范围的效果
//注意：要一以贯之地使用一套坐标
vector<int> alls; // 存储所有待离散化的值
// 1.排序去重，为二分查找做准备
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去掉重复元素
// 2.二分求出x对应的离散化的值
// 通过二分，确定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，不加1则从下标0开始映射
}
区间合并
// 将所有存在交集的区间合并
//typedef pair<int, int> PII;
void merge(vector<PII> &segs)
{
vector<PII> res;
//pair中sort默认对first升序，当first相同时对second升序
sort(segs.begin(), segs.end());
int st = -2e9, ed = -2e9; //初始维护区间设为在负无穷的长度为0的区间
//[st, ed]是当前维护的区间
//遍历所有区间，最后维护的区间没存入res就会退出循环
for (auto seg : segs)
if (ed < seg.first) //当前扫描到的区间和维护的区间没有交集
{
if (st != -2e9) res.push_back({st, ed}); //如果维护的区间不是初始区间，则存入res
st = seg.first, ed = seg.second; //将维护的区间更换为当前区间
}
else ed = max(ed, seg.second); //否则更新维护区间的右端点
if (st != -2e9) res.push_back({st, ed}); //如果最后维护的区间不是初始区间，则存入res
segs = res;
}