二维RMQ hdu 2888

时间:2022-08-30 14:44:11

题目:点这里

题意:给出一个n*m的矩阵,然后又Q个询问:每个询问有x1,y1,x2,y2,x1,y1为子矩阵的左上角坐标,x2,y2为右上角的坐标。求此子矩阵中元素最大值,判断最大值是否在子矩阵四个角上,在就输出yes,否则输出no。

分析:二维RMQ直接上代码。

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
const int max_=;
int dp[max_][max_][][];//RMQ的递推数组。1,3维是行,2 4维是列。
int a[max_][max_];
void RMQ_init(int n,int m)
{
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)//初始化
{
dp[i][j][][]=a[i][j];
}
for(int i=;(<<i)<=n;i++)
for(int j=;(<<j)<=m;j++)
if(i||j)//i,j不都为0。
{
for(int ii=;ii+(<<i)-<=n;ii++)
for(int jj=;jj+(<<j)-<=m;jj++)
{
if(i)//对行递推。
{
int k=<<(i-);
dp[ii][jj][i][j]=max(dp[ii][jj][i-][j],dp[ii+k][jj][i-][j]);
}
else
{
int k=<<(j-);
dp[ii][jj][i][j]=max(dp[ii][jj][i][j-],dp[ii][jj+k][i][j-]);
}
}
}
}
int RMQ_Q(int x1,int y1,int x2,int y2)//查询
{
int k1=;
while((<<(k1+))<=x2-x1+)k1++;
int k2=;
while((<<(k2+))<=y2-y1+)k2++;
x2=x2-(<<k1)+;
y2=y2-(<<k2)+;
return max(max(dp[x1][y1][k1][k2],dp[x1][y2][k1][k2]),max(dp[x2][y1][k1][k2],dp[x2][y2][k1][k2]));
}
int main()
{
int n,m;
while(~scanf("%d %d",&n,&m))
{
if(!n&&!m)
break;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
scanf("%d",&a[i][j]);
}
RMQ_init(n,m);
int k;
scanf("%d",&k);
while(k--)
{
int x1,y1,x2,y2;
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
int temp=RMQ_Q(x1,y1,x2,y2);
printf("%d ",temp);
if(temp==a[x1][y1]||temp==a[x1][y2]||temp==a[x2][y1]||temp==a[x2][y2])
printf("yes\n");
else
printf("no\n");
}
}
}

二维RMQ hdu 2888的更多相关文章

  1. HDU 2888:Check Corners(二维RMQ)

    http://acm.hdu.edu.cn/showproblem.php?pid=2888 题意:给出一个n*m的矩阵,还有q个询问,对于每个询问有一对(x1,y1)和(x2,y2),求这个子矩阵中 ...

  2. hdu 2888 二维RMQ模板题

    Check Corners Time Limit: 2000/10000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) T ...

  3. HDU 2888 Check Corners &lpar;模板题&rpar;【二维RMQ】

    <题目链接> <转载于 >>> > 题目大意: 给出一个N*M的矩阵,并且给出该矩阵上每个点对应的值,再进行Q次询问,每次询问给出代询问子矩阵的左上顶点和右下 ...

  4. hdu 2888 二维RMQ

    Check Corners Time Limit: 2000/10000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)To ...

  5. hduacm 2888 ----二维rmq

    http://acm.hdu.edu.cn/showproblem.php?pid=2888 模板题  直接用二维rmq 读入数据时比较坑爹  cin 会超时 #include <cstdio& ...

  6. 【HDOJ 2888】Check Corners(裸二维RMQ)

    Problem Description Paul draw a big m*n matrix A last month, whose entries Ai,j are all integer numb ...

  7. hdu2888 二维RMQ

    Check Corners Time Limit: 2000/10000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) T ...

  8. HDU2888 Check Corners(二维RMQ)

    有一个矩阵,每次查询一个子矩阵,判断这个子矩阵的最大值是不是在这个子矩阵的四个角上 裸的二维RMQ #pragma comment(linker, "/STACK:1677721600&qu ...

  9. POJ 2019 Cornfields &lbrack;二维RMQ&rsqb;

    题目传送门 Cornfields Time Limit: 1000MS   Memory Limit: 30000K Total Submissions: 7963   Accepted: 3822 ...

随机推荐

  1. js和jquery实现简单的选项卡

    选项卡切换在做网页的时候经常会用到,以往都是用JQ来实现,代码简单易懂,今天用原生的js实现了一下,二者还是有很大不同的,可以对比一下代码来研究一下. <!DOCTYPE html> &l ...

  2. Java正则表达式入门——转自RUNOOB&period;COM

    Java 正则表达式 正则表达式定义了字符串的模式. 正则表达式可以用来搜索.编辑或处理文本. 正则表达式并不仅限于某一种语言,但是在每种语言中有细微的差别. Java正则表达式和Perl的是最为相似 ...

  3. libevent 安装异常

    有homebrew的可以使用 1 brew install memcached 这个命令来安装没有homebrew的可以直接手动安装1.去官网http://memcached.org/下载最新的包,然 ...

  4. Batman&plus;joker乱谈

      偶然一天内两次看到关于希斯·莱杰的文章(上面这个joker),貌似很多地方看到过这个,但是为什么他这么出名.知乎上的一篇文章 http://daily.zhihu.com/story/434137 ...

  5. Http读书笔记1-5章

    第一章 内容提要 这一章主要介绍了什么是http以及http是干嘛的,以及与之有关的相关概念,当然了这些概念都是概览式的介绍一些.所以我将采用问答式的方式描述这一章! Q:http是干嘛的? A:ht ...

  6. React-Native&colon; bios打开VT-x选项

    问题: 我在Android Studio新建一个虚拟机的时候出现如图错误: 解决方案:重启电脑,开机的时候不停的按f12(不同的主机不一样),进入bios,然后打开Virtualization Tec ...

  7. centos下升级git版本的操作记录

    在使用git pull.git push.git clone的时候,或者在使用jenkins发版的时候,可能会报类似如下的错误: error: The requested URL returned e ...

  8. 阿里云服务器安装SQLServer本地无法远程访问

    新买的阿里云服务器,安装上sqlserver2012,本机连接测试没有问题,但是回到本地,使用ip远程连接报错. 尝试了网上各种办法,都是失败.最后找到原因,原来在阿里云的控制台上有设置: 首先进入安 ...

  9. 【挑战赛16A】【取石子】【组合数学】

    链接:https://www.nowcoder.com/acm/contest/113/A 来源:牛客网 取石子时间限制:C/C++ 1秒,其他语言2秒空间限制:C/C++ 262144K,其他语言5 ...

  10. D3&period;js的基础部分之选择集的处理 enter和exit的处理方法 &lpar;v3版本&rpar;

    上一节给大家讲述额绑定数据的原理.当数组的长度与元素的数量不一致时,有enter部分和exit部分,前者表示存在多余的数据,后者表示存在多余的元素.本节将给大家介绍如何处理这些多余的东西,最后会给大家 ...