题目
题解
做法1
没错，这个是我的做法，我们首先要搞明白，(R*R)的矩阵最多炸到(R*R)个位置，而且最优的情况绝对不是炸弹在整点的情况（因为边缘炸不到。）
看这个图：
黑色的矩阵就只炸到了(1,1)，绿色的矩阵却可以炸到(2,1)和(1,1)，多炸了一个，为什么？
因为两个都是炸不到(0,1)，但是绿色能炸到(2,1)，更高效的利用了边长为2这个性质。（画个图就知道左右移动的话炸到这两个是极限了）
然后我们上下移动就可以发现可以炸到四个了，当然，这也是纵向的极限了，不难想出对于(R*R)的正方形，我们最多能炸到(R*R)个位置，然后我们就可以把题目看成一个能炸((R-1)*(R-1))矩阵范围且边缘能炸到的炸弹了。
对于炸弹，我们换个角度看，我们站在正方形的右下角来看整个矩阵，如果我在(R,R)放个炸弹，这样(1,1)和(R,R)都会炸到。
做二维前缀和，然后每个点默认判断在这个点放炸弹，然后取max就行了。
代码仍然是全部下标从1开始，同时默认炸弹的横纵坐标都是大于等于(R)的（因为如果小于的话可以移动到大于等于，这样覆盖的范围更大了，而且原本覆盖的现在也能覆盖，更优秀，所以默认大于等于）。
时间复杂度：(O(5000^2))
#include<cstdio>
#include<cstring>
using namespace std;
int a[5100][5100],n=5001,m,R;
inline int mymax(int x,int y){return x>y?x:y;}
int main()
{
scanf("%d%d",&m,&R);if(R>n)R=n;
for(int i=1;i<=m;i++)
{
int x,y,c;scanf("%d%d%d",&x,&y,&c);
a[x+1][y+1]=c;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
}
int ans=0;
for(int i=R;i<=n;i++)
{
for(int j=R;j<=n;j++)ans=mymax(ans,a[i][j]-a[i-R][j]-a[i][j-R]+a[i-R][j-R]);
}
printf("%d
",ans);
return 0;
}
做法2
什么，前面那种太慢了？
STO： https://www.acwing.com/solution/content/1243/
我们可以采用扫描线的方式，由于我们采用了右下角看炸弹的观察角度，所以，我们思考一下如果一个位置能被炸弹炸到的话，炸弹会放在哪里呢？很明显是：((x,y)-(x+R-1,y+R-1))的这么一个范围，那么我们就可以把这个矩阵全部加上这个位置的权值，视为如果我们在这个区域放炸弹，就会得到这个位置的价值。
那么现在我们只需要找到一个权值最大的位置就行了。
对于这个，我们仍然可以采用差分加前缀和的方式找到权值最大的位置，但是复杂度不变。
于是奆佬用了扫描线加线段树（至于扫描线加线段树怎么做，一般会了扫描线这个自然就会了，如果不会可以看代码或者去模一下奆佬的博客学习一下，我就不说了吧），这里提醒一下，由于求最大值，所以线段树我们不用(x,y)都求一次，求一个就行了（周长的话是需要(x,y)都求一遍的）。
时间复杂度：(O(Nlog5000))
代码：
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int maxn = 1e5 + 233;
#define ls(x) (x << 1)
#define rs(x) ((x << 1) + 1)
struct Node{
int l, r, dat, mk;
#define l(x) t[x].l
#define r(x) t[x].r
#define dat(x) t[x].dat
#define mk(x) t[x].mk
}t[maxn * 4];
void build(int p, int l, int r)
{
l(p) = l; r(p) = r;
if(l == r)
{
dat(p) = 0; mk(p) = 0;
return ;
}
int mid = (l + r) >> 1;
build(ls(p), l, mid);
build(rs(p), mid + 1, r);
dat(p) = 0; mk(p) = 0;
}
void spr(int p)
{
if(mk(p))
{
dat(ls(p)) += mk(p);
dat(rs(p)) += mk(p);
mk(ls(p)) += mk(p);
mk(rs(p)) += mk(p);
mk(p) = 0;
}
}
void update(int p, int l, int r, int v)
{
if(l <= l(p) && r >= r(p))
{
dat(p) += v;
mk(p) += v;
return ;
}
spr(p);
int mid = (l(p) + r(p)) >> 1;
if(l <= mid) update(ls(p), l, r, v);
if(r > mid) update(rs(p), l, r, v);
dat(p) = max(dat(ls(p)), dat(rs(p)));
}
int ask(int p, int l, int r)
{
if(l <= l(p) && r >= r(p)) return dat(p);
spr(p);
int mid = (l(p) + r(p)) >> 1;
int res = 0;
if(l <= mid) res = max(res, ask(ls(p), l, r));
if(r > mid) res = max(res, ask(rs(p), l, r));
return res;
}
vector<pair<int, pair<int,pii> > > org;
int main()
{
int n, r;
cin >> n >> r;
for(int i = 1; i <= n; i++)
{
int x, y, z;
cin >> x >> y >> z;
y++;
org.push_back({x,{z, {y, y + r - 1}}});
org.push_back({x + r,{-z, {y, y + r - 1}}});
}
sort(org.begin(), org.end());
int ans = 0;
build(1,1,20001);
for(int i = 0; i < org.size(); i++)
{
pii now = org[i].second.second;
int ty = org[i].second.first;
update(1, now.first, now.second, ty);
ans = max(ans, ask(1, 1, 20001));
}
cout<<ans;
}
作者：这个显卡不太冷
链接：https://www.acwing.com/solution/content/1243/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。