当前位置：首页 > news >正文

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

news 2026/6/17 8:52:09

连续数的和（模拟法）

【描述】给出两个整数n和k，（2≤n≤70000,1≤k≤n），求出1,2,3,…,n中连续k个数的和，并计算出和为平方数的个数。
例如n=10,k=3。在1,2,…,10中，连续3个数的和有
1+2+3=6
2+3+4=9
3+4+5=12
4+5+6=15
5+6+7=18
6+7+8=21
7+8+9=24
8+9+10=27
其中和为平方数的仅有9，因为9=3×3。
【输入】
n,k两个整数。
【输出】
一个整数，即1,2,…,n中连续k个数的和为平方数的个数。
【输入样例1】
10 3
【输出样例1】
1

#include<iostream>#include<cmath>usingnamespacestd;// 一个整数n是否平方数boolis_square(longlongn){longlongm=sqrt(n);//求n的平方根,类型转换时向下取整returnm*m==n;}intmain(){intn,k;scanf("%d %d",&n,&k);intcnt=0;//注意局部变量定义时要初始化为0// 逐个查看区间和是否是平方数// 连续k个数的区间 [i,i+k-1]区间和 = sum[i+k-1] - sum[i-1]for(inti=1;i<=n-k+1;i++){// 累加 k个连续数: s = i + (i+1)+ ...+(i+k-1) = k*i + k*(k-1)/2longlongs=i*k+k*(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 */

连续数的和（前缀和法）

#include<iostream>#include<cmath>usingnamespacestd;longlongsum[70010];//前缀和数组// 一个整数n是否平方数boolis_square(longlongn){longlongm=sqrt(n);//求n的平方根,类型转换时向下取整returnm*m==n;}intmain(){intn,k;scanf("%d %d",&n,&k);for(inti=1;i<=n;i++)sum[i]=sum[i-1]+i;//预计算前缀和intcnt=0;//注意局部变量定义时要初始化为0// 逐个查看区间和是否是平方数// 连续k个数的区间 [i,i+k-1]区间和 = sum[i+k-1] - sum[i-1]for(inti=1;i<=n-k+1;i++){if(is_square(sum[i+k-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, c，l与r表示需要操作的数组元素区间（l<=r），c表示加操作的值;
【输出描述】输出进行加操作之后的数组
【样例输入】
5 3
1 2 3 4 5
1 5 1
2 4 2
3 3 -1
【样例输出】
2 5 5 7 6

#include<iostream>usingnamespacestd;// 定义最大数组长度（预留10个额外空间防止越界）constintN=1e5+10;intn,m;inta[N],d[N];// a为原数组，d为差分数组// 差分数组区间更新函数：对区间[l, r]的元素增加cvoidinsert(intl,intr,intc){d[l]+=c;// 左端点+l的差分值if(r+1<=n)d[r+1]-=c;// 右端点+1的差分值（防止越界）}intmain(){cin>>n>>m;// 输入数组长度和操作次数for(inti=1;i<=n;i++)cin>>a[i];// 构建差分数组d[1]=a[1];for(inti=2;i<=n;i++){d[i]=a[i]-a[i-1];}// 处理m次区间更新操作while(m--){intl,r,c;cin>>l>>r>>c;insert(l,r,c);}// 通过差分数组还原最终结果（前缀和）for(inti=1;i<=n;i++){d[i]+=d[i-1];// 累加差分值得到当前元素cout<<d[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个数组元素
【输出描述】输出数组中所有偶数位元素相加后的值减所有奇数位元素相加的值
【样例输入】
4
1 2 3 4
【样例输出】
-2

#include<iostream>usingnamespacestd;intmain(){intn;// 数组长度cin>>n;inta[n],d[n]={0};// 原数组a，差分数组d（初始化为0）// 输入原数组并构建差分数组for(inti=0;i<n;i++){cin>>a[i];// 输入原数组元素// 根据索引奇偶性生成差分值：偶数位取正，奇数位取负d[i]=(i%2==0)?a[i]:-a[i];}intsum=0;// 累加差分数组的中间结果// 从第二个元素开始累加差分值（索引从1到n-1）for(inti=1;i<n;i++)sum+=d[i];// 输出结果：首元素 + 差分累加和cout<<sum+a[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
【样例输入】
4
1 2 3 4
2 3 4 3
3 4 5 2
4 3 2 1
【样例输出】
YES

#include<iostream>usingnamespacestd;intmain(){intn;// 矩阵维度cin>>n;inta[n][n],s[n][n]={0};// 原矩阵a，前缀和矩阵s（初始化为0）// 输入原矩阵并构建前缀和数组for(inti=1;i<=n;i++){for(intj=1;j<=n;j++){cin>>a[i][j];// 前缀和公式：s[i][j] = 上方 + 左方 - 左上角 + 当前值s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];}}boolok=true;// 对称性标志// 检查所有i < j的对称子矩阵for(inti=1;i<=n;i++){for(intj=i+1;j<=n;j++){// 计算左下三角区域和（从(i,j)到(n,n)）intsum1=s[n][n]-s[i-1][n]-s[n][j-1]+s[i-1][j-1];// 计算右上三角区域和（从(j,i)到(n,n)）intsum2=s[n][n]-s[j-1][n]-s[n][i-1]+s[j-1][i-1];if(sum1!=sum2)ok=false;// 不对称则标记失败}}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 */