2020牛客暑期多校训练营（第二场）F-Fake Maxpooling
Cover the Tree
https://ac.nowcoder.com/acm/contest/5667/C
题目大意
给定整数n,m,k，构造一个n×m的矩阵A，其中Ai,j = lcm(i,j)，第i行j列的数是i和j的最小公倍数。 求所有k×k个子矩阵中的最大值之和。
解题思路
先用尽可能快的操作将整张表求出来，接下来用单调队列。（附上大佬详解链接https://www.cnblogs.com/RealMadrid/articles/10599588.html）
一次横排，一次竖排，记录每个区间中最大值的下标，顺便求和即可（这题要将代码讲的精细太头疼了）
用到双端队列deque，用法与queue相近，且添加了一些更舒服的操作，在头尾都可以删除或添加。（pop_back，pop_front，push_back，push_front等等）
AC代码
#include<bits/stdc++.h>
using namespace std;
int a[5010][5010],b[5010][5010],n,m,k;
long long ans; //ans用long long避免超限
deque<int> q;
int gcd(int x,int y)
{
if(y==0) return x;
return gcd(y,x%y);
}
int main()
{
int i,j,t;
scanf("%d%d%d",&n,&m,&k);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
a[i][j]=i*j/gcd(i,j);
for(i=1;i<=n;i++)
{
t=0;
while(!q.empty()) q.pop_back();
for(j=1;j<=k;j++)
{
while(q.size() && a[i][q.back()]<=a[i][j]) q.pop_back();
q.push_back(j);
}
t++,b[i][t]=a[i][q.front()];
for(j=k+1;j<=m;j++)
{
while(q.size() && a[i][q.back()]<a[i][j]) q.pop_back();
q.push_back(j);
while(q.size() && q.front()<j-k+1) q.pop_front();
t++,b[i][t]=a[i][q.front()];
}
}
for(i=1;i<=t;i++)
{
while(!q.empty()) q.pop_back();
for(j=1;j<=k;j++)
{
while(q.size() && b[q.back()][i]<=b[j][i]) q.pop_back();
q.push_back(j);
}
ans+=b[q.front()][i];
for(j=k+1;j<=n;j++)
{
while(q.size() && b[q.back()][i]<=b[j][i]) q.pop_back();
q.push_back(j);
while(q.size() && q.front()<j-k+1) q.pop_front();
ans+=b[q.front()][i];
}
}
printf("%lld\n",ans);
return 0;
}
2020牛客暑期多校训练营 文章被收录于专栏
只是题解，可参考，可学习，可点赞:)
