蓝桥杯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;
}

最近更新

  1. leetcode705-Design HashSet

    2024-04-03 08:46:03       8 阅读
  2. Unity发布webgl之后打开streamingAssets中的html文件

    2024-04-03 08:46:03       8 阅读
  3. vue3、vue2中nextTick源码解析

    2024-04-03 08:46:03       8 阅读
  4. 高级IO——React服务器简单实现

    2024-04-03 08:46:03       8 阅读
  5. 将图片数据转换为张量(Go并发处理)

    2024-04-03 08:46:03       7 阅读
  6. go第三方库go.uber.org介绍

    2024-04-03 08:46:03       8 阅读
  7. 前后端AES对称加密 前端TS 后端Go

    2024-04-03 08:46:03       10 阅读

热门阅读

  1. Vue-前端应用开发平时作业第二章作业2

    2024-04-03 08:46:03       4 阅读
  2. Android 11 init进程对Selinux的处理

    2024-04-03 08:46:03       5 阅读
  3. 读《Spring实战》第二章:装配bean

    2024-04-03 08:46:03       1 阅读
  4. oracle杀外部连接会话

    2024-04-03 08:46:03       3 阅读
  5. 高级排序算法-快速排序

    2024-04-03 08:46:03       5 阅读
  6. Jenkins 自动化更新 Stable Diffusion 介绍

    2024-04-03 08:46:03       2 阅读
  7. maya移除节点 修改节点

    2024-04-03 08:46:03       4 阅读