C++前缀和差分（练习题）

连续数的和模拟法【描述】给出两个整数n和k2≤n≤70000,1≤k≤n求出1,2,3,…,n中连续k个数的和并计算出和为平方数的个数。例如n10,k3。在1,2,…,10中连续3个数的和有123623493451245615567186782178924891027其中和为平方数的仅有9因为93×3。【输入】n,k两个整数。【输出】一个整数即1,2,…,n中连续k个数的和为平方数的个数。【输入样例1】10 3【输出样例1】1#includeiostream#includecmathusingnamespacestd;// 一个整数n是否平方数boolis_square(longlongn){longlongmsqrt(n);//求n的平方根,类型转换时向下取整returnm*mn;}intmain(){intn,k;scanf(%d %d,n,k);intcnt0;//注意局部变量定义时要初始化为0// 逐个查看区间和是否是平方数// 连续k个数的区间 [i,ik-1]区间和 sum[ik-1] - sum[i-1]for(inti1;in-k1;i){// 累加 k个连续数: s i (i1) ...(ik-1) k*i k*(k-1)/2longlongsi*kk*(k-1)/2;if(is_square(s))cnt;}printf(%d\n,cnt);在这里插入代码片return0;}/* 【输入用例2】 100 3 【输出用例2】 5 【输入用例3】 200 6 【输出用例3】 5 【输入用例4】 500 10 【输出用例4】 6 【输入用例5】 999 12 【输出用例5】 0 */连续数的和前缀和法【描述】给出两个整数n和k2≤n≤70000,1≤k≤n求出1,2,3,…,n中连续k个数的和并计算出和为平方数的个数。例如n10,k3。在1,2,…,10中连续3个数的和有123623493451245615567186782178924891027其中和为平方数的仅有9因为93×3。【输入】n,k两个整数。【输出】一个整数即1,2,…,n中连续k个数的和为平方数的个数。【输入样例1】10 3【输出样例1】1#includeiostream#includecmathusingnamespacestd;longlongsum[70010];//前缀和数组// 一个整数n是否平方数boolis_square(longlongn){longlongmsqrt(n);//求n的平方根,类型转换时向下取整returnm*mn;}intmain(){intn,k;scanf(%d %d,n,k);for(inti1;in;i)sum[i]sum[i-1]i;//预计算前缀和intcnt0;//注意局部变量定义时要初始化为0// 逐个查看区间和是否是平方数// 连续k个数的区间 [i,ik-1]区间和 sum[ik-1] - sum[i-1]for(inti1;in-k1;i){if(is_square(sum[ik-1]-sum[i-1]))cnt;}printf(%d\n,cnt);return0;}/* 【输入用例2】 50 2 【输出用例2】 4 【输入用例3】 300 9 【输出用例3】 15 【输入用例4】 500 19 【输出用例4】 5 【输入用例5】 800 88 【输出用例5】 5 【输入用例6】 2025 25 【输出用例6】 41 */区间修改后求和【描述】对数组多次区间加操作后求最终数组【输入描述】首先第一行输入两个数n,m;数字n表示数组的元素个数m表示对数组操作的次数。接下来一行输入n个数组元素接下来m行输入操作详细说明定义l, r, cl与r表示需要操作的数组元素区间lrc表示加操作的值;【输出描述】输出进行加操作之后的数组【样例输入】5 31 2 3 4 51 5 12 4 23 3 -1【样例输出】2 5 5 7 6#includeiostreamusingnamespacestd;// 定义最大数组长度预留10个额外空间防止越界constintN1e510;intn,m;inta[N],d[N];// a为原数组d为差分数组// 差分数组区间更新函数对区间[l, r]的元素增加cvoidinsert(intl,intr,intc){d[l]c;// 左端点l的差分值if(r1n)d[r1]-c;// 右端点1的差分值防止越界}intmain(){cinnm;// 输入数组长度和操作次数for(inti1;in;i)cina[i];// 构建差分数组d[1]a[1];for(inti2;in;i){d[i]a[i]-a[i-1];}// 处理m次区间更新操作while(m--){intl,r,c;cinlrc;insert(l,r,c);}// 通过差分数组还原最终结果前缀和for(inti1;in;i){d[i]d[i-1];// 累加差分值得到当前元素coutd[i] ;}return0;}/* 【输入用例2】 1 1 5 1 1 3 【输出用例2】 8 【输入用例3】 3 2 0 -1 2 1 3 -5 2 2 10 【输出用例3】 -5 4 -3 【输入用例4】 4 2 10 20 30 40 1 2 5 3 4 -10 【输出用例4】 15 25 20 30 【输入用例5】 6 3 3 1 4 1 5 9 2 5 0 1 6 -3 3 3 100 【输出用例5】 0 -2 101 -2 2 6 【输入用例6】 5 3 5 4 3 2 1 1 5 2 2 4 2 3 3 -3 【输出用例6】 7 8 4 6 3 */交错和【描述】求数组中偶数位数值与奇数位数值的差值数位表示数组下标的数字0属于偶数【输入描述】输入为两行第一行表示数组的长度第二行输入n个数组元素【输出描述】输出数组中所有偶数位元素相加后的值减所有奇数位元素相加的值【样例输入】41 2 3 4【样例输出】-2#includeiostreamusingnamespacestd;intmain(){intn;// 数组长度cinn;inta[n],d[n]{0};// 原数组a差分数组d初始化为0// 输入原数组并构建差分数组for(inti0;in;i){cina[i];// 输入原数组元素// 根据索引奇偶性生成差分值偶数位取正奇数位取负d[i](i%20)?a[i]:-a[i];}intsum0;// 累加差分数组的中间结果// 从第二个元素开始累加差分值索引从1到n-1for(inti1;in;i)sumd[i];// 输出结果首元素 差分累加和coutsuma[0];return0;}/* 【输入用例2】 1 5 【输出用例2】 5 【输入用例3】 2 1 2 【输出用例3】 -1 【输入用例4】 3 2 3 4 【输出用例4】 3 【输入用例5】 6 3 7 2 8 1 9 【输出用例5】 -18 【输入用例6】 5 5 -5 5 -5 5 【输出用例6】 25 */矩阵对称性【描述】判断一个矩阵是否关于主对角线对称主对角线是指从矩阵的左上角到右下角连成的线【输入描述】第一行输入n表示矩阵的维度矩阵的行、列默认均为n接下来输入矩阵所有的行列元素【输出描述】如果矩阵对称输出YES否则输出NO【样例输入】41 2 3 42 3 4 33 4 5 24 3 2 1【样例输出】YES#includeiostreamusingnamespacestd;intmain(){intn;// 矩阵维度cinn;inta[n][n],s[n][n]{0};// 原矩阵a前缀和矩阵s初始化为0// 输入原矩阵并构建前缀和数组for(inti1;in;i){for(intj1;jn;j){cina[i][j];// 前缀和公式s[i][j] 上方 左方 - 左上角 当前值s[i][j]s[i-1][j]s[i][j-1]-s[i-1][j-1]a[i][j];}}booloktrue;// 对称性标志// 检查所有i j的对称子矩阵for(inti1;in;i){for(intji1;jn;j){// 计算左下三角区域和从(i,j)到(n,n)intsum1s[n][n]-s[i-1][n]-s[n][j-1]s[i-1][j-1];// 计算右上三角区域和从(j,i)到(n,n)intsum2s[n][n]-s[j-1][n]-s[n][i-1]s[j-1][i-1];if(sum1!sum2)okfalse;// 不对称则标记失败}}cout(ok?YES:NO);// 输出结果return0;}/* 【输入用例2】 1 5 【输出用例2】 YES 【输入用例3】 2 1 2 2 1 【输出用例3】 YES 【输入用例4】 3 1 2 3 2 3 4 3 4 5 【输出用例4】 YES 【输入用例5】 4 1 2 3 4 2 3 4 5 3 4 5 6 4 5 7 7 【输出用例5】 NO 【输入用例6】 3 1 0 0 0 0 1 1 0 0 【输出用例6】 NO */