AcWing 797. 差分
原题链接：https://www.acwing.com/problem/content/description/799/
所谓的差分，是对于一个数组，定义一个数组，使得是的前缀和数组。即： 为了满足这个条件，我们可以构造这样一个数组： 所以差分又是前缀和的逆运算。通过差分数组，我们可以方便地为中的任意一段区间加上或者减去一个数，其时间复杂度为。
#include <iostream>#define N 100005int a[N], b[N];int main() { int n, m; scanf("%d %d", &n, &m); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); // 构造差分数组 // b[0] = a[1] // b[1] + b[0] = a[2] // b[2] + b[1] + b[0] = a[3]; // ... // b[i] = a[i+1] - a[i], b[0] ...
AcWing 796. 子矩阵的和
原题链接：https://www.acwing.com/activity/content/problem/content/830/
与前缀和大致相似，我们定义子矩阵数组preSum[]中，表示所有位于左下角的元素之和。如表示原数组中坐标和的元素和。
sub_matrix
于是，可以得出以下等式： 因此，代码如下：
#include <iostream>#define N 1005#define M 1005#define Q 200005int preSum[N][M];int nums[N][M];int ans[Q];int n, m, q;void build() { preSum[0][0] = 0; for (int i = 1; i < n; ++i) preSum[i][0] = 0; for (int i = 1; i < m; ++i) preSum[0][i] = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++ ...
AcWing 795. 前缀和
原题链接：https://www.acwing.com/problem/content/797/
简单题，只需注意区间的定义，是左闭右开的即可。
#include <iostream>#define N 100005int preSum[N]; // 前缀和数组int ans[N];int main() { int n, m; preSum[0] = 0; scanf("%d %d", &n, &m); int tmp; // 构造前缀和数组 // preSum[i]表示[0, i)的和。如preSum[1]表示[0, 1)的和，即presum[1] = nums[0]。 for (int i = 0; i < n; ++i) { scanf("%d", &tmp); preSum[i + 1] += preSum[i] + tmp; } int l, r; // 查询[l-1, r)的和，等于[0, r) - [0, l-1)。 for (int ...
AcWing 794. 高精度除法
原题链接：https://www.acwing.com/problem/content/796/
模拟手工除法，从高位往低位依次除。也正因为从高位往低位除，因此最后去除前导0的时候要首先将结果向量reverse一次。
#include <iostream>#include <algorithm>using namespace std;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_ ...
AcWing 793. 高精度乘法
原题链接：https://www.acwing.com/problem/content/795/
高精度乘以低精度，只需用高精度的每一位去乘以低精度即可。
高精度x低精度
#include <iostream>#include <string>#include <vector>using namespace std;// 16// x 135// -------------// | | |9|0|// | |4|8|// |1|6|// _____________// |2|1|7|0vector<int> mul(vector<int>& A, int B) { vector<int> C; int t = 0; // t表示进位 for (int i = 0; i < A.size(); ++i) { t = A[i] * B + t; C.push_back(t % 10); ...
AcWing 791. 高精度减法
原题链接：https://www.acwing.com/problem/content/794/
模板代码，和加法的实现差不多
#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(); //直接return 了就不用else for(int i = A.size(); i >= 0; i--) if(A[i] != B[i]) return A[i] > B[i]; return true;}// 注意A和B是反着装的// 计算A - B，这里A >= Bvector <int> sub(vector<int>& A, vector<int&g ...
AcWing 791. 高精度加法
原题链接：https://www.acwing.com/problem/content/793/
模板代码
模板代码的思路是直接将两个数逆序存储，然后从低位向高位加。
// C = A + B, A >= 0, B >= 0vector<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++版本
自己实现的思路是，顺序存储，然后用两个指 ...
AcWing 790. 数的三次方根
原题链接：https://www.acwing.com/problem/content/description/792/
思路就是直接对根所在的区间进行二分，直到区间长度小于某个误差值。注意到
当时，
当时，
因此根据的大小可以确定二分区间的右端点。
#include <iostream>double err = 1e-7;double cube(double x) { return x * x * x; }double bin_search(double x) { double i = 0, j = x < 1 ? 1 : x; while (j - i > err) { double k = (i + j) / 2; double tmp = cube(k); if (tmp > x) j = k; else i = k; } return i;}int main() { double x; scanf("%lf", &x); double ...
AcWing 789. 数的范围
原题链接：https://www.acwing.com/problem/content/description/791/
思路一：二分查找
用两个二分查找，一个查找target的左边界，一个查找右边界。
#include <iostream>#include <cstring>#define LL long long#define N 100005#define Q 10005#define K 10005int ans[Q][2], nums[N];int bin_search_r(int nums[], int left, int right, int target) { int i = left, j = right; while (i < j) { int k = (i + j) >> 1; if (nums[k] < target) i = k + 1; else if (target < nums[k]) j = k; else { ...
CMU Deep Learning Systems: Lecture 1 - Introduction and Logistics
Learning objectives of course
By the end of this course, you will
understand the basic functioning of modern deep learning libraries, including concepts like automatic differentiation, gradient-based optimization.
be able to implement several standard deep learning architectures (MLPs, ConvNets, RNNs, Transformers), truly from scratch … understand how hardware acceleration (e.g., on GPUs) works under the hood for modern deep learning architectures, and be able to develop your own highly efficie ...