| 等 级 | |
| 排 名 | 195 |
| 经 验 | 6625 |
| 参赛次数 | 1 |
| 文章发表 | 19 |
| 年 龄 | 20 |
| 在职情况 | 学生 |
| 学 校 | 西安工程大学 |
| 专 业 | 大数据 |
自我简介：
静，不是外在无声，而是内心无争
TA的其他文章
| 1021迭代法求平方根(c语言代码 2种求法) 浏览：104 |
| 1028求一元二次方程（c语言） 浏览：58 |
| 1052链表合并(c语言) 浏览：241 |
你可能喜欢
C语言程序设计教程（第三版）课后习题5.7 （C语言代码）浏览：361 |
C语言程序设计教程（第三版）课后习题9.6 （C语言代码）浏览：315 |
宏定义（C语言代码）浏览：671 |
C语言程序设计教程（第三版）课后习题11.1 （C语言代码）浏览：1947 |
The 3n + 1 problem （C语言代码）浏览：1378 |
首先对于这道题一维和二维的前缀和都可以解,那我们此处讲一下一维+双指针和普通没有优化的暴力二维,有兴趣的同学可以去尝试用二维前缀+二分法求一下这个题
第一种解法:暴力二维前缀和(只能拿80分)
因为我们用的暴力解,所以想法很简单把每个位置的前缀和都求出来然后一层一层的for循环就可以了,我们打个表看一下,就明白了,用一下题目给的数据
| arr[i][j] | j=1 | 2 | 3 | 4 |
| i=1 | 1 | 2 | 3 | 4 |
| 2 | 5 | 6 | 7 | 8 |
| 3 | 9 | 10 | 11 | 12 |
然后我们对每个位置进行二维前缀和的计算;我们看一下代码实现
kul[i][j]=kul[i-1][j]+kul[i][j-1]+arr[i][j]-kul[i-1][j-1]; //arr是输入的数据,ful是我们用来记录二维前缀和的数组
| kul[i][j] | j=1 | 2 | 3 | 4 |
| i=1 | 1 | 3 | 6 | 10 |
| 2 | 6 | 14 | 24 | 36 |
| 3 | 15 | 33 | 54 | 78 |
kul数组每个位置记录的都是1~i和1~j所以元素的总和,然后我们直接暴力对每个前缀和做差与题目给的k进行比对小的话结果就加1大的话就直接break；
if(kul[k][p]-kul[i-1][p]-kul[k][j-1]+kul[i-1][j-1]<=val) //如果可以就一直算下去,不行直接break,也算是个小优化吧
{
flag++;
}else{
break;
}我们看一下完整代码(感兴趣的同学可以优化一下二维前缀可以拿满分,这里就分享一下暴力的做法吧)
#include<stdio.h>
#include<string.h>
#define max 505
int arr[max][max],kul[max][max];
int main()
{
int n,m,k,val,i,j,p;
scanf("%d%d%d",&n,&m,&val);
memset(kul,0,sizeof(kul));
for(i=1; i<=n; i++)
{
for(j=1; j<=m; j++)
{
scanf("%d",&arr[i][j]);
kul[i][j]=kul[i-1][j]+kul[i][j-1]+arr[i][j]-kul[i-1][j-1];
}
}
int flag=0,mi=0;
for(i=1; i<=n; i++)
{
for(j=1; j<=m; j++)
{
for(k=i; k<=n; k++)
{
for(p=j; p<=m; p++)
{
if(kul[k][p]-kul[i-1][p]-kul[k][j-1]+kul[i-1][j-1]<=val)
{
flag++;
}
else
{
break;
}
}
}
}
}
printf("%d",flag);
return 0;
}第二种解法:一维前缀和加双指针(满分AC)
当然了我们用一维前缀和也是可以做出来的,我们的一维是对于列的一维,看一下表格:
| kul[i][j] | j=1 | 2 | 3 | 4 |
| i=1 | 1 | 2 | 3 | 4 |
| 2 | 6 | 8 | 10 | 12 |
| 3 | 15 | 18 | 21 | 24 |
我们的做法是按行从1开始计算,但我们加的值是按照列来计算的,如果满足题目给的k我们就直接加上就可以了,如果没有满足我们用while循环来进行列的向右遍历，看下源码
#include<stdio.h>
int s[505][505];
int main( )
{
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
scanf("%d",&s[i][j]);
s[i][j]+=s[i-1][j];
}
}
long long int res=0;
for(int i=1; i<=n; i++)
{
for(int j=i; j<=n; j++)
{
for(int left=1,right=1,sum=0; right<=m; right++)
{
sum+=s[j][right]-s[i-1][right];
while (sum>k)
{
sum-=s[j][left]-s[i-1][left];
left++;
}
res+=right-left+1;
}
}
}
printf("%lld",res);
return 0;
}0.0分
73 人评分
评论区
大佬！请问if(kul[k][p]-kul[i-1][p]-kul[k][j-1]+kul[i-1][j-1]<=val)怎么理解？？kul[k][p]-kul[i-1][p]-kul[k][j-1]+kul[i-1][j-1]是什么意思？求教！！
下面双指针的这个复杂度不是500*500*500的吗，为什么不会时间超限？
Thawne 2023-01-03 17:56:06 |
没事了，想岔劈了，1e8勉勉强强吧
四重for循环，有点看不明白 0.0
dotcpp0643114 2023-02-23 17:14:55 |
我看明白了
奔跑的吮指原味鸡 2023-03-26 15:41:19 |
这四个数相当于x1,y1 x2,y2。建议学一遍前缀和&子矩阵
为什么这样的题会是简单题 我比赛的时候就感觉好难啊
- «
- 1
- »
精彩推荐
IP判断 （C语言代码）浏览：992 |
C语言程序设计教程（第三版）课后习题10.7 （C语言代码）浏览：549 |
C语言程序设计教程（第三版）课后习题6.4 （C语言代码）浏览：573 |
C语言程序设计教程（第三版）课后习题1.5 （C语言代码）浏览：584 |
C语言程序设计教程（第三版）课后习题5.4 （C语言代码）浏览：552 |
【计算球体积】 （C语言代码）浏览：1158 |
C语言程序设计教程（第三版）课后习题8.4 （C语言代码）浏览：541 |
循环入门练习5 （C语言代码）浏览：908 |
1035 题解浏览：875 |
C二级辅导-求偶数和 （C语言代码）浏览：707 |
尘客 2023-03-20 09:17:50 |
这是二维矩阵区域和的计算公式, 你学一下二维前缀和就会了
菜鸟求带飞 2023-03-21 19:54:59 |
好的，谢谢大佬
又又 2023-04-04 16:27:26 |
画个图试一试，这其实就是i-1行和j-1和列围起来里面的那一块矩阵，只不过你减了kul[i-1][p]和kul[k][j-1]，kul[i-1[j-]减了两遍，所以加回来
又又 2023-04-04 16:28:11 |
你画图就可以发现这个矩阵是任意的，可以1x1，可以1x2，2x1，2x2....
菜鸟求带飞 2023-04-05 23:13:03 |
@dotcpp0661505 明白了，谢谢大佬！