注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

poj2019Cornfields题解  

2014-03-21 20:37:41|  分类: POJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
                                                                     玉米地
                                          BY   LGS
题解大意:给你N*N的正方形,求在这个正方形里面B*B的小正方形的最大值和最小值之差。有K个询问,每次读入要询问正方形的左上角坐标(X,Y);

题解:前几天刚学过单调队列,一看到这题就联想到了。特别是他给定了要求的B*B,这样就可以用单调队列,否则单调队列无法出队。且K比较大,一定是离线算法。对于二维的单调队列,我们可以用做2次1维的单调队列。第一次,做每行的单调队列,最大值每个区间存在B[I][J]。i,j是当前i行的最左列j。然后在用B数组做一次列的单调队列,最大值存在MAX。最小值同上。

总结:一遍A,真开心。
代码:
#include<cstdio>
#include<cstring>
#define maxn 260
using namespace std;
int i,j,k,n,st,en,m,x,y;
int q[maxn],p[maxn],max[maxn][maxn],min[maxn][maxn],
    a[maxn][maxn],b[maxn][maxn],bb[maxn][maxn];
void init(){memset(q,0,sizeof(q));memset(p,0,sizeof(p));}

void work(int i,int j)
 {
 while ((st<=en)&&(a[i][j]>q[en])) en--;
 en++;q[en]=a[i][j];p[en]=j;
 }
void work2(int i,int j)
 {
 while ((st<=en)&&(b[i][j]>q[en])) en--;
 en++;q[en]=b[i][j];p[en]=i;
 }
void work3(int i,int j)
 {
 while ((st<=en)&&(a[i][j]<q[en])) en--;
 en++;q[en]=a[i][j];p[en]=j;
 }
void work4(int i,int j)
 {
 while ((st<=en)&&(bb[i][j]<q[en])) en--;
 en++;q[en]=bb[i][j];p[en]=i;
 }
int main()
{
 scanf("%d%d%d",&n,&m,&k);
 for (i=1;i<=n;i++)
  for (j=1;j<=n;j++)
  scanf("%d",&a[i][j]);
for (i=1;i<=n;i++){
    st=1;en=0;init();
for (j=1;j<=n;j++)  {
                    work(i,j);
                  if (j>=m) b[i][j-m+1]=q[st];
                  if (p[st]==j-m+1)  st++; 
                    }
                  }

for (j=1;j<=n-m+1;j++){
      st=1;en=0;init();
   for (i=1;i<=n;i++){
                   work2(i,j);
          if (i>=m) max[i-m+1][j]=q[st];
          if (p[st]==i-m+1) st++;
                     } 
                      }
for (i=1;i<=n;i++){
    st=1;en=0;init();
for (j=1;j<=n;j++)  {
                    work3(i,j);
                  if (j>=m) bb[i][j-m+1]=q[st];
                  if (p[st]==j-m+1)  st++; 
                    }
                  }
for (j=1;j<=n-m+1;j++){
      st=1;en=0;init();
   for (i=1;i<=n;i++){
                   work4(i,j);
          if (i>=m) min[i-m+1][j]=q[st];
          if (p[st]==i-m+1) st++;
                     } 
                      }
for (i=1;i<=k;i++){scanf("%d%d",&x,&y);printf("%d\n",max[x][y]-min[x][y]);}
return 0;
}

  评论这张
 
阅读(587)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018