<span>HDU2888 Check Corners（二维RMQ）</span>

题意：给一个矩阵，然后Q个询问，每个询问有四个数，分别代表询问的子矩阵的左上角和右下角，

然后找出子矩阵的最大值输出，然后再把这个值与子矩阵的四个角的值比较，

如果有至少一个等于这个最大值就输出“yes”，否则输出“no”。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <cstdio>
#define MAXN 305
int n,m,val[MAXN][MAXN],dpmax[MAXN][MAXN][9][9];
void ST()
{
    int i,j,r,c,k1=0,k2=0;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            dpmax[i][j][0][0]=val[i][j];
    while((1<<(k1+1))<=n) k1++;
    while((1<<(k2+1))<=m) k2++;
    for(i=0; i<=k1; i++)
    {
        for(j=0; j<=k2; j++)
        {
            if(!i&&!j) continue;
            for(r=1; r+(1<<i)-1<=n; r++)
            {
                for(c=1; c+(1<<j)-1<=m; c++)
                {
                    if(!i) dpmax[r][c][i][j]=max(dpmax[r][c][i][j-1],dpmax[r][c+(1<<(j-1))][i][j-1]);
                    else dpmax[r][c][i][j]=max(dpmax[r][c][i-1][j],dpmax[r+(1<<(i-1))][c][i-1][j]);
                }
            }
        }
    }
}
int query(int r1,int c1,int r2,int c2)
{
    int kr=0,kc=0;
    while((1<<(kr+1))<=(r2-r1+1)) kr++;
    while((1<<(kc+1))<=(c2-c1+1)) kc++;
    int t1=dpmax[r1][c1][kr][kc];
    int t2=dpmax[r2-(1<<kr)+1][c1][kr][kc];
    int t3=dpmax[r1][c2-(1<<kc)+1][kr][kc];
    int t4=dpmax[r2-(1<<kr)+1][c2-(1<<kc)+1][kr][kc];
    return max(max(t1,t2),max(t3,t4));
}
int main()
{
    int i,j,k,r1,c1,r2,c2;
    while(~scanf("%d%d",&n,&m))
    {
        for(i=1; i<=n; i++)
            for(j=1; j<=m; j++)
                scanf("%d",&val[i][j]);
        ST();
        scanf("%d",&k);
        while(k--)
        {
            scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
            int ret=query(r1,c1,r2,c2);
            printf("%d ",ret);
            if(val[r1][c1]==ret||val[r1][c2]==ret||val[r2][c1]==ret||val[r2][c2]==ret) printf("yes\n");
            else printf("no\n");
        }
    }
    return 0;
}

全部评论

推荐最新楼层

03-14 10:50

已编辑

门头沟学院 Java

华为秋招炮灰有感

鼠鼠华子无线实习，bg双九，通软岗位，论文，专利，竞赛都水过一点，秋招《非all in》选手，《泡池子泡到肿》选手，分享一下自己的时间线，给大家多一个参考。---实习末期，接口人电话沟通，最终决定求稳继续投递实习原部门---免机试，九月走完线下流程，开始入池---十月起开始保温，打听手中已拿offer，比较薪资，给出华子的预估职级和薪资（完全不给A的空间）---十月第二次保温，询问签约情况，各种暗示劝说留空白三方---十月底签约另一家公司，遂被降低优先级---十一月若干次常规保温信息（还有机会/稍晚一点/等这周。。。）---十二月告知部门有13的指标，愿意接受可以立刻发offer（难绷，妄图性...

蓦然回首一枝花：能体会楼主的心情，我投了华为无线的成研所，双9bg，被华子最后开了个13级的侮辱价 12.3打oc电话的时候接口人表示乐观等待就行，然后中间4周就开始不回消息或者拖四五天才回，翻来覆去就是“等审批结果”。 12月27号，我看应该是泡不出来了所以联系了部门流转，这时候接口人开始主动给我打电话告诉我马上就能出结果了，于是我也没继续流转。 12.31给我打电话说得降薪审批，薪资大概就是对应着13级的样子，但我当时因为投的是成都的，没有意识到薪资是按照上海开的，还以为这个薪资在成都是14级，加上那个时候我也“孝”劲上来了，想着能收我就行，于是答应了。 1.13开了出来，联系我了薪资，确认了下发现是13级，当时实在是接受不了，于是最终还是拒了。拒的时候接口人告诉我说这个hc真的是他们争取了很久才争取到的，不过我一想到我12.3就打了oc电话，中间4周一直不搭理我或吊着我，最后12.31才告诉我争取不下来14级要降薪，也许争取真的要争取那么久吧，呵。这个过程中也为华为拒了不少offer，大厂的、央企的、银行的都拒过，网上总说“华为没有发小奖状之前hr的话一个字都不要信”，当时没有放在心上，以为不会摊到我头上，现在来看当时也挺年轻气盛的。我感觉要不是中途我一直在烦hr，可能我就和楼主一样被泡死了吧，不过最后给开了个13级也和泡死没差，不过是被多侮辱了一次。最后借楼主这个贴就只想跟后面的人提一个建议吧，还是那句说烂了的，“华为没有发小奖状之前hr的话一个字都不要信”，真的不要以为这样的情况不会出现在自己身上，不要拿自己的一辈子前途去送华为hr业绩。

点赞评论收藏