链接
https://ac.nowcoder.com/acm/contest/5667/F
题意
一个 $nm$ 的矩阵，每个单元格 $A_{i,j}=lcm(i,j)$，求所有 $kk$ 的子矩阵中的最大值的和
思路
二维滑动窗口
暴力求 $A$ 为 $O(nmlogn)$，考虑 $O(nm)$ 的求法（见代码）
设 $mx[i][j]$ 为以 $(i,j)$ 为右上角的子矩阵中的最大值，这样就不会对后面的更新产生影响
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include<bits/stdc++.h>
using namespace std;
const int N=5005;
int n,m,k,a[N][N],gcd[N][N];
long long res;
deque<int> dq;
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 k=1;i*k<=n&&j*k<=m;k++)
gcd[i*k][j*k]=k,a[i*k][j*k]=i*j*k;
for(int i=1;i<=n;i++) {
dq.clear();
for(int j=1;j<=m;j++) {
if(!dq.empty()&&j-dq.front()+1>k) dq.pop_front();
while(!dq.empty()&&a[i][dq.back()]<=a[i][j]) dq.pop_back();
dq.push_back(j);
if(j-k+1>0) a[i][j-k+1]=a[i][dq.front()];
}
}
for(int j=1;j<=m;j++) {
dq.clear();
for(int i=1;i<=n;i++) {
if(!dq.empty()&&i-dq.front()+1>k) dq.pop_front();
while(!dq.empty()&&a[dq.back()][j]<=a[i][j]) dq.pop_back();
dq.push_back(i);
if(i-k+1>0) a[i-k+1][j]=a[dq.front()][j];
}
}
for(int i=1;i<=n-k+1;i++) {
for(int j=1;j<=m-k+1;j++)
res+=a[i][j];
}
printf("%lld\n",res);
return 0;
}
|