2020牛客暑期多校训练营（第二场）F题

2020牛客暑期多校训练营（第二场）F题

大概题意：输入三个整数m, n, k构建一个m × n的矩阵A，A[m][n]所存的数为m，n的最大公倍数，求矩阵A中所有k × k的子矩阵中的最大值的和。

解题思路：通过组长的分享了解到两次单调队列的解法，思路为先用一个一维队列找出每一行长度为k区间的最大值，在通过另一个二维的队列找出列的最大值，最后求和即为答案。

#include<iostream>
#include<math.h>
#include<algorithm>
using namespace std;
typedef long long ll;
int findtheans(int A,int B)
{
	int muli=A*B;
	while(B)
    {
        int tmp=A%B;
        A=B;
        B=tmp;
    }
    return muli/A;

}
int n, m, k;
int A[5005][5005], tar[5005], a[5005][5005];
int main()
{
    cin>>n>>m>>k;
    int i,j;
    ll ans = 0;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
        	A[i][j]=findtheans(i,j);
		}  
    }
    for(i=1;i<=n;i++)
    {
        int l=0,r=0;
        for(j=1;j<=m;j++)
        {
            while(l<r&&j-tar[l]+1>k)
                l ++;
            while(l<r&&A[i][tar[r-1]]<=A[i][j])
                r --;
            tar[r++]=j;
            a[i][j]=A[i][tar[l]];
        }
    }
    for(int j=1;j<=m;j++)
    {
        int l=0,r=0;
        for(int i=1;i<=n;i++)
        {
            while(l<r&&i-tar[l]+1>k)
			l++;
            while(l<r&&a[tar[r-1]][j]<=a[i][j])
			r--;
            tar[r++]=i;
            a[i][j]=a[tar[l]][j];
        }
    }
    for(int i=k;i<=n;i++)
    {
        for(int j=k;j<=m;j++)
        {
            ans+=a[i][j];
        }
    }
    cout <<ans;
    return 0;
}

学到：单调队列的运用，滑动窗口