首页 > 代码库 > hdu 2888 Check Corners
hdu 2888 Check Corners
/* 题意:给出m,n代表给出长为m宽为n的矩阵,然后给出一个q代表查询的次数,然后q行每行给出一个 r1, c1, r2, c2 且满足(1 <= r1 <= r2 <= m, 1 <= c1 <= c2 <= n) 输出这个矩形范围内的最大值,如果最大值是四个顶点某一个的话就输出yes否则输出no */ #include<stdio.h> #include<math.h> #define Max(a,b) a>b?a:b int dp[305][305][9][9];//dp[x][y][i][j]dp状态的定义是前两维代表的是横纵坐标,后两维i代表的是在横坐标上2^i,j代表的是纵坐标上2^j int getMax(int a,int b,int c,int d) { int Mx=(int)(log(c-a+1)/log(2)); int My=(int)(log(d-b+1)/log(2)); return Max((Max(dp[a][b][Mx][My],dp[c-(1<<Mx)+1][b][Mx][My])),(Max(dp[a][d-(1<<My)+1][Mx][My],dp[c-(1<<Mx)+1][d-(1<<My)+1][Mx][My]))); } int dd(int a,int b,int c,int d,int Maax) { if(dp[a][b][0][0]==Maax) return 1; if(dp[a][d][0][0]==Maax) return 1; if(dp[c][b][0][0]==Maax) return 1; if(dp[c][d][0][0]==Maax) return 1; return 0; } int main() { int m,n; while(scanf("%d%d",&n,&m)!=EOF) { for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) scanf("%d",&dp[i][j][0][0]);//当i==j==0时dp[x][y][0][0]存的是点的值 int Mx=(int)(log(n)/log(2));//横坐标的倍增最大范围 int My=(int)(log(m)/log(2));//纵坐标的倍增最大范围 for(int i=0; i<=Mx; i++) for(int j=0; j<=My; j++) { if(i==0&&j==0)//当i==j==0时这个是一个点 continue; for(int x=1; x+(1<<i)-1<=n; x++)//把下面的两层for循环整体看的话就是遍历一遍原来的二维地图 for(int y=1; y+(1<<j)-1<=m; y++) { if(i==0) dp[x][y][i][j]=Max(dp[x][y][i][j-1],dp[x][y+(1<<(j-1))][i][j-1]);//当i==0时说明i控制的1的范围也就是,在每一列上进行dp相当于原来的一维rmq else dp[x][y][i][j]=Max(dp[x][y][i-1][j],dp[x+(1<<(i-1))][y][i-1][j]);/*当i!=0的时候说明每一列的dp已经知道 我们把行进行分开进行dp,可以整体考虑为,以x,y为起点的在行的宽为2^i,纵宽为2^j这样矩形的最大值 */ } } scanf("%d",&m); int a,b,c,d; for(int i=0;i<m;i++) { scanf("%d%d%d%d",&a,&b,&c,&d); int Maax=getMax(a,b,c,d); printf("%d %s\n",Maax,dd(a,b,c,d,Maax)?"yes":"no"); } } return 0; } /* 10 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 2 3 4 5 6 7 8 9 10 1 100 10 1 10 10 */
hdu 2888 Check Corners
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。