蓝桥杯23年第十四届省赛-子矩阵 |暴力、滑动窗口单调队列

题目链接：

蓝桥杯2023年第十四届省赛真题-子矩阵 - C语言网 (dotcpp.com)

6.子矩阵 - 蓝桥云课 (lanqiao.cn)

说明：

单调队列、滑动窗口模板。 先求每行的滑动窗口（最大值和最小值都求），再对求出来的滑动窗口再求每列的。 参考学习链接：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;
}