P3397 地毯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
方法1 欺负数据小 暴力水过
#include<iostream>
using namespace std;
const int N=1010;
int a[N][N];
int main(){
int n,m;
cin>>n>>m;
for(int i=0;i<m;i++){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
for(int q=x1;q<=x2;q++){
for(int w=y1;w<=y2;w++){
a[q][w]++;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout<<a[i][j]<<' ';
}
cout<<endl;
}
return 0;
}
方法2
前缀和 二维数组差分
不会差分的建议先去看看一维数组的差分
洛谷 P2367 语文成绩 刷题笔记-CSDN博客
#include<iostream>
using namespace std;
const int N=1010;
int a[N][N],b[N][N];
void add(int x1,int y1,int x2,int y2,int x){
b[x1][y1]+=x;
b[x1][y2+1]-=x;
b[x2+1][y1]-=x;
b[x2+1][y2+1]+=x;
}
int n,m;
int main(){
cin>>n>>m;
for(int i=0;i<m;i++){
int a,b,c,d;
cin>>a>>b>>c>>d;
add(a,b,c,d,1);
}
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]+b[i][j];
//扫描缓存池 计算前缀和
//看不懂缓存池的先去看一维数组差分
//上面提到了
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout<<a[i][j]<<' ';
}
cout<<endl;
}
return 0;
}
add函数推导
a数组是b数组的前缀和数组,对b数组的b[i][j]的修改,会影响到a数组中从a[i][j]及往后的每一个数。
二维前缀和推导文章来源:https://www.toymoban.com/news/detail-771222.html
文章来源地址https://www.toymoban.com/news/detail-771222.html
到了这里,关于洛谷 P3397 地毯 刷题笔记 二维差分矩阵的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!