AcWing 799. 最长连续不重复子序列
原题链接：https://www.acwing.com/problem/content/description/801/
思路：
用一个pos[]数组来存储某个数上次出现的位置
双指针i和j，表示当前最长不重复区间[i,j)。每当将要把nums[j]纳入区间时，考察nums[j]上次出现的位置。
若在i的左侧，则可以直接把nums[j]纳入最长不重复区间。
否则，将i移动到nums[j]上次出现位置的右侧。
#include <iostream>#include <cstring>#define N 100005int nums[N];// 记录一个数上次出现的位置int pos[N];int n;// 区间[i, j)，j表示下一个将要纳入区间的数的下标int longest_repeat() { int i = 0, j = 1, max = 0; while (j <= n) { if (j - i > max) max = j -i; if (j == n) break; if ...
AcWing 798. 差分矩阵
原题链接：https://www.acwing.com/problem/content/800/
参考之前的构造一维矩阵的思路（差分是前缀和的逆运算），假设数组是的前缀和矩阵，有以下等式成立： 将除了矩阵以外的所有项移到左边，就可以得到根据前缀和矩阵求出差分矩阵的等式： 构造出差分矩阵后，就可以根据一维差分的思想，来修改二维差分矩阵了。这个过程本质上用的也还是容斥原理。
#include<iostream>#define N 1005int a[N][N];int b[N][N];int n, m, q;// 构建二维差分矩阵，本质是前缀和的逆运算void build() { // a[i][j] = a[i][j-1] + a[i-1][j] - a[i-1][j-1] + b[i-1][j-1] // b[i-1][j-1] = a[i][j] - a[i][j-1] - a[i-1][j] + a[i-1][j-1] for (int i = 1; i <= n; i++) { for (int j = 1; j <= ...
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 ...