AcWing 4964.子矩阵

AcWing 4964.子矩阵

首先就是运用了暴力的思路,能够过个70%的数据,剩下的直接时间超时了,没办法优化了。

讲一下暴力的思路:

其实就是模拟而已,也就是看作想要找的矩阵为一个小窗口,然后不断移动的事而已。

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<cmath> 
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<sstream>
#include<map>
#include<limits.h>
#include<set>
#define MAX 1005
#define int long long
#define _for(i,a,b) for(int i=a;i<(b);i++)
#define ALL(x) x.begin(),x.end()
using namespace std;
vector<int>cunchu;
int arr[MAX][MAX];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n, m;
    int a, b;
    cin >> n >> m >> a >> b;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)
            cin >> arr[i][j];
    }
    int sum = 0;//计算结果
    int left1 = 1;//这里代表的是对于上界的限制
    int left2 = a;//代表对于下界的限制
    int right1 = 1;//代表对于左边的限制
    int right2 = b;//代表对于右边的限制
    while (left2 <= n) {
        cunchu.clear();
        if (right2 > m)
        {
            right1 = 1;
            right2 = b;
            left2++;
            left1++;
            continue;
        }
        for (int i = left1; i <= left2; i++) {
            for (int j = right1; j <= right2; j++) {
                cunchu.push_back(arr[i][j]);
            }
        }
        sort(cunchu.begin(), cunchu.end());
        sum += (cunchu.front() * cunchu.back()) % 998244353;
        right1++;
        right2++;
    }
    cout << sum;
    return 0;
}

接下来就是优化版本:

这里用的是滑动窗口问题的解决方法,也就是所谓数据结构中的单调队列,这也是需要一些数据结构基础的才能接受的知识点。

思路:单调队列讲究的就是一个单调,我们可以先套用单调队列的模板,可以参考一下y总的模板,作者的模板也是跟y总学的,建议首先理解,然后自己敲出来。

我们想,在给定的大矩阵当中,我们从中随便选一块小矩阵的大小,我们要求它的最大值最小值,如果要是暴力的话,复杂度肯定是n**2,而单调队列可以降到n,在求最值的时候我们尝试用单调队列进行求出。但是,我们以往用的单调队列都是线性的,也就是一维的,但不是二维的,怎么办?这样我们可以换个思路,可以从前面写的那个二维双指针可以知道,我们可以把二维问题变成一维的,也就是说,首先固定两个相对的边界。

假设我们这里就首先固定了左右边界,这个时候列数是不是就是小矩阵的长呢?可以自己画图看一下。这个时候,如果说我们先求出来每一行的最大值,再来求每一列的最小值,这两个过程是不是都是线性的呢?是的,这个时候我们的单调队列才派上用场。

对于每一行的最值求完之后,我们还需要对于这些最值中再求最值,这样才能是小矩阵的最值,所以又需要用一次单调队列,这样虽然麻烦,但是效率却是很高的。OK,核心思路就到这里

上代码:

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<cmath> 
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<sstream>
#include<map>
#include<limits.h>
#include<set>
#define MAX 1005
#define int long long
#define _for(i,a,b) for(int i=a;i<(b);i++)
#define ALL(x) x.begin(),x.end()
using namespace std;
vector<int>cunchu;
int arr[MAX][MAX];//存储的大矩阵
int rmax[MAX][MAX], rmin[MAX][MAX];//对于第i-1行的每一个长度为b的窗口求最大/小值
int q[MAX];//队列
int one[MAX], two[MAX], three[MAX];//用来存储列的最值的
void get_max(int a[], int b[], int total, int qujian) {
    int front = 0;
    int rear = -1;
    for (int i = 0; i < total; i++) {
        if (front <= rear && q[front] + qujian <= i)front++;//当前队头滑出窗口
        while (front <= rear && a[q[rear]] <= a[i])rear--;//队尾元素比进来的元素小,那么我们就开始更新
        q[++rear] = i;
        if (i >= qujian - 1)//滑动窗口已经完全在数组里面进行滑动了,就开始统计每个窗口的最大值。
            b[i] = a[q[front]];
    }
}
void get_min(int a[], int b[], int total, int qujian) {
    int front = 0;
    int rear = -1;
    for (int i = 0; i < total; i++) {
        if (front <= rear && q[front] <= i - qujian)front++;
        while (front <= rear && a[q[rear]] >= a[i])rear--;
        q[++rear] = i;
        if (i >= qujian - 1)
            b[i] = a[q[front]];
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n, m;
    int a, b;
    cin >> n >> m >> a >> b;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            cin >> arr[i][j];
    }
    for (int i = 0; i < n; i++) {
        get_max(arr[i], rmax[i], m, b);//对于每一行的每一个长度为b的窗口求最大值
        get_min(arr[i], rmin[i], m, b);//对于每一行的每一个长度为b的窗口求最小值
    }
    int count = 0;//用来统计积的和
    //这里的外循环是对于列的遍历,内循环才是对于行的遍历
    for (int i = b-1; i < m; i++) {//为什么初值是b-1呢?这个时候窗口的队头才是i=0,初值不是b-1的话,窗口是不满的
        for (int j = 0; j < n; j++) one[j] = rmax[j][i];//这个时候我们对于每一行的当前窗口的最大值进行存储
        get_max(one, two, n, a);//这里是对于这些行的最大值再进行求最大值,也就是小矩阵的最大值了
        for (int j = 0; j < n; j++)one[j] = rmin[j][i];//同理,求最小值
        get_min(one, three, n, a);

        for (int j = a - 1; j < n; j++) {//为什么这里用a-1当初值呢?其实也是窗口的问题,如果纵向看,窗口的宽就是a了,如果初值不是a-1,窗口也是不满的
            count = (count + two[j] * three[j]) % 998244353;//这样就是对于所有小矩阵的最值进行相乘然后相加取模了
        }
    }
    cout << count;
    return 0;
}

转载请说明出处内容投诉
CSS教程_站长资源网 » AcWing 4964.子矩阵

发表评论

欢迎 访客 发表评论

一个令你着迷的主题!

查看演示 官网购买