原题传送门

 

  

 

解题思路：打表求出lcm矩阵,注意矩阵最好是开成int类型的并且范围不要太大（亲身经历过内存超限的烦恼），接着就是横着把每一行用单调队列求出连续k个数的最大值，并把这些求出的最大值放入新的矩阵中，在新的矩阵中竖着再次以单调队列求出连续k个数的最大值，并累加入答案，注意记录答案要开long long。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[5010][5010];
int gcd(int a,int b)
{
    if(b==0) return a;
    else return gcd(b,a%b);
}
int row[5010][5010];///行滑动得最大值
deque<int> q;
int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    if(n>m)
    {
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=i;j++)
            {
                int tmp=(i*j)/gcd(i,j);
                a[i][j]=tmp;a[j][i]=tmp;
            }
        }
        for(int i=m+1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                a[i][j]=(i*j)/gcd(i,j);
            }
        }
    }
    else{
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=i;j++)
            {
                int tmp=(i*j)/gcd(i,j);
                a[i][j]=tmp;a[j][i]=tmp;
            }
        }
        for(int i=n+1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                a[j][i]=(i*j)/gcd(i,j);
            }
        }
    }
    int s=0;
    for(int i=1;i<=n;i++)
    {
        q=deque<int>();
        s=0;
        for(int j=1;j<=m;j++)
        {
            while(q.size()&&j-q.front()>=k) q.pop_front();
            while(q.size()&&a[i][q.back()]<=a[i][j]) q.pop_back();
            q.push_back(j);
            if(j>=k)
            {
                //cout<<a[i][q.front()]<<" ";
                row[i][++s]=a[i][q.front()];
            }
        }
        //puts("");
    }
    ll ans=0;
    for(int i=1;i<=s;i++)
    {
        q=deque<int>();
        for(int j=1;j<=n;j++)
        {
            while(q.size()&&j-q.front()>=k) q.pop_front();
            while(q.size()&&row[q.back()][i]<=row[j][i]) q.pop_back();
            q.push_back(j);
            if(j>=k)
            {
                //cout<<row[q.front()][i]<<" ";
                ans+=1ll*row[q.front()][i];
            }
        }
    }
   // puts("");
    printf("%lld",ans);
    return 0;
}

2020-07-13

其他的就没了，一次次的摸索导致WA的次数稍多，不过无妨，也算是摸索出来了，hh.

 

版权声明：本文为Mrzmy原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/Mrzmy/p/13296515.html