题目链接:
蓝桥杯2023年第十四届省赛真题-子矩阵 - C语言网 (dotcpp.com)
说明:
单调队列、滑动窗口模板。 先求每行的滑动窗口(最大值和最小值都求),再对求出来的滑动窗口再求每列的。 参考学习链接:https://blog.csdn.net/weixin_72060925/article/details/127952750
对于固定大小的子矩阵, 又是求子矩阵里的最值,那么就要考虑用滑动窗口来做,因为子矩阵大小固定,即行和列大小固定,滑动窗口大小也是在窗口大小固定时使用的。
可以想象一下一个子矩阵,先求每行的滑动窗口(最大值和最小值都求),那么这个子矩阵每行(共a行)的b个(列)元素,都变成一个最值表示,a*b个变成了a个,再对求出来的滑动窗口再求每列的滑动窗口,就是这a行上面的a个元素变成一个最值,也就是一个子矩阵“浓缩”成了一个最值。
如果大小不确定的子矩阵问题,且涉及的是子矩阵的元素和,就要考虑前缀和降维。
代码:
正解:
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e3+10;
int ans=0;
int mod=998244353;
int g[N][N];
int q[N];
int line_max[N][N];int line_min[N][N];
int minv[N][N];int maxv[N][N];
//四重循环暴力
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m,a,b;
cin>>n>>m>>a>>b;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++)
cin>>g[i][j];
}
//每行求滑动窗口 对该行的某个起点(j)求出窗口里的最大值
for(int i=0;i<n;i++){
int h=0,t=-1;//注意h和t写在第一层里 ,每行的滑动窗口不相关
for(int j=0;j<m;j++){
if(h<=t&&q[h]<j-b+1){
h++;
}
while(h<=t&&g[i][q[t]]<=g[i][j]){
t--;
}
q[++t]=j;
if(j-b+1>=0) line_max[i][j-b+1]=g[i][q[h]];
}
}
//每行求滑动窗口 对该行的某个起点(j)求出窗口里的最小值
for(int i=0;i<n;i++){
int h=0,t=-1;//注意h和t写在第一层里 ,每行的滑动窗口不相关
for(int j=0;j<m;j++){
if(h<=t&&q[h]<j-b+1){
h++;
}
while(h<=t&&g[i][q[t]]>=g[i][j]){
t--;
}
q[++t]=j;
if(j-b+1>=0) line_min[i][j-b+1]=g[i][q[h]];
}
}
//对已经求出的行滑动窗口(每行的每个窗口变成由最大值代表的一个数)最大值矩阵 求每列的滑动窗口最大值
for(int j=0;j<m-b+1;j++){
int h=0,t=-1;
for(int i=0;i<n;i++){
if(h<=t&&q[h]<i-a+1)
h++;
while(h<=t&&line_max[q[t]][j]<=line_max[i][j])
t--;
q[++t]=i;
//第j列上的 第i-a+1个窗口 保存对应最大值
if(i-a+1>=0) maxv[i-a+1][j]=line_max[q[h]][j];
}
}
for(int j=0;j<m-b+1;j++){
int h=0,t=-1;
for(int i=0;i<n;i++){
if(h<=t&&q[h]<i-a+1)
h++;
while(h<=t&&line_min[q[t]][j]>=line_min[i][j])
t--;
q[++t]=i;
//第j列上的 第i-a+1个窗口 保存对应最大值
if(i-a+1>=0) minv[i-a+1][j]=line_min[q[h]][j];
}
}
for(int i=0;i<n-a+1;i++){
for(int j=0;j<m-b+1;j++){
ans=(ans+minv[i][j]*maxv[i][j]%mod)%mod;
}
}
cout<<ans;
return 0;
}
暴力(70%蓝桥官网测试点):
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e3+10;
int ans=0;
int mod=998244353;
int g[N][N];
//四重循环暴力
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m,a,b;
cin>>n>>m>>a>>b;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++)
cin>>g[i][j];
}
for(int i=0;i<n-a+1;i++){
for(int j=0;j<m-b+1;j++){
int mx=0,mn=1e9;
for(int k=0;k<a;k++){
for(int l=0;l<b;l++){
mx=max(mx,g[i+k][j+l]);
mn=min(mn,g[i+k][j+l]);
}
}
ans=(ans+mx*mn%mod)%mod;
}
}
cout<<ans;
return 0;
}