首页 > 其他分享 >POJ 2019 Cornfields(简单二维RMQ)

POJ 2019 Cornfields(简单二维RMQ)

时间:2023-06-12 14:33:27浏览次数:43  
标签:RMQ int Sample MAXN Cornfields 2019 include Input


思路:二维RMQ



#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=255;
int val[MAXN][MAXN];
int dmin[MAXN][MAXN][8][8];
int dmax[MAXN][MAXN][8][8];
void initRMQ(int n,int m)
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            dmin[i][j][0][0]=dmax[i][j][0][0]=val[i][j];
    for(int ii=0;(1<<ii)<=n;ii++)
        for(int jj=0;(1<<jj)<=m;jj++)
        if(ii+jj)
            for(int i=1;i+(1<<ii)-1<=n;i++)
                for(int j=1;j+(1<<jj)-1<=m;j++)
                if(ii)
                {
                    dmin[i][j][ii][jj] = min(dmin[i][j][ii-1][jj] ,dmin[i+(1<<(ii-1))][j][ii-1][jj]);
                    dmax[i][j][ii][jj] = max(dmax[i][j][ii-1][jj] ,dmax[i+(1<<(ii-1))][j][ii-1][jj]);
                }
                else
                {
                    dmin[i][j][ii][jj] = min(dmin[i][j][ii][jj-1] , dmin[i][j+(1<<(jj-1))][ii][jj-1]);
                    dmax[i][j][ii][jj] = max(dmax[i][j][ii][jj-1] , dmax[i][j+(1<<(jj-1))][ii][jj-1]);
                }
}
int getMax(int x1,int y1,int x2,int y2)
{
    int k1=0;
    while((1<<(k1+1))<=x2-x1+1)k1++;
    int k2=0;
    while((1<<(k2+1))<=y2-y1+1)k2++;
    x2 = x2 - (1<<k1)+1;
    y2 = y2 - (1<<k2)+1;
    return max(max(dmax[x1][y1][k1][k2],dmax[x1][y2][k1][k2]) ,max(dmax[x2][y1][k1][k2],dmax[x2][y2][k1][k2]) );
}
int getMin(int x1,int y1,int x2,int y2)
{
    int k1=0;
    while((1<<(k1+1))<=x2-x1+1)k1++;
    int k2=0;
    while((1<<(k2+1))<=y2-y1+1)k2++;
    x2 = x2 - (1<<k1)+1;
    y2 = y2 - (1<<k2)+1;
    return min( min(dmin[x1][y1][k1][k2],dmin[x1][y2][k1][k2]) ,min(dmin[x2][y1][k1][k2],dmin[x2][y2][k1][k2]) );
}

int main()
{
    int n,b,k;
    while(scanf("%d%d%d",&n,&b,&k)==3&&n&&b&&k)
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                scanf("%d",&val[i][j]);
        initRMQ(n,n);
        while(k--)
        {
            int x1,y1;
            scanf("%d%d",&x1,&y1);
            int ans=getMax(x1,y1,x1+b-1,y1+b-1)-getMin(x1,y1,x1+b-1,y1+b-1);
            printf("%d\n",ans);
        }
    }
    return 0;
}




Description



给出一个N*N (N<=250)的方阵,以及K(<=100000)个询问。每次询问如下:以(Xi,Yi)为左上角,边长为B的子方阵中,最大值和最小值的差是多少?

注意对于所有的询问,B都是一个定值。



Input



第一行N,B(<=N),K。含义如上。

接下来N行N列的一个矩阵,每个数<=250。

 

接下来K行表示询问,每行两个数Xi, Yi 表示询问的方阵的左上角。



Output



一行一个正整数,含义如上。



Sample Input



5 3 1 5 1 2 6 3 1 3 5 2 7 7 2 4 6 1 9 9 8 6 5 0 6 9 3 9 1 2



Sample Output



5






标签:RMQ,int,Sample,MAXN,Cornfields,2019,include,Input
From: https://blog.51cto.com/u_16156555/6462554

相关文章

  • X-NUCA'2019部分题目WP
    0x00前言题目质量好高,题目好评0x01Ezphp题目描述ezphpphpforbeginner.hint:noracecondition题目解答题目环境:apache+php题目源码:<?php$files=scandir('./');foreach($filesas$file){if(is_file($file)){if($file!=="index.ph......
  • 洛谷P5322 [BJOI2019] 排兵布阵
    题目大意有s名对手,n座城堡,你有m名士兵如果一名玩家向第\(i\)座城堡派遣的士兵数严格大于对手派遣士兵数的两倍,那么这名玩家就占领了这座城堡,获得\(i\)分。求最大得分数据范围对于\(10\%\)的数据:\(s=1,n\le3,m\le10\)对于\(20\%\)的数据:\(s=1,n\le10,m\le1......
  • CCSP2019T2_纸牌计数 | 2019苏州CCSP大学生计算机系统与程序设计竞赛
    题目描述偶然在CSDN看到有人写了CCSP2019T2_纸牌计数的题解,突然想起来是一个不错的计数、dp题。以前的U盘找不到了,记得当时存了一步步偏分到AC代码,可惜。又想起来18年打铁了。。。此人的题解的链接CCSP201902纸牌计数——解题报告当年一共有5题,取自:https://www.sohu.com/a/34......
  • P5518 [MtOI2019]幽灵乐团 / 莫比乌斯反演基础练习题
    简要题意计算\[\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C}\left(\frac{\text{lcm}(i,j)}{\gcd(i,k)}\right)^{f(type)}\]其中:\[\begin{aligned}f(0)&=1\crf(1)&=i\timesj\timesk\crf(2)&=\gcd(i,j,k)\end{aligned}\]\(T\)组数据,每......
  • 2019精选书籍推荐
    距离2020年还剩2个月的时间,整理了今年读过的书籍,精选了18本我认为比较好的书,推荐给大家。年纪大了,只看书不做笔记似乎已经不行了,记忆力下降的很快,有时候一本书读完,居然没记住多少内容。所以接下来的精读的书籍我都要做读书笔记了。人与人的差别是思维方式的差别,而思维方式来源于......
  • 程序员小灰2019年整理
    漫画:寻找无序数组的第k大元素(修订版漫画:如何将一个链表“逆序”?漫画:什么是加密算法?漫画:什么是“图”?(修订版)漫画:深度优先遍历和广度优先遍历漫画:图的“最短路径”问题漫画:Dijkstra算法的优化漫画:图的“多源”最短路径漫画:有趣的“切蛋糕“问题漫画:什么是二分查找?(修订版)漫......
  • 软件测试3班,学员就业前的模拟面试(2019-9-12)(金朝阳)
    1:你用过Fiddler在项目中发现过哪些有价值的bug?2:接口测试,返回的数据格式类型一般有哪些类型?(Json\xml\html等等)3:App兼容性测试怎么做?APP升级测试怎么做?4:你测试过哪些类型的安卓机型?哪些类型的苹果机型?5:你测试过安卓机型的操作系统是多少?苹果机型的操作系统是多少?6:你在做接口测试的......
  • 软测5班Loadrunner阶段性考试(2019-10-19)
    试题1:用你在Loadrunner中所学习的知识,将“欢迎来到然学科技”保存为一个变量,并且在日志中打印输出(10分)。答案:lr_save_string("欢迎来到科技","ranther");lr_output_message("你好:%s",lr_eval_string("{ran}"));试题2:Loadrunner中如何保持每次参数取值的唯一性(2分)?Unique+Once(保持......
  • 软测5班jmeter笔记(2019-10-29)
    接口测试理论自动化测试的金字塔模型硬件接口:比如usb接口,电源接口、耳机接口...软件接口:数据系统访问接口、http请求接口...为什么要做接口测试Web前端:指用户可以直观操作和看到的界面。html,Css样式,javascript脚本。android和ios等。web后端:是指与数据库交互进行处理响应的业务......
  • P5288 [HNOI2019]多边形
    P5288[HNOI2019]多边形Solution先进行大量的模拟。最终所有线段的端点均为点\(n\)。第一问答案为\((n-1-与n相连的线段数量)\)。可以把线段看成节点,将原图转为若干棵二叉树组成的森林。这里只建那些不与点\(n\)相连的非边线段。原操作可以看作是sp......