AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

AcWing 99. 激光炸弹    原题链接    中等

作者: 作者的头像   秦淮岸灯火阑珊 ,  2019-01-20 12:24:32 ,  所有人可见 ,  阅读 13378


44


18

题目描述


一种新型的激光炸弹,可以摧毁一个边长为 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)$

内存优化手段
  1. 你可以省略$a[i][j]$数组,将它用$f[i][j]$代替
  2. 因为$0<x[i],y[i]<=5000$,所以$f[x_i][j_i]+=w[i]$即可.就是说数据范围,告诉我们可以使用数组存储.也就是可以用二维前缀和
  3. 具体见代码吧懒惰病
这道题目还有一个重点,就是要注意,坐标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;
}

66 评论


用户头像
ComistryMo   2022-12-09 16:45      3    踩      回复

不判断r的话代码会tle的


用户头像
15579642709   2022-03-25 19:40      3    踩      回复

f[x][y]=z 这里应该为+=

用户头像
September.   2023-03-05 10:56      1    踩      回复

为什么要+=

用户头像
xcb   2023-03-06 20:38    回复了 September. 的评论      3    踩      回复

必须是+=, 不能是=, 因为1个位置可能有多个目标


用户头像
岩专郭启童   2023-12-12 21:06      2    踩      回复

现在这个代码会SF,因为m会超过5010,数组越界了


用户头像
SPIDER_MAN   2020-07-19 22:45      1    踩      回复

过不了样例?


用户头像
熊二爱吃菜花   2024-03-11 22:33         踩      回复

这个代码不过啊


用户头像
masonpop   2022-05-08 17:03         踩      回复

#include [HTML_REMOVED]
using namespace std;
int n,a[5010][5010],m,maxx,maxy;
int main()
{
cin>>n>>m;
maxx=maxy=m;//这个很重要!

//if(n==2 && m==1000000000)
//{
    //cout<<2;
    //return 0;
//}
for(int i=1;i<=n;i++)
{
    int x,y,w;
    cin>>x>>y>>w;
    x++,y++;
    a[x][y]+=w;
    maxx=max(maxx,x);
    maxy=max(maxy,y);//最大值优化
}
for(int i=1;i<=5001;i++)
{
    for(int j=1;j<=5001;j++)//预处理前缀和,直接用a(前面都是预处理过的)
    {
        a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+a[i][j];//节省空间直接在原数组上递推
    }
}
int ans=0;
if(m>=5001)
{
    cout<<a[5001][5001];
    return 0;
}
for(int i=m;i<=5001;i++)//枚举右下角
{
    for(int j=m;j<=5001;j++)
    {
        ans=max(ans,a[i][j]-a[i-m][j]-a[i][j-m]+a[i-m][j-m]);//直接计算即可
    }
}
cout<<ans<<endl;
return 0;

}

大佬燕这样特判一下才螚AC

用户头像
秦淮岸灯火阑珊   2022-05-10 11:14         踩      回复

谢谢!

用户头像
ʕʔ_18   2022-07-12 17:58         踩      回复

能不能讲解一下这个是什么意思?

if(m>=5001)
{
cout<<a[5001][5001];
return 0;
}

用户头像
masonpop   2022-07-14 09:06    回复了 ʕʔ_18 的评论         踩      回复

这个表示的就是如果范围太大,就直接输出最大范围(超出范围的点没有意义)

用户头像
ʕʔ_18   2022-07-14 13:35    回复了 masonpop 的评论         踩      回复

好的谢谢

用户头像
芋泥小雪球   2023-03-22 15:41         踩      回复

你好可不可以问一下问什么for循环的时候不是for(int i = 1; i <= maxx; i)和for(int j = 1; j <= maxy; j)而是要遍历到最大边界呢。(我那么写报错了不理解为什么会报错…)

用户头像
masonpop   2023-03-22 17:07    回复了 芋泥小雪球 的评论         踩      回复

而且,比如这题的n=200,m=2000,如果那样写的话for循环不会执行,但是我这样写就可以把整个地图的权值算进去。应该是这个问题。可以理解成我们在地图外面加了很多权值为0的空位。

用户头像
masonpop   2023-03-22 17:08    回复了 芋泥小雪球 的评论         踩      回复

题目也没有限制激光炸弹必须整个在范围内是不是。

用户头像
masonpop   2023-03-22 17:09    回复了 芋泥小雪球 的评论         踩      回复

我是蒟蒻也只能给您这么解释了。

用户头像
masonpop   2023-03-22 17:10    回复了 芋泥小雪球 的评论         踩      回复

注意初值要从m开始,否则i-m,j-m 会 RE。

用户头像
芋泥小雪球   2023-03-22 17:12    回复了 masonpop 的评论         踩      回复

感谢回复 我刚才理解了 纠结了n个小时的一道题 我写的for循环是for(int i=m;i<=maxx;i++) 然后就wrong answer了 我明白了是因为如果半径m大于maxx 这个循环根本执行不了 所以答案是错的0…

用户头像
麻雀001   2024-06-09 17:03         踩      回复

那maxx就没有必要


用户头像
lanqiaobei11   2022-02-09 14:25         踩      回复

写得好


用户头像
ACD   2021-11-14 10:52         踩      回复

#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];

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;

}
代码要稍微改下,才能ac


用户头像
Jäger   2021-03-17 09:05         踩      回复

#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;
}
能看下 我这个哪错了吗 大佬们


用户头像
hufu   2020-08-10 17:07         踩      回复
  f[x][y]=z;

这个地方应该是f[x][y] += z;
不同目标可能在同一位置

用户头像
time_4   2020-09-04 09:57         踩      回复

啊对 秦大佬的代码要改一下 不然好像不能ac(笑哭)


用户头像
bfw   2020-07-15 19:55         踩      回复

所以那个所谓的 不妨认为这个点就是这个格子的中心 在代码中并没有体现(我还以为是黑科技压内存 /fad)

用户头像
KevinFreem   2023-01-18 00:10         踩      回复

因为这句话,所以才直接套用模板公式啊


用户头像
253718226   2020-03-12 11:29         踩      回复

题目中矩形的数据范围R<=10^9,两重循环不会超时吗?

用户头像
ddkk   2020-06-26 17:43         踩      回复

同想问(小声

用户头像
帅   2020-07-13 17:03    回复了 ddkk 的评论         踩      回复

跟r也没什么关系呀,又不是循环r,r用前缀和了呀

用户头像
Ravanla   2020-07-16 18:26    回复了 帅 的评论         踩      回复

哦哦意思是小r

用户头像
Febuxostat   2020-07-27 09:22    回复了 帅 的评论         踩      回复

r的初始值赋的是m(代码中的),m的范围是10^9,还是两重循环肯定要超时啊。

用户头像
帅   2020-08-03 17:02    回复了 Febuxostat 的评论         踩      回复

第一个for循环就会更改r的值,r并不是最大的1e9

用户头像
Febuxostat   2020-08-04 20:45    回复了 帅 的评论         踩      回复

r=max(r,x),如果r是1e9的话,x怎么可能会去更新r,要更新也是往大里了更。

用户头像
苏盖昆吞   2020-08-26 16:49         踩      回复

同想问*2


用户头像
许可可可可   2019-12-09 20:43         踩      回复

按下标从0开始就一直会wa…嘤嘤嘤 所以下标从0开始就不可以了吗?QAQ

用户头像
Bug-Free   2020-03-18 16:28      1    踩      回复

不行, 数据越界了


用户头像
鬼子进村   2019-08-17 16:30         踩      回复

二维数组f【】【】不需要初始化么。。

用户头像
Ryougi   2019-08-17 16:51         踩      回复

定义在主函数外的数组初值就是0

用户头像
秦淮岸灯火阑珊   2019-08-17 18:23         踩      回复

全局变量自动为0

用户头像
秦淮岸灯火阑珊   2019-08-17 18:23    回复了 Ryougi 的评论         踩      回复

大佬所言极是。

用户头像
鬼子进村   2019-08-17 19:02    回复了 Ryougi 的评论         踩      回复

谢谢大佬 。。

用户头像
鬼子进村   2019-08-17 19:02    回复了 秦淮岸灯火阑珊 的评论         踩      回复

谢谢大佬 。。

用户头像
秦淮岸灯火阑珊   2019-08-17 20:20    回复了 鬼子进村 的评论         踩      回复

感谢大佬!


用户头像
朝暮不思   2019-08-04 22:52         踩      回复

求问大佬 为啥炸不到两边是j-m 我画了图还是理解不了555

用户头像
朝暮不思   2019-08-04 23:10         踩      回复

我看这个式子 r-1矩形上的点不是也在r矩形的边上吗 ?

用户头像
秦淮岸灯火阑珊   2019-08-05 07:27    回复了 朝暮不思 的评论         踩      回复

但其有一个缺点,就是其爆炸范围,即那个边长为 R 的正方形的边必须和x,y轴平行。
若目标位于爆破正方形的边上,该目标不会被摧毁。

用户头像
朝暮不思   2019-08-05 08:28    回复了 秦淮岸灯火阑珊 的评论         踩      回复

好的谢谢

用户头像
朝暮不思   2019-08-05 08:52    回复了 秦淮岸灯火阑珊 的评论         踩      回复

qwq其实我想问f[i][j]-f[i][j-m]-f[i-m][j]+f[i-m][j-m] 我知道这是求r-1矩形的 但是这个r-1矩形上不是有些点也在r矩形的边上嘛 为什么可以炸掉

用户头像
秦淮岸灯火阑珊   2019-08-05 14:42    回复了 朝暮不思 的评论         踩      回复

为什么r-1矩阵上会有点在r矩阵上啊?r-1矩阵最边上的点,都不会到r矩阵的边上吧.

用户头像
朝暮不思   2019-08-05 16:55    回复了 秦淮岸灯火阑珊 的评论         踩      回复

之前对式子理解有误qwq 现在看懂了

用户头像
秦淮岸灯火阑珊   2019-08-05 18:03    回复了 朝暮不思 的评论         踩      回复

您太强了.


用户头像
脆脆鲨   2019-06-14 11:39         踩      回复

请问一下,要想两边不被炸到,那么边长应该是m-2把,那么应该是

ans=max(ans,f[i][j]-f[i][j-m+1]-f[i-m+1][j]+f[i-m+1][j-m+1]);

才对吧

用户头像
秦淮岸灯火阑珊   2019-06-14 18:18         踩      回复

我们把$(x_i,y_i)$作为一个格子,但是实际上他们只是一个点,所以说我们不妨认为这个点就是这个格子的中心,既然如此的话我们就可以认为是$(x_i-0.5,y_i-0.5)$

用户头像
脆脆鲨   2019-06-15 18:03    回复了 秦淮岸灯火阑珊 的评论         踩      回复

明白了多谢


用户头像
Dy   2019-06-07 13:01         踩      回复

若目标位于爆破正方形的边上,该目标不会被摧毁,可以这么理解

若爆炸长度为长度为r,若正好对其则他跨越了r+1个点,若r 等于3,若从左上角计算则是1, 2, 3, 4, 由于边界无法爆炸,那么只能碰到2,3,所以偏移一下,让其偏移后,变为0.5, 1.5, 2.5, 3.5,这样就可以取到1, 2, 3三个点,正好也就是r个点


用户头像
满船清梦压星河   2019-05-19 11:10         踩      回复

秦大佬,我想问问为什么我r=c=m改成就会r=c=-1就会WA啊?我感觉逻辑上也没啥错啊

用户头像
秦淮岸灯火阑珊   2019-05-19 13:37         踩      回复

你看我们的循环,都是[1,r],[1,m]的前缀和遍历

用户头像
秦淮岸灯火阑珊   2019-05-19 13:37         踩      回复

如果说边界超过n,m呢,你看看题意

用户头像
满船清梦压星河   2019-05-19 13:40    回复了 秦淮岸灯火阑珊 的评论         踩      回复

我知道了。一开始我想的是:【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++)的时候如果不这样做会出错。


用户头像
itdef   2019-05-07 17:17         踩      回复

这道题目还有一个重点,就是要注意,坐标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 才能真正摧毁这个目标

用户头像
许可可可可   2019-12-09 20:41         踩      回复

不知道是不是数据改动了 现在这样好像会WA

用户头像
Carbon   2020-01-29 19:11    回复了 许可可可可 的评论         踩      回复

确实是的

用户头像
阿斯蒂芬   2021-07-17 00:09         踩      回复

因为是二维前缀和,目标可能位于a[0][i],或a[j][0]也就是数组边界,如果x, y不加1,而前缀和从[1][1]开始,那么数组边界的前缀和就没被处理,可能导致忽略数组边界上的一些目标。


用户头像
Gerald   2019-05-02 22:25         踩      回复

因为0<x[i],y[i]<=5000,所以f[xi][ji]+=w[i]即可
这句话能解释一下吗?

用户头像
秦淮岸灯火阑珊   2019-05-03 13:03         踩      回复

就是说数据范围,告诉我们可以使用数组存储.也就是可以用二维前缀和

用户头像
Gerald   2019-05-05 13:14    回复了 秦淮岸灯火阑珊 的评论         踩      回复

谢谢大佬


App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息