ZW_Blog

题目描述 题目大意&链接给定 a，b 两个子序列，判断 a 序列是否是 b 序列的子序列，是：Yes，否：No。 输入输出样例：输入： 3 51 3 51 2 3 4 5 输出： Yes 详情：ac_2816判断子序列 解题思路这题采用双指针的思想，可以参考ac_800数组元素的目标和： 定义 i，j 指针分别指向 a，b 序列的左端点，j一直右移循环遍历，若 a[i] == b[j] 则 i++ ，当 i==n 时则 a 是 b 的子序列： int i = 0, j = 0;while(i < n && j < m){ if(a[i] == b[j]) i++; j++;} 完整代码#include<iostream>using namespace std;const int N = 1e5 + 10;int n, m;int a[N], b[N];int main(){ scanf("%d %d",...

题目描述 题目大意&链接在两个数组中，找出满足 A[i] + B[j] = x 的数对（i，j）。 输入输出样例：输入： 4 5 61 2 4 73 4 6 8 9 输出： 1 1 详情：ac_800数组元素的目标和 解题思路这题采用双指针的思想，具体： 定义 i 指针指向 A 数组的左端点，j 指针指向 B 数组的右端点向左移动，由于 A，B 都是递增有序数组，当 A[i] + B[j] = x 时输出这个答案并跳出循环，i 指针右移继续寻找： for(int i = 0, j = m - 1; i < n; i++){ while(j >= 0 && A[i] + B[j] > x) j--; if(A[i] + B[j] == x) { printf("%d %d\n", i, j); break; ...

题目描述 题目大意&链接给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。 输入输出样例：输入： 51 2 2 3 5 输出： 3 详情：ac_799最长连续不重复子序列 解题思路这题采用双指针的思想，具体： 采用 map 哈希表存储数列中个元素出现的次数，i 指针往后移动，当 mp[a[i]] > 1 时，表示前面有重复元素，此时将 j 指针后移一位并 mp[a[j]]– ： map<int, int> mp;...mp[a[i]]++;while(mp[a[i]] > 1){ mp[a[j]]--; j++;} res 记录最长连续不重复子序列： res = max(res, i - j + 1); 完整代码#include<iostream>#include<map>using namespace std;const int N = 1e6 + 10;int n;int a[N], s[N];map<int, int>...

题目描述 题目大意&链接在一个给定的 n * m 的矩阵中，将给定的子矩阵中的元素都加上c。 输入输出样例：输入： 3 4 31 2 2 13 2 2 11 1 1 11 1 2 2 11 3 2 3 23 1 3 4 1 输出： 2 3 4 14 3 4 12 2 2 2 详情：ac_798差分矩阵 解题思路差分矩阵的思想可以参考ac_797差分和ac_796子矩阵的和。 构造差分矩阵： void insert(int x1, int y1, int x2, int y2, int c){ b[x1][y1] += c; //原前缀和矩阵（x1,y1）后面的元素都会 + c b[x2+1][y1] -= c; //进行抵消，只在给定区间 + c b[x1][y2+1] -= c; b[x2+1][y2+1] +=c; //进行补偿} 还原成前缀和矩阵： for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) b[i][j]...

总结英语背了一个小时单词

题目描述 题目大意&链接在一个给定的 n 个元素的数列中，将 [l, r]之间的元素都加上c（循环遍历时间复杂度为 O(n) 可能会超时，采用差分解决类似的问题可以降低时间复杂度至 O(1)）。 输入输出样例：输入： 6 31 2 2 1 2 11 3 13 5 11 6 1 输出： 3 4 5 3 4 2 详情：ac_797差分 解题思路首先差分和前缀和思想是互逆的，前缀和是求子区间和，差分是在子区间每个元素上加上元素 c。 输入数组 a ，得到它的差分 b 数组： for(int i = 1; i <= n; i++) scanf("%d", &a[i]);//b[i] = a[i] - a[i-1] a数组是b数组的前缀和，b数组是a数组的差分for(int i = 1; i <= n; i++) insert(i, i, a[i]);...//对区间 [l, r] 加 c 时，只需 b[l] += c 和 b[r+1] -= c，将区间操作转换为端点操作。void insert(int l, int r, int...

题目描述 题目大意&链接在一个给定的 n 行 m 列矩阵中，查询出子矩阵的和。 输入输出样例：输入： 3 4 31 7 2 43 6 2 82 1 2 31 1 2 22 1 3 41 3 3 4 输出： 172721 详情：ac_796子矩阵的和 解题思路子矩阵的和需要注意2点。 计算前缀和： //计算前缀和res[i][j] = res[i-1][j] + res[i][j-1] - res[i-1][j-1] + arr[i][j]; 计算矩阵区间和： //计算矩阵区间和cout<<res[x2][y2] - res[x1-1][y2] - res[x2][y1-1] + res[x1-1][y1-1]<<endl; 完整代码#include<iostream>using namespace std;const int N = 1010;int n, m, q;int arr[N][N];int res[N][N] = {0}; //res[i, j]...

题目描述 题目大意&链接对于每个询问，输出原序列中从第 l 个数到第 r 个数的和。 输入输出样例：输入： 5 32 1 3 6 41 21 32 4 输出： 3610 详情：ac_795前缀和 解题思路前缀和需要注意1点。 需要明确 res[i] 表示前i个元素的和，因此： for(int i = 1; i <= n; i++) { scanf("%d", &q[i]); res[i] = res[i-1] + q[i];} 完整代码#include<iostream>using namespace std;const int N = 1e6 + 10;int n, m;int q[N];int res[N] = {0}; // res[i]表示前i个元素的和（从1开始）int main(){ scanf("%d %d", &n, &m); for(int i = 1; i <= n; i++) ...

题目描述 题目大意&链接给定两个正整数，计算高精度整数乘以低精度整数。 输入输出样例：输入： 23 输出： 6 详情：ac_793高精度乘法 解题思路高精度乘法需要注意2点。 计算机处理乘法是将被乘数的每一位乘以乘数，然后赋值给进位 t ，t%10 作结果的数值位，t/10作进位： 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;} 去除结果的前导0： while(c.size() > 1 && c.back() == 0) c.pop_back(); //去除结果的前导0 完整代码#include<iostream>#include<vector>using namespace std;vector<int> mul(vector<int>...

题目描述 题目大意&链接给定两个正整数，计算高精度整数除以低精度整数。 输入输出样例：输入： 72 输出： 31 详情：ac_794高精度除法 解题思路高精度除法需要注意3点。 除法和加减乘法不同，它可以正序存储，但为统一模板，这里也采用逆序将其存储，因此div函数的循环条件需要更改： for(int i = A.size() - 1; i >= 0; i--){ ...} 余数 r 要模拟除法运算，r/b 作商的数值位；r %= b 作下一位的余数： for(int i = A.size() - 1; i >= 0; i--){ r = r * 10 + A[i]; c.push_back(r / b); r %= b;} 由于是逆序存储且逆序输出，则答案需要反转一下并去除结果的前导0： reverse(c.begin(), c.end());while(c.size() > 1 && c.back() == 0)...