当前位置：首页 > news >正文

hdu 2888 Check Corners

news 来源：原创 2024/5/19 5:50:20

二维RMQ

题意：给一个n*m的矩阵，下面q的询问，每个询问给出一个子矩阵的左上角和右下角的坐标，要你求出这个子矩阵里面的最大元素，然后输出，并且，这个最大元素和子矩阵的四个角上的元素比较，只要能和其中一个元素相等，就输出yes，否则输出no

一维RMQ的ST算法，是叫一段2^i长度的序列分成两个2^(i-1)的序列然后计算。二维的RMQ依然使用ST的DP思想，不过对于一个矩形，将其分成完全相等的4个部分，然后求最值，特殊情况是，当一个子矩阵的宽为1，即在宽上不能二分的时候，已经长为1，即长不能二分的时候，其实就是一个一维的RMQ，我是采用了单独处理的方法（我把它归为初始化的一部分），而对于一般情况，就是普通的DP了

查询也是一样的，和一维的查询思想相同，也是将要查询的矩阵分成4份，允许有覆盖部分的去查询

思想不难的，代码量多了而已，注意细节，另外空间比较那个，会超空间，只要数组在够用的情况下尽可能小就可以了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define N 305
#define M 11
#define INF 0x3f3f3f3f

int row,col;
int __pow[M];
int dp[N][M][N][M];
int a[N][N];

bool check(int res , int r1 , int c1 , int r2 , int c2)
{
    if(res == a[r1][c1] || res == a[r1][c2] || res == a[r2][c1] || res == a[r2][c2]) return true;
    return false;
}

inline int max(int aa ,int bb ,int cc ,int dd)
{
    int res = -INF;
    res = aa > res ? aa : res;
    res = bb > res ? bb : res;
    res = cc > res ? cc : res;
    res = dd > res ? dd : res;
    return res;
}

void ST()
{
    int KR = (int)(log((double)row) / log(2.0));
    int KC = (int)(log((double)col) / log(2.0));
    for(int i=1; i<=row; i++)            //初始化dp[i][0][j][0]
        for(int j=1; j<=col; j++)
            dp[i][0][j][0] = a[i][j];
    for(int i=1; i<=row; i++)           //初始化dp[i][0][j][p]
        for(int pc=1; pc<=KC; pc++)
            for(int j=1; j+__pow[pc]-1<=col; j++)
            {
                int kc = j + __pow[pc-1];
                int x = dp[i][0][j][pc-1] , y = dp[i][0][kc][pc-1];
                dp[i][0][j][pc] = x > y ? x : y;
            }
    for(int j=1; j<=col; j++)           //初始化dp[i][p][j][0]
        for(int pr=1; pr<=KR; pr++)
            for(int i=1; i+__pow[pr]-1<=row; i++)
            {
                int kr = i + __pow[pr-1];
                int x = dp[i][pr-1][j][0] , y = dp[kr][pr-1][j][0];
                dp[i][pr][j][0] = x > y ? x : y;
            }
    for(int pr=1; pr<=KR; pr++) 
        for(int pc=1; pc<=KC; pc++)
            for(int i=1; i+__pow[pr]-1<=row; i++)
                for(int j=1; j+__pow[pc]-1<=col; j++)
                {
                    int kr = i + __pow[pr-1];
                    int kc = j + __pow[pc-1];
                    dp[i][pr][j][pc] = max(dp[i][pr-1][j][pc-1] , dp[i][pr-1][kc][pc-1] , dp[kr][pr-1][j][pc-1] , dp[kr][pr-1][kc][pc-1]);
                }
}

int RMQ(int r1 , int c1 , int r2 , int c2)
{
    int KR = (int)(log((double)(r2-r1+1)) / log(2.0));
    int KC = (int)(log((double)(c2-c1+1)) / log(2.0));
    int kr = r2 - __pow[KR] + 1;
    int kc = c2 - __pow[KC] + 1;
    return max(dp[r1][KR][c1][KC] , dp[r1][KR][kc][KC] , dp[kr][KR][c1][KC] , dp[kr][KR][kc][KC]);
}

int main()
{
    for(int i=0; i<M; i++) __pow[i] = (1<<i);
    while(scanf("%d%d",&row,&col)!=EOF)
    {
        for(int i=1; i<=row; i++)
            for(int j=1; j<=col; j++)
                scanf("%d",&a[i][j]);
        ST();
        int q;
        scanf("%d",&q);
        while(q--)
        {
            int ok = 0,r1,c1,r2,c2;
            scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
            int res = RMQ(r1,c1,r2,c2);
            printf("%d ",res);
            if(check(res ,r1,c1,r2,c2)) printf("yes\n");
            else                        printf("no\n");
        }
    }
    return 0;
}