AcWing 算法基础课笔记 1.基础算法

您所在的位置：网站首页 › acwing算法基础班视频下载 › AcWing 算法基础课笔记 1.基础算法

AcWing 算法基础课笔记 1.基础算法

#AcWing 算法基础课笔记 1.基础算法| 来源: 网络整理| 查看: 265

AcWing 算法基础课笔记 1.基础算法排序快速排序基本思想思路讲解快排模板归并排序基本思想思路归并模板二分整数二分基本思想注意点整数二分模板浮点数二分基本思想浮点数二分模板高精度前置知识：大整数的存储两个大整数相加高精度加法模板两个大整数相减注意点高精度减法模板高精度乘低精度高精度乘低精度模板高精度除以低精度高精度除以低精度模板前缀和与差分前缀和基本原理前缀和模板例题差分基本思想差分模板例题双指针算法核心思想双指针算法模板位运算核心思想位运算模板离散化离散化模板区间合并区间合并模板

排序快速排序基本思想

基于分治。第一步确定分界点x：取左边界q[l]，或者取中间值q[(l+r)/2]，或者取右边界q[r]，也可以随机。第二步调整区间(较难部分)：让小于等于x的数在一个区间，大于x的在另一个区间在这里插入图片描述第三步递归处理左右两端

平均时间复杂度： O(nlogn) 每层期望是 n/2 ，递归深度 logn，故平均时间复杂度 O(nlogn)

思路讲解

思路1（暴力解法，需要额外空间放a b）：在这里插入图片描述思路2：（较优美的解法）：使用双指针，从数组两端向中间靠拢。指针 i 从左端找大于等于 x 的数，指针 j 从右端找小于等于 x 的数，然后swap二者，直至 i 和 j 相遇。

快排模板 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 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 while (l while (l /* ... */} // 检查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; } 高精度

一般分四种：（大整数指位数（length） ⩽ \leqslant ⩽ 106。小整数指数值 ⩽ \leqslant ⩽ 109, 这里一般考虑 ⩽ \leqslant ⩽ 10000）两个大整数相加：A+B 两个大整数相减：A-B 一个大整数乘以一个小整数：A*a 一个大整数除以一个小整数：A/a （两个大整数相乘相除太复杂不常考，这里不考虑，浮点数也不讲，同样用的少。）在这里插入图片描述

前置知识：大整数的存储

对于一个大整数，通常用数组来存，这里从低位开始存较好。原因是：因为整数相加要进位，当最高位要进位的时候，我们在数组的末尾使用 push_back() 加一位即可，较方便。反之，在头部加一位要将整个数组后移，较麻烦。在这里插入图片描述

两个大整数相加

对于存在数组中的两个大整数：A[ ]、B[ ]，相加时如下，这里 t 存储进位1：在这里插入图片描述

高精度加法模板 // C = A + B, A >= 0, B >= 0 vector add(vector &A, vector &B) { if (A.size() vector C; for (int i = 0, t = 0; i vector C; int t = 0; for (int i = 0; i vector 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; } 前缀和与差分前缀和基本原理

对于原数组 a1、a2、a3、…、an 前缀和数组 Si = a1 + a2 + a3 + … + ai 定义 S0 = 0

第一个问题：如何求 Si 使用一个 for 循环，递归 S[i] = S[i-1] + ai 第二个问题：前缀和有什么作用？在计算区间 [ l , r ] 内数的和，若直接使用 for 循环，时间复杂度为 O(n) 但是若使用前缀和，可直接计算 Sr - Sl-1

除了一维数组的计算，也可以推导至二维，计算二维数组中 [ aij, alr ] 的和。二维前缀和数组一般是从 1 开始而不是 0 。在这里插入图片描述

前缀和模板

一维前缀和：

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] 例题

在这里插入图片描述

#include using namespace std; const int N = 100010; int n, m; int a[N],s[N]; int main(){ scanf("%d%d", &n, &m); for(int i = 1; i scanf("%d%d%d", &n, &m, &q); for(int i = 1; i scanf("%d", &s[i][j]); } } for(int i = 1; i s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1]; } } while(q--){ int x1, y1, x2, y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2); printf("%d\n", s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]); } return 0; } 差分基本思想

差分是前缀和的逆运算即根据给出的前缀和求原数组的值这里根据 A[ ] 数组，构造 B[ ] 数组，使得 A 是 B 的前缀和在这里插入图片描述差分有什么作用？对于将数组 A[ ] 的 [ l , r ] 区间内所有数都 + c，操作 A 数组时，需要遍历一遍，时间复杂度为 O(n)。而操作 B 数组时，只需要将 bl + c ，就可以使的从 a[ l ] 到 a[ n ]的所有数都加 c，再使用 br+1 - c，消除对 a[ r ]之后数的影响，就可以将时间复杂度降至 O(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 例题

在这里插入图片描述

#include using namespace std; const int N = 100010; int n, m; int a[N], b[N]; void insert(int l, int r, int c){ b[l] += c; b[r+1] -= c; } int main(){ scanf("%d%d", &n, &m); for(int i = 1; i int l, r, c; scanf("%d%d%d", &l, &r, &c); insert(l, r, c); } for(int i = 1; i b[x1][y1] += c; b[x2+1][y1] -= c; b[x1][y2+1] -=c; b[x2+1][y2+1] += c; } int main(){ scanf("%d%d%d", &n, &m, &q); for(int i = 1; i int x1, y1, x2, y2, c; scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c); insert(x1, y1, x2, y2, c); } for(int i = 1; i b[i][j] += b[i-1][j] + b[i][j-1] - b[i-1][j-1]; printf("%d ", b[i][j]); } puts(""); } return 0; } 双指针算法核心思想

对于以往需要双重 for 循环暴力解的题目进行优化在快排和归并排序中都用到了双指针的思想。在这里插入图片描述所以一般做题都是先用暴力解法想思路，再用双指针优化时间复杂度。

双指针算法模板 for (int i = 0, j = 0; i int l = 0, r = alls.size() - 1; while (l vector res; sort(segs.begin(), segs.end()); int st = -2e9, ed = -2e9; for (auto seg : segs) if (ed st, ed}); st = seg.first, ed = seg.second; } else ed = max(ed, seg.second); if (st != -2e9) res.push_back({st, ed}); segs = res; }

附：有些较复杂的懒得写特别细，建议AcWing学一下y总的课效果更好。以上模板、截图均来源：AcWing 的算法基础课链接：https://www.acwing.com/blog/content/277/

【本文地址】

AcWing 算法基础课笔记 1.基础算法

AcWing 算法基础课笔记 1.基础算法

今日新闻

推荐新闻