2020牛客暑期多校训练营(第二场)Fake Maxpooling
程序员文章站
2022-04-02 18:51:02
...
**
Fake Maxpooling
**
题目描述:
给定大小为n×m的矩阵和整数k,其中A {i,j} = lcm(i,j),是i和j的最小公倍数。 您应该找到所有大小为k×k的子矩阵中的最大值之和
输入:
输入只有一行:三个整数n,m,k(1≤n,m≤5000,1≤k≤min{n,m})
输出:
一个整数ans,为所有大小为k×k的子矩阵中的最大值之和
样例输入:
3 4 2
样例输出:
38
思路:单调队列+滑动窗口。
#include<cstdio>
#include<deque>
using namespace std;
const int MAXN=5005;
int a[MAXN][MAXN],gcd[MAXN][MAXN];
long long ans;
deque<int> q;
int n,m,k;
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(!gcd[i][j])
for(int z=1;z*i<=n&&z*j<=m;z++)
{
gcd[z*i][z*j]=z;
a[z*i][z*j]=i*j*z;
}//利用类似于素数筛的方法建图,时间复杂度O(mn)
for(int i=1;i<=n;i++)
{
while(!q.empty()) q.pop_back();
for(int j=1;j<k;j++)
{
while(q.size()&&a[i][q.front()]<a[i][j]) q.pop_back();
q.push_back(j);
}
for(int j=k;j<=m;j++)
{
while(q.size()&&q.front()<j-k+1) q.pop_front();
while(q.size()&&a[i][q.front()]<a[i][j]) q.pop_back();
q.push_back(j);
a[i][j]=a[i][q.front()];
}
}
for(int i=k;i<=m;i++)
{
while(!q.empty()) q.pop_back();
for(int j=1;j<k;j++)
{
while(q.size()&&a[q.front()][i]<a[j][i]) q.pop_back();
q.push_back(j);
}
for(int j=k;j<=n;j++)
{
while(q.size()&&q.front()<j-k+1) q.pop_front();
while(q.size()&&a[q.front()][i]<a[j][i]) q.pop_back();
q.push_back(j);
ans+=a[q.front()][i];
}
}
printf("%lld\n",ans);
}
上一篇: C++判断四个点能否构成正方形
推荐阅读
-
2019牛客暑期多校训练营(第二场)H Second Large Rectangle
-
2020牛客暑期多校训练营(第四场)——Basic Gcd Problem
-
2020牛客暑期多校训练营(第五场)
-
2020牛客暑期多校训练营(第九场) The Flee Plan of Groundhog
-
2020牛客暑期多校训练营Groundhog and Apple Tree(树形dp,贪心)
-
2020暑期牛客多校训练营第九场(K)The Flee Plan of Groundhog(lca,树形dp)
-
2020牛客暑期多校训练营(第二场)Cover the Tree
-
2020牛客暑期多校训练营(第一场)H-Minimum-cost Flow
-
2020牛客暑期多校 第一场 F Infinite String Comparision(字符串)
-
Harmony Pairs 2020牛客暑期多校训练营(第六场)