20181030noip模拟赛T1

YY的矩阵

YY有一个大矩阵（N*M）, 矩阵的每个格子里都有一个整数权值W[i,j]（1<=i<=M,1<=j<=N）

对于这个矩阵YY会有P次询问，每次询问这个大矩阵的一个子矩阵内的最大值。

输入

第一行两个整数N和M。

接下来N行，每行M个整数

然后，一行是整数P；

接下来P行，每行4个整数r1, c1, r2, c2（分别表示子矩阵的左上角坐标和右下角坐标）

输出

共P行，每行一个整数，表示相应的最大值。

Input

4 4

4 4 10 7

2 13 9 11

5 7 8 20

13 20 8 2

1 1 4 4

1 1 3 3

1 3 3 4

1 1 1 1

Output

数据范围：

60%的数据：N×M×P<10^8

100%的数据：1 <= N, M <= 300；1 <= P <= 1,000,000；1 <= r1 <= r2 <= N, 1 <= c1 <= c2 <= M，1<=W[i][j]<=10000.

思路：

听说正解是二维rmq？？

本人懒得敲……

于是便有了一个O（n^3+p*n）的算法

首先O(N^3)预处理出dp[i][j][k]表示第i行从j到k的最大值

然后对于每组询问

O(x2-x1)的扫一遍即可

（跑满好像要300000000，然而我好像是全场跑的最快的？？？？）

代码：

#include<iostream>

#include<cstdio>

#define rii register int i

#define rij register int j

#define rik register int k

using namespace std;

int dt[][],m,n,p,dp[][][];

inline void ycl()

{

    for(rii=;i<=n;++i)

    {

        for(rij=;j<=m;++j)

        {

            dp[i][j][j]=dt[i][j];

            for(rik=j+;k<=m;++k)

            {

                if(dp[i][j][k-]>dt[i][k])

                {

                    dp[i][j][k]=dp[i][j][k-];

                }

                else

                {

                    dp[i][j][k]=dt[i][k];

                }

            }

        }

    }

}

inline int rd(){

    register int x=,f=;char ch=getchar();

    while(!isdigit(ch)) {f=ch=='-'?:;ch=getchar();}

    while(isdigit(ch))  {x=(x<<)+(x<<)+ch-'';ch=getchar();}

    return f?x:-x;

}

inline void out(int a)

{

    if(a<)

    {

          putchar('-');

          a=-a;

    }

    if(a>)

    out(a/);

    putchar(a%+'');

}

int main()

{

    freopen("yy.in","r",stdin);

    freopen("yy.out","w",stdout);

    n=rd();

    m=rd();

    for(rii=;i<=n;++i)

    {

        for(rij=;j<=m;++j)

        {

            dt[i][j]=rd();

        }

    }

    ycl();

    scanf("%d",&p);

    for(rii=;i<=p;++i)

    {

        int x1=rd(),y1=rd(),x2=rd(),y2=rd();

        int ans=;

        for(rij=x1;j<=x2;++j)

        {

            if(ans<dp[j][y1][y2])

            {

                ans=dp[j][y1][y2];

            }

        }

//        printf("%d\n",ans);

        out(ans);

        putchar();

    }

    return ;

}

巴特西

20181030noip模拟赛T1

YY的矩阵

思路：

代码：

最新文章

热门文章