子矩阵
题目 子矩阵
思路分析
所有子矩阵里的最大值*最小值相加 结果模上一个数
其实最麻烦的地方就是怎么求出子矩阵的最大值和最小值
在大矩阵里给定小矩阵的宽和高 其实就类似于一个滑动窗口
固定宽 不断在整个宽里滑动
在滑动窗口中求最大值和最小值倒是容易了 就是模版的内容
但模板毕竟是一维的
那想办法把这个二维的转变成一维
把n行拆分成n个一维的单调队列 可以预处理出来每个宽B高1的矩形的最大值和最小值
那么对于一个高A的矩形 就只需要对这些最大值最小值里面再做一次一维的滑动窗口
就能得到整个宽B高A的矩形的最大值和最小值了
那么要算整个矩形中所有子矩形的面积之和也是顺水推舟了
晕了……这tm只是c组的第4题 …………
代码实现
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1010,MOD=998244353;
int w[N][N];//大矩阵
int rmax[N][N],rmin[N][N];//每行窗口为B的最大值和最小值
int q[N];
int n,m,A,B;
void get_max(int a[],int b[],int tot,int k)
{
int hh=0,tt=-1;
for(int i=0;i<tot;i++)
{
if(hh<=tt && i-q[hh]>=k)
hh++;
//求最大 递减区间 若出现向上 出队
while(hh<=tt && a[i]>=a[q[tt]])
tt--;
q[++tt]=i;
//当前区间的最大值为队头
b[i] = a[q[hh]];
}
}
void get_min(int a[],int b[],int tot,int k)
{
int hh=0,tt=-1;
for(int i=0;i<tot;i++)
{
if(hh<=tt && i-q[hh]>=k)
hh++;
//求最小 递增区间 若出现向下 出队
while(hh<=tt && a[i]<=a[q[tt]])
tt--;
q[++tt]=i;
//当前区间的最大值为队头
b[i] = a[q[hh]];
}
}
int main()
{
scanf("%d%d%d%d", &n, &m, &A, &B);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
scanf("%d", &w[i][j]);
//预处理出每一行的rmax和rmin
for(int i=0;i<n;i++){
//大宽度为m 小窗口为B
get_max(w[i],rmax[i],m,B);
get_min(w[i],rmin[i],m,B);
}
int res = 0;
//每个窗口里有个最大值和最小值已经求出来了
//现在对于同一个窗口（固定宽） 要求出所有行的的最大值
//用temp先把每个窗口的最大值和最小值存住 然后枚举每一行 做一次A的滑动窗口
//结果就会是整个矩形的最大值和最小值
//存放在Rectmax和Rectmin中
int temp[N],Rectmax[N],Rectmin[N];
for (int i=B-1;i<m;i++)
{
for(int j=0;j<n;j++)
temp[j]=rmax[j][i];
get_max(temp,Rectmax,n,A);
for(int j=0;j<n;j++)
temp[j] = rmin[j][i];
get_min(temp, Rectmin, n, A);
//把所有矩形的最大值和最小值相乘 累加起来 模上mod 就是答案
for(int j=A-1;j<n;j++)
res=(res+(LL)Rectmax[j]*Rectmin[j])%MOD;
}
printf("%d\n", res);
return 0;
}
💬 评论