<题目链接>

<转载于 >>> >

题目大意:

给出一个N*M的矩阵,并且给出该矩阵上每个点对应的值,再进行Q次询问,每次询问给出代询问子矩阵的左上顶点和右下顶点,问该子矩阵的最大值是多少,并且判断该最值是否在该子矩阵的四个顶角上。

解题分析:

很明显求二维区间内的最值,需要用到二维RMQ,其中dp[i][j][k][l]表示左上角为(i,j),右下角为(i + 2 ^ k - 1, j + 2 ^ l - 1)这个矩形内的最值。注意这个四维数组不要开得太大,否则容易MLE。

 #include <cstdio>
#include <cstring>
#include <algorithm> using namespace std;
const int maxn = ; int n, m, q, val[maxn][maxn], dp[maxn][maxn][][]; //dp[i][j][k][l]表示左上角为(i,j),右下角为(i + 2 ^ k - 1, j + 2 ^ l - 1)这个矩形内的最值 void rmq_init(int n, int m){
for (int i = ; i <= n; i++) {
for (int j = ; j <= m; j++)
dp[i][j][][] = val[i][j];
} for (int x = ; (<<x) <= n; x++)
for (int y = ; (<<y) <= m; y++)
if (x + y){
for (int i = ; i + (<<x) - <= n; i++)
for (int j = ; j + (<<y) - <= m; j++) {
if (x) //在y轴方向比较
dp[i][j][x][y] = max(dp[i][j][x-][y], dp[i+(<<(x-))][j][x-][y]);
else //在x轴方向比较
dp[i][j][x][y] = max(dp[i][j][x][y-], dp[i][j+(<<(y-))][x][y-]);
}
}
} int rmq_query(int x1, int y1, int x2, int y2) {
int x = , y = ;
while ((<<(x+)) <= x2 - x1 + ) x++;
while ((<<(y+)) <= y2 - y1 + ) y++;
x2 = x2 - (<<x) + ;
y2 = y2 - (<<y) + ; return max( max(dp[x1][y1][x][y], dp[x2][y1][x][y]), max(dp[x1][y2][x][y], dp[x2][y2][x][y]));
} int main () {
while (scanf("%d%d", &n, &m) == ) {
for (int i = ; i <= n; i++) {
for (int j = ; j <= m; j++)
scanf("%d", &val[i][j]);
}
rmq_init(n, m); scanf("%d", &q);
int x1, y1, x2, y2;
while (q--) {
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
int ans = rmq_query(x1, y1, x2, y2);
bool flag = false;
if (ans == val[x1][y1] || ans == val[x1][y2] || ans == val[x2][y1] || ans == val[x2][y2]) //检查最值是否在子矩阵的四个顶角上
flag = true;
printf("%d %s\n", ans, flag ? "yes" : "no");
}
}
return ;
}

2018-10-20

最新文章

  1. 【POJ 3261】Milk Patterns 可重叠的k次最长重复子串
  2. 9月5日网页基础知识 通用标签、属性(body属性、路径、格式控制) 通用标签(有序列表、无序列表、常用标签)(补)
  3. irc操作小记
  4. C语言面向对象风格编程
  5. 移动平台WEB前端开发技巧汇总
  6. android eclipse——error: device not found解决办法
  7. After a rest, go on
  8. Swift中使用typealias定义一个闭包closure
  9. 学习H5一周随笔
  10. spring8——AOP之Bean的自动代理生成器
  11. [UWP]为什么ContentControl的ControlTemplate里放两个ContentPresenter会出问题(绕口)
  12. camera测试之MTF
  13. DAY05、基本数据类型与内置方法
  14. boost常用库案例
  15. 【读书笔记】iOS-强类型与弱类型
  16. LyX快捷键管理
  17. 解决双系统(Window10+Ubuntu16.10)下ubuntu安装git时提示软件包git没有可安装候选问题
  18. MFC单文档视图拆分窗口和相关链接
  19. 【Html】Clipboard.js 实现点击复制,剪切板操作
  20. 用OpenGL进行曲线、曲面的绘制

热门文章

  1. Linux永久修改IP地址
  2. Confluence 6 workbox 的位置
  3. XSS-HTML&amp;javaSkcript&amp;CSS&amp;jQuery&amp;ajax-CSS
  4. 饮冰三年-人工智能-linux-09 服务
  5. MySQL 存储过程与事物
  6. C#异常断电后重新启动项目出现配置未初始化错误
  7. lua和java防注入
  8. 反射PropertyInfo的简单使用
  9. babelrc
  10. 【译】理解JavaScript闭包——新手指南