题意：
一个n * m的矩阵，第i行第j列的值是lcm（i，j），然后给定一个 k * k的子矩阵（k<=min(n,m)），然后求出大矩阵中每个子矩阵的最大值的和
看样例：
3 4 2
38
给的矩阵是：
1 2 3 4
2 2 6 4
3 6 3 12
所有2 * 2的子矩阵的最大值分别是 ：
2,6，6,6，6,12，总和是38
题解：
暴力求法是O（n m log n），先考虑O（n m）的做法
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*i*k;
}
}
之后再用单调队列
曾经做过一个叫滑动窗口的题，其实和这个是一个类型，那个是一维的，本题这个是二维的
滑动窗口的题解（含题目链接）
分别求出每行和每列的k个长度区间的最大值
tail表示尾，head表示头，不断得到区间内的最大值，并存进b中，最终覆盖给a
其实就是把二维的拆分成行和列的一维，然后分别进行和滑动窗口那个题一样的操作
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e3+5;
int a[maxn][maxn];
int b[maxn];
int qu[maxn];
int n,m,k;
int gcd(int a,int b)
{
if(b==0)return a;
else return gcd(b,a%b);
}
int lcm(int a,int b)
{
return a*b/gcd(a,b);
}
void getr(int j)//固定列
{
memset(qu,0,sizeof(qu));
int head=0;
int tail=1;
for(int i=1;i<=n;i++)
{
while(head<=tail&&qu[head]+k<=i)head++;
while(head<=tail&&a[i][j]>a[qu[tail]][j])tail--;
qu[++tail]=i;
if(i>=k)
b[i-k+1]=a[qu[head]][j];
}
for(int i=1;i<=n-k+1;i++)
a[i][j]=b[i];
}
void getl(int i)//固定行
{
memset(qu,0,sizeof(qu));
int head=0;
int tail=1;
for(int j=1;j<=m;j++)
{
while(head<=tail&&qu[head]+k<=j)head++;
while(head<=tail&&a[i][j]>a[i][qu[tail]])tail--;
qu[++tail]=j;
if(j>=k)
b[j-k+1]=a[i][qu[head]];
}
for(int j=1;j<=m-k+1;j++)
a[i][j]=b[j];
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
a[i][j]=lcm(i,j);
}
for(int i=1;i<=m;i++)
getr(i);
for(int i=1;i<=n;i++)
getl(i);
long long sum=0;
for(int i=1;i<=n-k+1;i++)
{
for(int j=1;j<=m-k+1;j++)
{
sum+=a[i][j];
}
}
printf("%lld\n",sum);
}
京公网安备 11010502036488号