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 ...
AcWing 788. 逆序对的数量
原题链接：https://www.acwing.com/problem/content/description/790/
首先根据定理：交换紧邻的一个逆序对会使得整个数组的逆序对数量减一，我们可以得知，冒泡排序中元素交换的次数即等于逆序对的个数。
所以，可以直接使用冒泡排序统计逆序对的数量：
void bubble_sort(int nums[], int left, int right) { for (int i = 0; i < right - left; i++) { for (int j = left; j < right - i - 1; j++) { if (nums[j] > nums[j+1]) { swap(nums[j], nums[j+1]); count++; } } }}
但是冒泡排序的复杂度是，效率太低。
我们可以考虑采用分治思想，将数组一分为二，然后求出：
左半部分逆序对的个数
右半部分逆序对 ...
AcWing 787. 归并排序
原题链接：https://www.acwing.com/problem/content/789/
归并算法采用双指针实现，模板实现起来也比较简单。
// merge sort in [left, right)void merge_sort(int nums[], int left, int right) { if (right - left <= 1) return; int mid = (left + right) >> 1; merge_sort(nums, left, mid); merge_sort(nums, mid, right); int i = left, j = mid, k = 0; // i 和 j 不断移动取最小值，直到其中一个越界 while (i < mid && j < right) if (nums[i] < nums[j]) tmp[k++] = nums[i++]; else tmp[k++] = num ...
AcWing 786. 第k个数
原题链接：https://www.acwing.com/problem/content/788/
k-选取问题的核心依然是快速划分算法partition()，可以保证在的时间内完成k-选取。
#include <iostream>void swap(int& x, int& y) { if (x == y) return; x ^= y; y ^= x; x ^= y;}int partition(int nums[], int left, int right) { int i = left, j = right - 1; swap(nums[left], nums[(left + right) >> 1]); int pivot = nums[left]; while (i < j) { while (i < j && pivot < nums[j]) j--; if (i < j) nums[i++] = nums[j]; ...
AcWing 785. 快速排序
原题链接：https://www.acwing.com/problem/content/description/787/
快速排序算法最核心的部分是如何根据分界点pivot将数据划分为大于分界点和小于分界点的两部分。假设将划分算法记作partition()，那么partition又分为三种主流的实现。
LUG版
这个版本的缺点在于，对于大部分数据存在重复的情况，这个版本的划分会极不平衡。当数据全部重复时，使用该版本partition()算法的快速排序复杂度在。
这个版本的特点可以总结为：
勤于拓展
懒于交换
int partition(int nums[], int left, int right) { int i = left, j = right - 1; int mid = (left + right) >> 1; // 偷懒直接取中点 swap(nums[i], nums[mid]); int pivot = nums[i]; while (i < j) { while (i < j &a ...