网站建设简介联系方式,广告设计培训机构,网站建站网站jp586 vip,外贸订单源码目录
题目链接
一些话 切入点
流程
套路
ac代码 题目链接 99. 激光炸弹 - AcWing题库
数#xff5e;啦#xff01;我草#xff0c;又~在#xff5e;水#xff5e;字#xff5e;数#xff5e;啦#xff01;我草#xff0c;又~在#xff5e;水#xff5e;字啦我草又~在水字数啦我草又~在水字数啦我草又~在水字数啦我草又~在水字数啦我草又~在水字数啦我草又~在水字数啦我草又~在水字数啦我草又~在水字数啦我草又~在水字
数啦我草又~在水字数啦我草又~在水字数啦我草又~在水字 一些话
数啦我草又~在水字数啦我草又~在水字数啦我草又~在水字数啦我草又~在水字数啦我草又~在水字数啦我草又~在水字数啦我草又~在水字数啦我草又~在水字数啦 切入点 现在有一种新型的激光炸弹可以摧毁一个包含 R×R 个位置的正方形内的所有目标。 激光炸弹的投放是通过卫星定位的但其有一个缺点就是其爆炸范围即那个正方形的边必须和 xy 轴平行。 求一颗炸弹最多能炸掉地图上总价值为多少的目标。 1. 求一个矩阵内值的总和符合二维前缀和的前提条件
2.求符合条件情况的最值符合枚举的特征
3.写法复杂条件多符合模拟的特征 数据范围 0≤R≤1e9 0N≤10000 0≤Xi,Yi≤5000 0≤Wi≤1000 1. xi,yi5e3,可能用到双循环枚举
二维数组 流程 1.模拟题列出伪代码
1.1读题得条件 地图上有 N 个目标用整数 Xi,Yi, 表示目标在地图上的位置每个目标都有一个价值 Wi。 注意不同目标可能在同一位置。 不能直接用cin读值要先用一个变量储存后再加入这个坐标对应的二维数组里 现在有一种新型的激光炸弹可以摧毁一个包含 R×R 个位置的正方形内的所有目标。 激光炸弹的投放是通过卫星定位的但其有一个缺点就是其爆炸范围即那个正方形的边必须和 xy 轴平行。 可以枚举一个坐标然后直接运算表示矩阵
1.2伪代码枚举部分 1.2.1确定要枚举什么如何缩小范围
1.题目要求一个与xy轴平行的矩阵值的总和最值所以要枚举这个矩阵矩阵边长是确定的可以通过枚举一个顶点来表示整个矩阵用二维前缀和求矩阵总和只要枚举左上角的顶点然后通过坐标运算就可以表示出右下角的顶点
2.枚举边界超过最大的xyr时没有意义所以只要取xryr的最大值即可
3.r的范围到1e9但是xy最大只有5e3超过5e3的部分可以直接舍弃r取5e31和r的最小值即可在确认nm前进行
1.2.3数据读入部分
题目xy从0开始因为要用前缀和前缀和里有减1的操作所以读入的坐标要先才能用
w储存读入的值然后加入到二维数组
1.2.2前缀和部分
双循环预处理前缀和数组然后用枚举的坐标查询前缀和与maxn比较 2.核验数据范围
1.5e3可以开一个二维数组
2.答案最多是n*w 1e7不用开long long 套路
1.相距为r的坐标的运算
相距为r的两个点a(x1,y1),b(x2,y2)
x2 x1 r - 1;
y2 x2 r - 1; 2.二维前缀和
//预处理
for(int i 1;i n;i){for(int j 1;j n;j){s[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1];}
}
// 查询左上角坐标(x1,y1)右上角坐标(x2,y2)
int res;
res s[x1][y1] - s[x1-1][y2] - s[x2][y1-1] s[x1-1][y1-1]; ac代码
// 1231 - 12 41
// 21:39 ~21:42
// 14:45~15:03
// 不能用cin读值要加等于x,yr太大时变小找最大xyr来确定边界
// 枚举左上角得右下角输出前缀和#include iostream
#include cstring
#include algorithm
#include cstdio
using namespace std;
const int N 5e3 10;
int n,m,r;
int s[N][N];//5e310级别的二维数组开不了longlong只能开一个数组
int maxn -0x3f3f3f3f;
int main(){int t;cin t r;r min(5001,r);//双循环的最大值因为要枚举坐标所以边界不能太大n m r;while(t--){int x,y,w;scanf(%d%d%d,x,y,w);x,y;s[x][y] w;n max(x,n);m max(y,m);}for(int i 1;i n;i){for(int j 1;j m;j){s[i][j] s[i][j-1] s[i-1][j] - s[i-1][j-1];}}for(int i 1;i r - 1 n;i){for(int j 1;j r - 1 m;j){maxn max(maxn,s[ir-1][jr-1] - s[ir-1][j-1] - s[i-1][jr-1] s[i-1][j-1]);}}cout maxn endl;return 0;
} 我草又~在水字数啦我草又~在水字数啦我草又~在水字数啦我草又~在水字数啦我草又~在水字数啦我草又~在水字数啦我草又~在水字数啦我草又~在水字数啦我草又~在水字
