不判断r的话代码会tle的

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

为什么要+=

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

宣传亿下个人主页

https://www.acwing.com/blog/content/31065/

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

谢谢！

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

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…

写得好

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

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;

这个地方应该是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把，那么应该是

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

才对吧

我们把$(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]即可
这句话能解释一下吗？

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

谢谢大佬