2020牛客暑期多校训练营（第二场） Fake Maxpooling
题目大意：
给你一个 (n*m) 的矩阵，(a[i][j]=lcm(i,j)) 问所有大小是 (k*k) 的子矩阵的最大值之和。
题解：
这个题目很简单，只是有点卡时间和空间。
(n*m*log(max(n,m))) 这个时间虽然容易 $TLE $ ，但是还是可以卡过去的，写一下题解是为了记录一种 (O(n*m)) 复杂度来计算 (GCD(i,j)) (1<=i<=5000) (1<=j<=5000) 的方法
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
if (!Gcd[i][j])
for (int k = 1; k * i <= n && k * j <= m; k ++)
Gcd[k * i][k * j] = k, A[k * i][k * j] = i * j * k
之后就是两个单调队列。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#include <iostream>
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
using namespace std;
const int maxn = 5e3+2;
typedef long long ll;
int cew_max[maxn][maxn];
int unit_max[maxn][maxn];
int queue_max[maxn];
void init(int n,int m){
//用 O(n*m) 求出 Gcd(i,j)的值
//用 O(n*m) 求出 lcm(i,j)的值
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
if (!unit_max[i][j])
for (int k = 1; k * i <= n && k * j <= m; k ++)
unit_max[k * i][k * j] = i*j*k;
}
int main() {
int n, m, b;
scanf("%d%d%d", &n, &m, &b);
init(n,m);
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++){
// printf("%3d ",unit_max[i][j]);
// }
// printf("
");
// }
for(int i=1;i<=m;i++){
int f1=1,t1=1;
int l=1,r=2;
queue_max[1]=i;
cew_max[l][i]=max(cew_max[l][i],unit_max[l][i]);
while(r<=n){
if(queue_max[f1]<l) f1++;
if(r-l+1<=b){
while(t1>=f1&& unit_max[r][i]>unit_max[queue_max[t1]][i]) t1--;
queue_max[++t1]=r;
r++;
cew_max[l][i]=max(cew_max[l][i],unit_max[queue_max[f1]][i]);
}
else {
// printf("cew[%d][%d]=%d
",l,i,cew_max[l][i]);
l++;
}
}
// printf("cew[%d][%d]=%d
",n-b+1,i,cew_max[n-b+1][i]);
}
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++){
// printf("cew_max[%d][%d]=%d
",i,j,cew_max[i][j]);
// }
// }
for(int i=1;i<=n;i++){
int f1 = 1,t1 = 1;
int l = 1,r = 2;
queue_max[1]=i;
unit_max[i][l]=max(unit_max[i][l],cew_max[i][l]);
while(r<=m){
if(queue_max[f1]<l) f1++;
if(r-l+1<=b){
while(t1>=f1&&cew_max[i][r]>cew_max[i][queue_max[t1]]) t1--;
queue_max[++t1] = r;
r++;
// printf("l=%d r=%d i=%d
",l,r,i);
unit_max[i][l]=max(unit_max[i][l],cew_max[i][queue_max[f1]]);
// printf("unite[%d][%d]=%d cew[%d][%d]=%d
",i,l,unit_max[i][l],i,queue_max[f1],cew_max[i][queue_max[f1]]);
}
else l++;
}
}
ll ans=0;
for(int i=1;i+b-1<=n;i++){
for(int j=1;j+b-1<=m;j++){
// printf("unit_max[%d][%d]=%d
",i,j,unit_max[i][j]);
ans+=unit_max[i][j];
}
}
printf("%lld
",ans);
return 0;
}