ZW_Blog

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

题目描述 题目大意&链接求出给定数列中每个数的二进制表示中 1 的个数。 输入输出样例：输入： 51 2 3 4 5 输出： 1 1 2 1 2 详情：ac_801二进制中1的个数 解题思路这题求二进制数就是采用“除基取余”法： 将一个数除以2得到的余数作二进制数的数值位（低位），循环进行直到这个数除以2商是0，它的余数为最高位，这样的余数组成的数就是这个数的二进制数： int tmp = q[i], cnt = 0;while(tmp != 0){ if(tmp % 2 == 1) cnt++; tmp/=2;}printf("%d ", cnt); 完整代码#include<iostream>using namespace std;const int N = 1e6 + 10;int n;int q[N];int main(){ scanf("%d", &n); for(int i = 0; i < n; i++)...

题目描述 题目大意&链接给定 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++) ...