acwing-区间和
区间和假定有一个无限长的数轴,数轴上每个坐标上的数都是 0。
现在,我们首先进行 n 次操作,每次操作将某一位置 x 上的数加 c。
接下来,进行 m 次询问,每个询问包含两个整数 l 和 r,你需要求出在区间 [l,r][�,�] 之间的所有数的和。
输入格式第一行包含两个整数 n 和 m。
接下来 n 行,每行包含两个整数 x 和 c。
再接下来 m 行,每行包含两个整数 l 和 r。
输出格式共 m 行,每行输出一个询问中所求的区间内数字和。
数据范围−10^9≤x≤10^9,1≤n,m≤10^5,−10^9≤l≤r≤10^9,−10000≤c≤10000
输入样例:12345673 31 23 67 51 34 67 8
输出样例:123805
数轴的长度是10的9次方级别,需要进增加和查询的点的数量是10的5次方级别。这些点在数轴上的分布非常稀疏,如果直接使用前缀和会超时。
考虑把这些稀疏的点通过一个映射关系映射到一块连续的区域,操作次数就会变为10的5次方级别,再使用前缀和就可以了。
把所有需要进行增加和查询的点记录到all数组里,对数组进行排序。
用二分找到这个点 ...
acwing-二进制中1的个数
二进制中1的个数给定一个长度为 n 的数列,请你求出数列中每个数的二进制表示中 11 的个数。
输入格式第一行包含整数 n。
第二行包含 n 个整数,表示整个数列。
输出格式共一行,包含 n 个整数,其中的第 i 个数表示数列中的第 i 个数的二进制表示中 11 的个数。
数据范围1≤n≤1000001,0≤数列中元素的值≤1090≤数列中元素的值≤109
输入样例:1251 2 3 4 5
输出样例:11 1 2 1 2
将十进制数与1后右移1位直到十进制数为0可以实现十进制转二进制。
123456789101112131415161718192021#include<iostream>#include<vector>using namespace std;int main(){ int n; cin>>n; vector<int> a(n+1); vector<int> res; for(int i=0;i<n;i++) cin>>a[i]; for(i ...
acwing-判断子序列
判断子序列给定一个长度为 n 的整数序列 a1,a2,…,an 以及一个长度为 m 的整数序列 b1,b2,…,bm。
请你判断 a 序列是否为 b 序列的子序列。
子序列指序列的一部分项按原有次序排列而得的序列,例如序列 {a1,a3,a5} 是序列 {a1,a2,a3,a4,a5} 的一个子序列。
输入格式第一行包含两个整数 n,m。
第二行包含 n个整数,表示 a1,a2,…,an。
第三行包含 m 个整数,表示 b1,b2,…,bm。
输出格式如果 a 序列是 b 序列的子序列,输出一行 Yes。
否则,输出 No。
数据范围1≤n≤m≤105,−109≤ai,bi≤109
输入样例:1233 51 3 51 2 3 4 5
输出样例:1Yes
设置两个指针i,j分别指向a,b开头,如果对应元素相等,i++否则j++.循环结束后判断i的位置确定是否满足
12345678910111213141516171819202122/*while循环版*/#include<iostream>#include<vector>using namespace s ...
acwing-数组元素的目标和
数组元素的目标和给定两个升序排序的有序数组 A 和 B,以及一个目标值 x。
数组下标从 00 开始。
请你求出满足 A[i]+B[j]=x=的数对 (i,j)。
数据保证有唯一解。
输入格式第一行包含三个整数 n,m,x,分别表示 A 的长度,B 的长度以及目标值 x。
第二行包含 n 个整数,表示数组 A。
第三行包含 m个整数,表示数组 B。
输出格式共一行,包含两个整数 i 和 j。
数据范围数组长度不超过 105105。同一数组内元素各不相同。1≤数组元素≤1091≤数组元素≤109
输入样例:1234 5 61 2 4 73 4 6 8 9
输出样例:11 1
方法一用哈希表记录x-a[i]的下标,如果b中元素在哈希表中出现过说明b[j]+a[i]==x。题目保证有唯一解,输出完直接返回。
1234567891011121314151617181920212223#include<iostream>#include<vector>#include<unordered_map>using namespace std ...
acwing-最长连续不重复子序列
最长连续不重复子序列给定一个长度为 n 的整数序列,请找出最长的不包含重复的数的连续区间,输出它的长度。
输入格式第一行包含整数 n。
第二行包含 n 个整数(均在 0∼1050∼105 范围内),表示整数序列。
输出格式共一行,包含一个整数,表示最长的不包含重复的数的连续区间的长度。
数据范围1≤n≤105
输入样例:1251 2 2 3 5
输出样例:13
维护一个滑动窗口和哈希表,哈希表记录窗口内数字出现的频率
右指针一直向右滑动将元素加入哈希表
如果右指针指向的元素在窗口内出现次数超过1次,左指针向右移动缩小窗口直到每个元素只出现一次。记录窗口长度取最大值
123456789101112131415161718192021#include<iostream>#include<vector>using namespace std;int main(){ int n; cin>>n; vector<int> a(n+1),h(n+1,0); for(int i=0;i<n;i++) ...
acwing-差分矩阵
差分矩阵输入一个 n 行 m 列的整数矩阵,再输入 q 个操作,每个操作包含五个整数 x1,y1,x2,y2,c,其中 (x1,y1) 和 (x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。
每个操作都要将选中的子矩阵中的每个元素的值加上 c。
请你将进行完所有操作后的矩阵输出。
输入格式第一行包含整数 n,m,q。
接下来 n行,每行包含 m个整数,表示整数矩阵。
接下来 q行,每行包含 55 个整数 x1,y1,x2,y2,c,表示一个操作。
输出格式共 n 行,每行 m 个整数,表示所有操作进行完毕后的最终矩阵。
数据范围1≤n,m≤1000,1≤q≤100000,1≤x1≤x2≤n,1≤y1≤y2≤m,−1000≤c≤1000,−1000≤矩阵内元素的值≤1000−1000≤矩阵内元素的值≤1000
输入样例:12345673 4 31 2 2 13 2 2 11 1 1 11 1 2 2 11 3 2 3 23 1 3 4 1
输出样例:1232 3 4 14 3 4 12 2 2 2
二维版的差分。
同样也是二维版前缀和的逆运算
123456789101112 ...
acwing-差分
差分输入一个长度为 n 的整数序列。
接下来输入 m 个操作,每个操作包含三个整数 l,r,c,表示将序列中 [l,r][�,�] 之间的每个数加上 c。
请你输出进行完所有操作后的序列。
输入格式第一行包含两个整数 n 和 m。
第二行包含 n 个整数,表示整数序列。
接下来 m行,每行包含三个整数 l,r,c,表示一个操作。
输出格式共一行,包含 n 个整数,表示最终序列。
数据范围1≤n,m≤100000,1≤l≤r≤n,−1000≤c≤1000,−1000≤整数序列中元素的值≤1000−1000≤整数序列中元素的值≤1000
输入样例:123456 31 2 2 1 2 11 3 13 5 11 6 1
输出样例:13 4 5 3 4 2
差分是前缀和的逆运算,用于快速计算一段区间内加上某一个常数
构建a的差分数组b,同时a是b的前缀和数组。
b[l]+c后,a数组变为a[l]+c,a[l+1]+c...a[r]+c,a[r+1]+c...a[n]+c
b[r+1]-c后,a数组变为a[l]+c,a[l+1]+c...a[r]+c,a[r+1]+c-c...a[n]+c ...
acwing-子矩阵的和
子矩阵的和输入一个 n 行 m 列的整数矩阵,再输入 q 个询问,每个询问包含四个整数 x1,y1,x2,y2,表示一个子矩阵的左上角坐标和右下角坐标。
对于每个询问输出子矩阵中所有数的和。
输入格式第一行包含三个整数 n,m,q。
接下来 n 行,每行包含 m 个整数,表示整数矩阵。
接下来 q 行,每行包含四个整数 x1,y1,x2,y2,表示一组询问。
输出格式共 q 行,每行输出一个询问的结果。
数据范围1≤n,m≤1000,1≤q≤200000,1≤x1≤x2≤n,1≤y1≤y2≤m,−1000≤矩阵内元素的值≤1000
输入样例:12345673 4 31 7 2 43 6 2 82 1 2 31 1 2 22 1 3 41 3 3 4
输出样例:123172721
二维版的前缀和
12345678910111213141516171819202122232425262728#include<iostream>using namespace std;const int N = 1005;int a[N][N];int s[N][N];int main() ...
acwing-前缀和
前缀和输入一个长度为 n 的整数序列。
接下来再输入 m 个询问,每个询问输入一对 l,r。
对于每个询问,输出原序列中从第 l 个数到第 r 个数的和。
输入格式第一行包含两个整数 n和 m。
第二行包含 n个整数,表示整数数列。
接下来 m 行,每行包含两个整数 l 和 r,表示一个询问的区间范围。
输出格式共 m行,每行输出一个询问的结果。
数据范围1≤l≤r≤n,1≤n,m≤100000,−1000≤数列中元素的值≤1000
输入样例:123455 32 1 3 6 41 21 32 4
输出样例:1233610
前缀和模板题。
前缀和数组s[i]表示a[1]+...+a[i-1](这个题下标从1开始)
[l,r]的区间和等于a[1]+...a[l-1]+a[l]+...+a[r]-(a[1]+...+a[l-1])也就是s[r+1]-s[l]。
构造前缀和数组是线性时间复杂度,每次查询是常数时间复杂度。
123456789101112131415161718192021#include<iostream>#include<vector>using ...
acwing-高精度除法
高精度除法给定两个非负整数(不含前导 00) A,B,请你计算 A/B 的商和余数。
输入格式共两行,第一行包含整数 A,第二行包含整数 B。
输出格式共两行,第一行输出所求的商,第二行输出所求余数。
数据范围1≤A的长度≤100000,1≤B≤10000,B 一定不为 0
输入样例:1272
输出样例:1231
因为除法是从高位开始算,加减法和乘法都是从低位开始,所以除法其实不用倒序存储数据。但是为了和前边保持一致,同样采用倒序存储。
1234567891011121314151617181920212223242526272829#include<iostream>#include<vector>#include<algorithm>using namespace std;vector<int> div(vector<int> a,int b,int &r){ vector<int> c; for(int i=a.size()-1;i>=0;i--){ ...