<题目链接>

<转载于 >>> >

题目大意:

给出一个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. 结构struct
  2. TOJ3136
  3. FragmentStatePageradapter 与 FragmentPageradapter的区别
  4. java1.8中Lambda表达式reduce聚合测试例子
  5. linux top 参数详解
  6. c++对象成员的引用---12
  7. 锋利的jQuery-1--jQuery对象和DOM对象以及相互转化
  8. 设计模式学习之工厂方法(Factory Method,创建型模式)(2)
  9. c#中怎么删除一个非空目录
  10. Chapter 3 - How to Move a sprite
  11. [转]python pickle包,cPickle包 存储
  12. lc面试准备:Remove Duplicates from Sorted List
  13. Setup Automapper in ASP.NET Core
  14. Twitter分布式自增ID算法snowflake原理解析
  15. 浅谈Kubernetes生产架构
  16. Ubuntu安装cuda
  17. js获得当前元素的样式
  18. 根据设备宽高设置View的大小
  19. Oracle EBS 用户职责人员取值
  20. 【Java】详解菜单组件

热门文章

  1. Struts2中类数据封装的方式
  2. ORA-00257 archiver error. 错误的处理方法
  3. yum -y 与yum有何区别(转载)
  4. mvc 模式和mtc 模式的区别
  5. laravel 配置设置
  6. Linux下source命令详解
  7. python selenium打开新窗口,多窗口切换
  8. python网络爬虫day1
  9. 解决OS睡眠功能中,移动鼠标就会唤醒
  10. 设置git记住用户和密码