首页 > 其他 > 详细

CF574EOpenStreetMap

时间:2019-12-13 13:42:04      阅读:84      评论:0      收藏:0      [点我收藏+]

题意:给你一个n*m的矩阵,求出所有大小为a*b的矩阵的最小值之和。

一句话题解:单调队列+单调队列

技术分享图片
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int N=3005;
int n,m,a,b;
int q[N*N];
long long h[N][N],g[N],ans,t[N][N],x,y,z;

int main()
{
    scanf("%d%d%d%d",&n,&m,&a,&b);
    scanf("%lld%lld%lld%lld",&g[0],&x,&y,&z);
    for (int i=1;i<=n*m;i++) g[i]=(g[i-1]*x+y)%z;
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) {
            h[i][j]=g[(i-1)*m+j-1];
        }
    }
    for (int i=1;i<=n;i++) {
        int head=1,tail=0;
        for (int j=1;j<=m;j++) {
            while (head<=tail&&j-q[head]>=b) head++;
            while (head<=tail&&h[i][q[tail]]>h[i][j]) --tail;
            q[++tail]=j;
            t[i][j]=h[i][q[head]];
        }
    }
    for (int j=1;j<=m;j++) {
        int head=1,tail=0;
        for (int i=1;i<=n;i++) {
            while (head<=tail&&i-q[head]>=a) head++;
            while (head<=tail&&t[q[tail]][j]>t[i][j]) --tail;
            q[++tail]=i;
            if (i>=a&&j>=b) ans+=t[q[head]][j];
        }
    }
    cout << ans << endl;
    return 0;
}
View Code

CF574EOpenStreetMap

原文:https://www.cnblogs.com/yglng/p/12034461.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!