题面链接
F-Fake Maxpooling
题解
思路
直接求矩阵复杂度为O(nmlog(n))超时，用筛法求lcm时间复杂度为O(nm)（矩阵每个值只计算一次），再用二维单调队列维护最大值
坑点是卡空间，只能开两个N*N的数组，有点毒瘤
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define ll long long
using namespace std;
const int N=5005;
int q[N],a[N][N],b[N][N];
int front,back;int main()
{int n,m,k;cin>>n>>m>>k;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(!b[i][j]){for(int k=1;k*i<=n&&k*j<=m;k++){b[k*i][k*j]=k,a[k*i][k*j]=k*i*j;}}}}for(int i=1;i<=n;i++)//找每行连续k列的最大值 {front=1,back=1;q[1]=0;for(int j=1;j<=m;j++){while(j-q[front]+1>k&&front<=back) front++;while(a[i][j]>=a[i][q[back]]&&front<=back) back--;q[++back]=j;b[i][j]=a[i][q[front]];}} for(int j=1;j<=m;j++)//找每列连续k行的最大值 {front=1,back=1;q[1]=0;for(int i=1;i<=n;i++){while(i-q[front]+1>k&&front<=back) front++;while(b[q[back]][j]<=b[i][j]&&front<=back) back--;q[++back]=i;a[i][j]=b[q[front]][j];}} ll sum=0;for(int i=k;i<=n;i++)for(int j=k;j<=m;j++) sum+=a[i][j];cout<<sum<<endl;system("pause");return 0;
}