题目描述
一种新型的激光炸弹,可以摧毁一个边长为 R 的正方形内的所有的目标。
现在地图上有 N 个目标,用整数Xi,Yi表示目标在地图上的位置,每个目标都有一个价值Wi。
激光炸弹的投放是通过卫星定位的,但其有一个缺点,就是其爆炸范围,即那个边长为 R 的正方形的边必须和x,y轴平行。
若目标位于爆破正方形的边上,该目标不会被摧毁。
求一颗炸弹最多能炸掉地图上总价值为多少的目标。
输入格式
第一行输入正整数 N 和 R ,分别代表地图上的目标数目和正方形的边长,数据用空格隔开。
接下来N行,每行输入一组数据,每组数据包括三个整数Xi,Yi,Wi,分别代表目标的x坐标,y坐标和价值,数据用空格隔开。
输出格式
输出一个正整数,代表一颗炸弹最多能炸掉地图上目标的总价值数目。
数据范围
$0<N≤10000$
$0≤Xi,Yi≤5000$
输入样例:
2 1
0 0 1
1 1 1
输出样例:
1
二维前缀和+各种内存优化
解法思路:我们首先观察题目,可以建立一个数组f[i][j]表示坐标为$(x_i,y_j)$上的权值,那么我们接着思考,因为题目上面说了要求算出这个边长为r的正方形面积,而且整个题目中,只有查询操作,没有修改操作,且内存只要略微省着用,就可以满足$O(n^2)$的条件,所以我们可以确认这一题可以使用二维前缀和。
二维前缀和,顾名思义,它的意义就是,在一个二维的空间中,求取前缀和,那么不同于一维前缀和,它的特点是什么?首先,我们可以观察,$f[i][j],f[i-1][j],f[i][j-1],a[i-1][j-1]$的关系,可以通过画一个矩阵,看几何意义,就可以很容易地明白它的代数意义 得出$f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j]$
我们把$(x_i,y_i)$作为一个格子,但是实际上他们只是一个点,所以说我们不妨认为这个点就是这个格子的中心,既然如此的话我们就可以认为是$(x_i−0.5,y_i−0.5)$
内存优化手段
- 你可以省略$a[i][j]$数组,将它用$f[i][j]$代替
- 因为$0<x[i],y[i]<=5000$,所以$f[x_i][j_i]+=w[i]$即可.就是说数据范围,告诉我们可以使用数组存储.也就是可以用二维前缀和
- 具体见代码吧
懒惰病
这道题目还有一个重点,就是要注意,坐标x,y都要加1,因为这道题目的坐标是从0开始的,而我们处理是从一开始的。
C++ 代码
#include<iostream>
#include<cstdio>
using namespace std;
int f[5010][5010],n,m,r,c,x,y,z,i,j,ans;
int main()
{
cin>>n>>m;
r=c=m;
for(i=1; i<=n; i++)
{
scanf("%d%d%d",&x,&y,&z);
x++,y++;
f[x][y]=z;
r=max(r,x);
c=max(c,y);
}
for(i=1; i<=r; i++)
for(j=1; j<=c; j++)
f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+f[i][j];
for(i=m; i<=r; i++)
for(j=m; j<=c; j++)
ans=max(ans,f[i][j]-f[i][j-m]-f[i-m][j]+f[i-m][j-m]);
cout<<ans<<endl;
return 0;
}
不判断r的话代码会tle的
f[x][y]=z 这里应该为+=
为什么要+=
必须是+=, 不能是=, 因为1个位置可能有多个目标
现在这个代码会SF,因为m会超过5010,数组越界了
过不了样例?
这个代码不过啊
#include [HTML_REMOVED]
using namespace std;
int n,a[5010][5010],m,maxx,maxy;
int main()
{
cin>>n>>m;
maxx=maxy=m;//这个很重要!
}
大佬燕这样特判一下才螚AC
谢谢!
能不能讲解一下这个是什么意思?
if(m>=5001)
{
cout<<a[5001][5001];
return 0;
}
这个表示的就是如果范围太大,就直接输出最大范围(超出范围的点没有意义)
好的谢谢
你好可不可以问一下问什么for循环的时候不是for(int i = 1; i <= maxx; i)和for(int j = 1; j <= maxy; j)而是要遍历到最大边界呢。(我那么写报错了不理解为什么会报错…)
而且,比如这题的n=200,m=2000,如果那样写的话for循环不会执行,但是我这样写就可以把整个地图的权值算进去。应该是这个问题。可以理解成我们在地图外面加了很多权值为0的空位。
题目也没有限制激光炸弹必须整个在范围内是不是。
我是蒟蒻也只能给您这么解释了。
注意初值要从m开始,否则i-m,j-m 会 RE。
感谢回复 我刚才理解了 纠结了n个小时的一道题 我写的for循环是for(int i=m;i<=maxx;i++) 然后就wrong answer了 我明白了是因为如果半径m大于maxx 这个循环根本执行不了 所以答案是错的0…
那maxx就没有必要
写得好
#include[HTML_REMOVED]
#include[HTML_REMOVED]
using namespace std;
int f[5010][5010],n,m,r,c,x,y,z,i,j,ans;
int main()
{
cin>>n>>m;
if(m>5000){
m=5000;
}
r=m;
c=m;
for(i=1; i<=n; i)
{
scanf(“%d%d%d”,&x,&y,&z);
x,y;
f[x][y]+=z;
r=max(r,x);
c=max(c,y);
}
for(i=1; i<=r; i)
for(j=1; j<=c; j++)
f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+f[i][j];
}
代码要稍微改下,才能ac
#include[HTML_REMOVED]
using namespace std;
int n,r;
int x,y,w;
int Max = 0,ans = 0;
int a[5010][5010],s[5010][5010];
int sum(int x1,int y1,int x2,int y2){
return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
}
int main(){
cin >> n >> r;
while(n –){
cin >> x >> y >> w;
x; y;
a[x][y] += w;
Max = max(Max,max(x,y));
}
for(int i = 1; i <= Max; i ){
for(int j = 1; j <= Max; j ){
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
}
}
for(int i = 1; i <= Max; i ){
for(int j = 1; j <= Max; j ){
int x1 = i,y1 = j;
int x2 = x1 + (r - 1),y2 = y1 + (r - 1);
ans = max(ans,sum(x1,y1,x2,y2));
}
}
cout << ans << endl;
return 0;
}
能看下 我这个哪错了吗 大佬们
这个地方应该是
f[x][y] += z;
不同目标可能在同一位置
啊对 秦大佬的代码要改一下 不然好像不能ac(笑哭)
所以那个所谓的 不妨认为这个点就是这个格子的中心 在代码中并没有体现(我还以为是黑科技压内存 /fad)
因为这句话,所以才直接套用模板公式啊
题目中矩形的数据范围R<=10^9,两重循环不会超时吗?
同想问(小声
跟r也没什么关系呀,又不是循环r,r用前缀和了呀
哦哦意思是小r
r的初始值赋的是m(代码中的),m的范围是10^9,还是两重循环肯定要超时啊。
第一个for循环就会更改r的值,r并不是最大的1e9
r=max(r,x),如果r是1e9的话,x怎么可能会去更新r,要更新也是往大里了更。
同想问*2
按下标从0开始就一直会wa…嘤嘤嘤 所以下标从0开始就不可以了吗?QAQ
不行, 数据越界了
二维数组f【】【】不需要初始化么。。
定义在主函数外的数组初值就是0
全局变量自动为0
大佬所言极是。
谢谢大佬 。。
谢谢大佬 。。
感谢大佬!
求问大佬 为啥炸不到两边是j-m 我画了图还是理解不了555
我看这个式子 r-1矩形上的点不是也在r矩形的边上吗 ?
但其有一个缺点,就是其爆炸范围,即那个边长为 R 的正方形的边必须和x,y轴平行。
若目标位于爆破正方形的边上,该目标不会被摧毁。
好的谢谢
qwq其实我想问f[i][j]-f[i][j-m]-f[i-m][j]+f[i-m][j-m] 我知道这是求r-1矩形的 但是这个r-1矩形上不是有些点也在r矩形的边上嘛 为什么可以炸掉
为什么r-1矩阵上会有点在r矩阵上啊?r-1矩阵最边上的点,都不会到r矩阵的边上吧.
之前对式子理解有误qwq 现在看懂了
您太强了.
请问一下,要想两边不被炸到,那么边长应该是m-2把,那么应该是
才对吧
我们把$(x_i,y_i)$作为一个格子,但是实际上他们只是一个点,所以说我们不妨认为这个点就是这个格子的中心,既然如此的话我们就可以认为是$(x_i-0.5,y_i-0.5)$
明白了多谢
若目标位于爆破正方形的边上,该目标不会被摧毁,可以这么理解
若爆炸长度为长度为r,若正好对其则他跨越了r+1个点,若r 等于3,若从左上角计算则是1, 2, 3, 4, 由于边界无法爆炸,那么只能碰到2,3,所以偏移一下,让其偏移后,变为0.5, 1.5, 2.5, 3.5,这样就可以取到1, 2, 3三个点,正好也就是r个点
秦大佬,我想问问为什么我r=c=m改成就会r=c=-1就会WA啊?我感觉逻辑上也没啥错啊
你看我们的循环,都是[1,r],[1,m]的前缀和遍历
如果说边界超过n,m呢,你看看题意
我知道了。一开始我想的是:【r和c不是取x和y的最大值吗?假如一开始r=c=m的意思就是,取max(max x,m)和max(max y,m)。但是我觉得不需要这样吧?直接取x和y的最大值就行了,为什么m更大的时候要取m?】,后来发现在for(i=m,i<=r;i++)的时候如果不这样做会出错。
这道题目还有一个重点,就是要注意,坐标x,y都要加1,因为这道题目的坐标是从0开始的,而我们处理是从一开始的。
存疑
我改成
for(i=0; i<n; i)
{
scanf(“%d%d%d”,&x,&y,&z);
x,y;
f[x][y]=z;
r=max(r,x);
c=max(c,y);
}
for(i=1; i<=r; i)
for(j=1; j<=c; j)
f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+f[i][j];
for(i=m; i<=r; i)
for(j=m; j<=c; j)
ans=max(ans,f[i][j]-f[i][j-m]-f[i-m][j]+f[i-m][j-m]);
cout<<ans<<endl;
一样可以通过;个人觉得 x y++ 的原因是 “若目标位于爆破正方形的边上,该目标不会被摧毁。”
所以至少xy要加1 才能真正摧毁这个目标
不知道是不是数据改动了 现在这样好像会WA
确实是的
因为是二维前缀和,目标可能位于a[0][i],或a[j][0]也就是数组边界,如果x, y不加1,而前缀和从[1][1]开始,那么数组边界的前缀和就没被处理,可能导致忽略数组边界上的一些目标。
因为0<x[i],y[i]<=5000,所以f[xi][ji]+=w[i]即可
这句话能解释一下吗?
就是说数据范围,告诉我们可以使用数组存储.也就是可以用二维前缀和
谢谢大佬