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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Vijos】【p1055】【奶牛浴场】  

2014-03-25 17:28:16|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    做完这题发现咱是蒟蒻中的蒟蒻....
    题目大意:给一个矩形和矩形中的一些障碍物,求一个最大子矩阵不包含任何障碍物。
    不会做...所以去看了一篇论文。论文君
    以前看过,现在完全忘了233......看了之后感觉:特别神= =。
    然后这一题用第一种方法就非常不错了...
    先来讲讲第一种方法咱的做法(QAQ,貌似实现出来时间比其他人慢了2倍~4倍以上233):
    1)读入所有障碍物的点的坐标x,y 
    2)对y排序,然后用每一对相邻的y的差乘以该矩形的长来更新答案(就是论文中的预处理的情况)
    3)对x排序,然后先从左到右,枚举点xi作为该矩形的左边上的点,并设置上界为l,下界为0,然后扫一遍这个点之后的所有的点,每碰到一个点用这两个点的x之差乘以上界减去下界之差更新答案,然后按照论文中所说的修改上下界即可。然后把所有的x的排列倒过来,再做一遍即可。
    关于这个的正确性的证明,首先显然肯定该最大子矩阵的四条边上都有点,所以枚举左边的点是可行的,然后这个也是最优的。所以这个可以AC本题。
这是论文中算法1的代码。
===============================

program vijosp1055;
const maxn=5010;
type point=record
     x,y:longint;
     end;
     arr=array[0..maxn]of point;

var y:array[0..maxn]of longint;
    p:array[0..maxn]of point;
    n,m,s:longint;
    ans:int64;

procedure qsort(l,r:longint);
var i,j,u,v:longint;
begin
  i:=l;j:=r;
  u:=y[(l+r)shr 1];
  repeat
    while y[i]<u do inc(i);
    while y[j]>u do dec(j);
    if i<=j then
     begin
       v:=y[i];y[i]:=y[j];y[j]:=v;
       inc(i);dec(j);
     end;
  until i>j;
  if i<r then qsort(i,r);
  if j>l then qsort(l,j);
end;

procedure qsort(l,r:longint;var a:arr);
var i,j,x:longint;y:point;
begin
  i:=l;j:=r;
  x:=a[(l+r)shr 1].x;
  repeat
    while a[i].x<x do inc(i);
    while a[j].x>x do dec(j);
    if i<=j then
     begin
       y:=a[i];a[i]:=a[j];a[j]:=y;
       inc(i);dec(j);
     end;
  until i>j;
  if i<r then qsort(i,r,a);
  if j>l then qsort(l,j,a);
end;

procedure main;
var i,j,l,r:longint;
    area:int64;
begin
  for i:=1 to s do
   begin
     l:=m;r:=0;
     for j:=i+1 to s do
      begin
        area:=abs(p[j].x-p[i].x)*(l-r);
        if area>ans then ans:=area;
        if p[i].y<p[j].y then
         begin
           if l>p[j].y then l:=p[j].y;
         end
        else
         begin
           if r<p[j].y then r:=p[j].y;
         end;
      end;
     l:=m;r:=0;
     for j:=i-1 downto 1 do
      begin
        area:=abs(p[j].x-p[i].x)*(l-r);
        if area>ans then ans:=area;
        if p[i].y<p[j].y then
         begin
           if l>p[j].y then l:=p[j].y;
         end
        else
         begin
           if r<p[j].y then r:=p[j].y;
         end;
      end;
   end;
end;

procedure init;
var i:longint;j:point;
begin
  read(n,m);
  read(s);
  for i:=1 to s do
   begin
     read(p[i].x,p[i].y);
     y[i]:=p[i].y;
   end;
  inc(s);p[s].x:=0;p[s].y:=0;y[s]:=0;
  inc(s);p[s].x:=0;p[s].y:=m;y[s]:=m;
  inc(s);p[s].x:=n;p[s].y:=0;y[s]:=0;
  inc(s);p[s].x:=n;p[s].y:=m;y[s]:=m;
  qsort(1,s);
  qsort(1,s,p);
  ans:=0;
  for i:=1 to s-1 do
   if ans<(y[i+1]-y[i])*n then
     ans:=(y[i+1]-y[i])*n;
  main;
  write(ans);
end;

begin
  init;
end.

====================================
    然后第二种方法就是悬线法。
    首先悬线法的初步理解可以去百度下 一道叫 玉蟾宫的题目的题解(推荐lydrainbowcat神犇的题解),感觉那里面的 h[]其实就是悬线的长度,非常巧妙。
    实际上感觉看完论文就应该都容易懂了...
    当然第二个算法在本题中如果直接用的话肯定TLE无误....所以得另外想办法...
    当然就是离散哈....实际上有用的悬线就只有那一些行或者列存在障碍物的点。首先加上四个边界点,然后把这个矩形离散掉,然后再按论文中的做就可以了,离散之后的矩形大小为O(S^2)级别,所以这个也就是O(S^2)级别的。不过加上离散化的二分查找还是略DT的。
    所以就待码吧= =
     等等!突然发现...离散化的话...实际上就跟S有关了...那么...为什么咱要用这个方法结果也是O(S^2)..囧....

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

历史上的今天

评论

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

页脚

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