蓝桥杯2023年第十四届省赛真题-子矩阵

题目来自DOTCPP：

暴力思路（两个测试点超时）：

题目要求我们求出子矩阵的最大值和最小值的乘积，我们可以枚举矩阵中的所有点，以这个点为其子矩阵的左上顶点，然后判断一下能不能构成子矩阵。如果可以，我们在遍历这个子矩阵，求出子矩阵的最大值和最小值，将它加起来。同时，由于题目告诉我们答案可能非常大，即使我们用long long 类型来存答案，也会溢出。因此，我们答案每次加上子矩阵的最小值和最大值的乘积后，可以对998244353 取模，这样可以保证最终答案数据不会溢出。

暴力代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1020;int n, m, a, b;
int arr[N][N];signed main(){cin >> n >> m >> a >>b;for(int i =1; i <= n; i++){for(int j = 1; j <= m; j++){cin >> arr[i][j];}}int s = 0;//枚举矩阵每个点for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){if(i+a-1 > n || j+b-1 > m) continue;int ssmin= 1e9+10, ssmax = -1;//找到矩阵中的最大值和最小值for(int k = i; k <= i+a-1; k++){for(int l = j; l <= j+b-1; l++){int x = arr[k][l];ssmax = max(ssmax, x);ssmin = min(ssmin, x);// cout << ssmin << " " << ssmax << endl;}}s += ssmax * ssmin;//题目说了答案非常大 即使是long long 类型也会溢出//所以我们每次的答案%998244353s = s%998244353;// cout << ssmin << "*" << ssmax << endl;}}cout << s  << endl;return 0;
}

优化思路-滑动窗口+单调队列：

暴力代码的思路是枚举每个点，将这个点当成子矩阵的左上角顶点，然后找到子矩阵最小值和最大值，答案加上最小值和最大值的乘积。我们可以对找到子矩阵的最小值和最大值优化，就不会超时了。

窗口每一次都是从一行的最左边或每一列的上边开始出发：

①我们先对矩阵的每一行，让长度为b的窗口开始滑动，找到这一行的最小值和最大值，赋给该窗口的左顶点。

②我们在对矩阵的每一列，让长度为a的窗口开始滑动，找到这一列的最小值和最大致，赋给该窗口的上顶点。

③也就是说，左上角这个顶点是这个矩阵的最小值和最大值。

容易错误的点：

①对矩阵的每一列操作，是在行处理后，找到最小值或最大值基础上，在对列进行操作，找到最小值和最大值。而不是对原数组arr，找到原数据的最小值和最大值。

②我们是先对每一行求得子矩阵的最小值和最大值，在这个基础上，再求每一列的最小值和最大值。因此，每一列的最小值和最大值是我们需要的，我们不能把每一行的最小值和最大值、每一列的最小值和最大值放在一起。我们需要的是每一列的最小值和最大值，要分开存数据。

滑动窗口+单调队列代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1010;int n, m ,a , b;
int arr[N][N];
//队列中存的是整数在数组的下标
int q[N]; //数组模拟队列
int hh ,tt; //队头指针 队尾指针
int ssmax[N][N], ssmax_col[N][N];
int ssmin[N][N], ssmin_col[N][N];signed main(){cin >> n >> m >> a>> b;for(int i = 1; i <=n; i++){for(int j = 1; j <= m; j++){cin >> arr[i][j];}}//最小值-行//窗口的最左边为该窗口的最小值 for(int i = 1; i <= n; i++){//队头指针 队尾指针 初始化hh = 1, tt = 0;for(int j = 1;j <= m; j++){//保证队列数组从小到大的单调性while(hh <= tt && arr[i][j] < arr[i][q[tt]]) tt--;//将更小的数覆盖之前的位置q[++tt] = j;//保证窗口长度不超过bif(j-q[hh]+1 > b) hh ++;//当窗口长度为b时候，最小值付给最左边位置if(j>=b) ssmin[i][j-b+1] = arr[i][q[hh]];}}//要基于行的操作//最小值-列for(int j = 1; j <= m; j++){hh = 1, tt = 0;for(int i = 1; i <= n; i++){while(hh <= tt && ssmin[i][j] < ssmin[q[tt]][j]) tt--;q[++tt] = i;if(i-q[hh]+1 > a)hh++;if(i >=a)ssmin_col[i-a+1][j] = ssmin[q[hh]][j];}}//最大值-行//窗口的最左边为该窗口的最大值 for(int i = 1; i <= n; i++){//队头指针 队尾指针 初始化hh = 1, tt = 0;for(int j = 1;j <= m; j++){//保证队列数组从大到小的单调性while(hh <= tt && arr[i][j] > arr[i][q[tt]]) tt--;//将更大的数覆盖之前的位置q[++tt] = j;//保证窗口长度不超过bif(j-q[hh]+1 > b) hh ++;//当窗口长度为b时候，最大值付给最左边位置if(j>=b) ssmax[i][j-b+1] = arr[i][q[hh]];}}//基于行的操作基础//最大值-列for(int j = 1; j <= m; j++){hh = 1, tt = 0;for(int i = 1; i <= n; i++){while(hh <= tt && ssmax[i][j] > ssmax[q[tt]][j]) tt--;q[++tt] = i;if(i-q[hh]+1 > a)hh++;if(i >=a)ssmax_col[i-a+1][j] = ssmax[q[hh]][j];}}int ans = 0;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){ans += (ssmin_col[i][j] * ssmax_col[i][j]) % 998244353 ;}}cout << ans % 998244353<< endl;return 0;
}