tip:真是让大家久等了因为前段时间刚刚接轨嵌入式学习就拉下了这里真诚的向大家道歉以后算法一周一更我的一周是周日到下周六这样两头宽松一些欢迎大家批评指正前缀和作用快速求出一段区间和【模板】缀和1题目2链接【模板】前缀和3解析1创建前缀和数组f[i]: 区间[1,i]所有元素和f[i] f[i-1]a[i]2,利用前缀和[l,r]:f[r]-f[l-1]tip:数组下标从一开始4代码#includeiostream using namespace std; typedef long long ll; const int N 1e58; ll a[N],f[N]; int main(){ ll n,m; cin n m; for(int i 1;i n;i) cin a[i]; for(int i 1;i n;i) f[i] f[i-1]a[i]; while(m--){ int l,r; cin l r; cout f[r]-f[l-1] endl; } return 0; }P1115 最大子段和1题目2链接https://www.luogu.com.cn/problem/P11153解析以a[i]为结尾所有子区间最大子段和f[i]-[1.i-1]中所有前缀和的最小值-p min (p,f[i])4代码#includeiostream using namespace std; const int N 2e58; typedef long long ll; ll a[N],f[N]; int main(){ int n; cin n; for(int i 1;i n;i) cin a[i]; for(int i 1;i n;i) f[i] f[i-1]a[i]; ll ret -1e20; ll p 0; for(int i 1;in;i){ ret max(ret,f[i]-p); p min(p,f[i]); } cout ret endl; return 0; }【模板】二维前缀和1题目2链接【模板】二维前缀和3解析1,二维前缀和作用快速查询二维数组中某子矩阵中所有元素的和2二维前缀和公式推导记忆方法即可不需要死记硬背这里可以理解为小时候最为熟悉的直角坐标系由一个点坐标变成一个小块f[i][j] f[i-1][j]f[i][j-1]-f[i-1][j-1]a[i][j]3做法1预处理一个二维前缀和矩阵f[i][j]:(1,1)到(i,j)所有元素和f[i][j] f[i-1][j]f[i][j-1]-f[i-1】[j-1]a[i][j]2用二维前缀和解决问题(x1,y1) ~ (x2,y2)f[x2][y2]-f[x1-1][y2]-f[x2][y1-1]f[x1-1][y1-1]4代码#includeiostream using namespace std; typedef long long ll; const int N 1010; ll f[N][N]; ll a[N][N]; int main(){ int n,m,q; cin n m q; for(int i 1;i n;i){ for(int j 1;j m;j){ cin a[i][j]; f[i][j] f[i-1][j]f[i][j-1]-f[i-1][j-1]a[i][j]; } } while(q--){ int x1,y1,x2,y2; cin x1 y1 x2 y2; cout f[x2][y2]-f[x1-1][y2]-f[x2][y1-1]f[x1-1][y1-1] endl; } return 0; }P2280 [HNOI2003] 激光炸弹1题目2链接https://www.luogu.com.cn/problem/P22803解析如何计算一颗炸弹最多能炸掉地图上总价值为多少的目标-首先为了缩减枚举范围炸弹是必须和小块边重合确保范围是最大的-所以接下来就是找边长m的大正方形中价值最大的了二维前缀和4代码#includeiostream using namespace std; const int N 5010; int a[N][N]; int f[N][N]; int main(){ int n,m; cin n m; while(n--){ int x,y,v; cin x y v; x; y; //变成熟悉的数组下标从1开始 a[x][y] v;//题目要求可能存在多个目标在同一位置上的情况 } //前缀和数组 for(int i 1;i5001;i){//没有告诉数组行列直接取最大 for(int j 1;j 5001;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,5001);//防止越界 //枚举所有边长为m的正方形 for(int x2 m;x2 5001;x2){//用右下角下标对应前缀和公式 for(int y2 m;y2 5001;y2){ int x1 x2-m1,y1 y2-m1; ret max(ret,f[x2][y2]-f[x1-1][y2]-f[x2][y1-1]f[x1-1][y1-1]); } } cout ret endl; return 0; }
