蓝桥杯好题推荐—激光炸弹

🌈个人主页： 💫个人格言:“成为自己未来的主人~”

题目链接

解题思路

在这道题目当中，我们使用的是二维前缀和数组的思想，我们首先可以常见一个二维前缀和数组和一个存放价值的数组。 #include using namespace std; const int N = 5e3+10; int f[N][N];//前缀和存放数组 int a[N][N]; 然后，我们先对这个价值数组进行处理，由于后面使用的时候，我们是从（1,1）开始的，所以，我们统一把坐标往右下移动一位。 int n,m;cin»n»m; //先把数据存放到价值的数组中 for(int i=1;i<=n;i++) { int x,y,v;cin»x»y»v; x++; y++;//使得下标从（1,1）开始 a[x][y]+=v; } 此外，这里还有一个特别需要注意的点，就是题目中所同一个位置可能存放多个价值，所以，我们在进行价值处理的时候，应使用的是。 a[x][y]+=v; 然后，我们构建二维前缀和数组。 n = 5005;//确保可以找到全部的元素 for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j]; } } 我们这里设置的将所有的数组的元素都包含在内。 然后，我们对每个边长的这个正方形进行遍历，确保它走过了所有的元素，然后获取最大值。 //遍历 int ret = 0; m =min(m,n); for(int x2=m;x2<=n;x2++) { for(int y2=m;y2<=n;y2++) { int x1 = x2-m+1; int y1 = y2-m+1; ret = max(ret,f[x2][y2]-f[x1-1][y2]-f[x2][y1-1]+f[x1-1][y1-1]); } } 在这个之前，我们需要将m设置为m何n的最小值，因为这个正方形的边长是可能大于这个整个数组的长度的。

代码解决

#include using namespace std; const int N = 5e3+10; int f[N][N];//前缀和存放数组 int a[N][N]; int main() { int n,m;cin»n»m; //先把数据存放到价值的数组中 for(int i=1;i<=n;i++) { int x,y,v;cin»x»y»v; x++; y++;//使得下标从（1,1）开始 a[x][y]+=v; } //构建二维前缀和数组 n = 5005;//确保可以找到全部的元素 for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j]; } } //遍历 int ret = 0; m =min(m,n); for(int x2=m;x2<=n;x2++) { for(int y2=m;y2<=n;y2++) { int x1 = x2-m+1; int y1 = y2-m+1; ret = max(ret,f[x2][y2]-f[x1-1][y2]-f[x2][y1-1]+f[x1-1][y1-1]); } } cout«ret«endl; return 0; } 好了，今天的内容就到这里，我们明天再见。