【题解】2020牛客暑假多校训练营(第二场)F-Fake Maxpooling
程序员文章站
2022-06-18 23:38:13
题面链接F-Fake Maxpooling题解思路直接求矩阵复杂度为O(nmlog(n))超时,用筛法求lcm时间复杂度为O(nm)(矩阵每个值只计算一次),再用二维单调队列维护最大值坑点是卡空间,只能开两个N*N的数组,有点毒瘤代码#include #include #include #include #define ll long longusing nam...
题面链接
题解
思路
直接求矩阵复杂度为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;
}
本文地址:https://blog.csdn.net/qq_43200004/article/details/107346918
上一篇: Maven 配置Pom.xml 解析
下一篇: 神奇的选择器 :focus-within
推荐阅读
-
2020暑假牛客多校训练营第二场
-
2020牛客暑期多校训练营(第二场)Cover the Tree 题解(dfs序)
-
2020牛客暑期多校第二场题解
-
【题解】2020牛客暑假多校训练营(第二场)F-Fake Maxpooling
-
2020牛客暑假多校训练营(第二场)补题B,C
-
2020暑假牛客多校训练营第二场
-
2020牛客暑期多校训练营(第二场)Cover the Tree 题解(dfs序)
-
2020牛客暑假多校第二场 B Boundary (数学/map+三点共圆圆心公式)
-
2020牛客暑期多校训练营(第二场)Fake Maxpooling
-
2020牛客暑期多校训练营(第二场)A、B、C、D、F、G、J题解及补题