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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ1071】【SCOI2007】【组队】  

2014-03-26 21:39:12|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
      (首先感谢wshjzaa君直接一语道破题解,orz....)
      额...题意挺纠结的...
      题目大意:有一些球员,每个球员有height和speed两项参数,从中选出一些球员,设其中的min(height)为MinH,同理min(speed)为MinV,要求满足对于所有队员都有不等式:A*(height-MinH)+B*(speed-MinV)<=C,ABC已知,求最多能选多少人?
      题目比较囧...首先咱们令 height=x,speed=y,MinH=x',MinV=y',那么咱们就可以草稿纸上算出 Ax+By<=C+A*x'+B*y',然后还得有x>=x',y>=y'。咱们可以枚举x',y',然后就是统计这个半平面交(实际上就是三角形)内部的点的个数。关键在于如何统计....貌似可以YY到bzoj1062糖果雨的统计方法,但是貌似这个没有用....
      然后统计不会...
      所以还是去orz去了.... 一些神奇的方法(咱想学学线性规划啊233)
     先来看看一些关于这个三角形的性质。显然底坐标就是咱们的 (x',y'),然后高只需要代入x=x'即可得到 (x',y'+C/B),然后同理代入y'可以得到 (x'+C/A,y'),这是这个三角形的三个顶点的坐标,即两个直角边为 C/B与C/A。
     然后那个神奇的做法咱还是来yy下吧...
     
    首先对于咱们枚举直角三角形的左下端点(x0,y0),那么咱们的任务就是统计这样一个直角三角形的内部区域的点,所有在这个三角形内部的点满足 三个东西: 

     xi>=x0;
     yi>=y0;
     A*xi+B*yi<=C+A*x0+B*y0

    如果直接暴力的话的确是O(n^3),但是咱们可以发现一点,那就是相邻的转移实际上是有联系的,也许咱们能用这种联系来降低复杂度 (先orz wshjzaa君....这题蒟蒻卡了几天了233...)

    咱们先来看看算法怎么做:
    1)咱们需要预处理几个东西,就是按y降序排序后的点集,然后就是把y和xi*a+yi*b离散化(降序)。
    2)把 A*xi+B*yi离散化,开一个数组num[],num[i]表示 A*xi+B*yi=i(离散化后)的点出现了多少次。
    3)首先暴力枚举每一个点,以(xi,yi)暴力求出有多少点在三角形内部,然后把这些点的 A*xi+B*yi插入num[]。用一个tot统计这个时候的点。
    4)从yi开始降序枚举y坐标yj,以(xi,yj)为左下角,然后每一次把yj的点集中x>xi且a*x+b*y<=c+a*xi+b*yj的加入,并插入到num[]中,然后用tot-此时的num[i](i满足w[i]>a*xi+b*yj+c),就是这个三角形内部的答案。
    5)关于4):w[]实际上一开始想的是树状数组,然后这个的话复杂度加上离散化的二分的话就是O(n^2log^2n),但是咱们可以发现这个区域是一个单调的,所以咱们维护两个指针,然后如果新增加元素的话右指针如果小于它的话就右移,然后询问的左区间单调递增,然后每一次左移的时候减出去那部分点即可。这样子就是O(1)的了,然后离散化以前都傻叉只会写二分查找,没想过预处理233,预处理完之后复杂度就是O(n^2)的了。

    以上的复杂度,2)的暴力是O(n)的,之后的加点也是每个点进入一次或者不进入,也是O(n)的,然后每一次枚举xi,都做一遍,所以复杂度O(n^2),足以ac此题了。

    另外由于p 没有函数模板,所以写了三个快排一个二分查找略显DT TAT。

    然后上面口胡实在看不懂的话,可以看看下面的题解....(不是咱的...)(不过思想貌似和上面的略有不同,上面是从上至下扫描,这个是从下至上扫描)
    【BZOJ1071】【SCOI2007】【组队】 - z55250825 - z55250825
 
================================

program bzoj1071;
const maxn=5010;
type point=record
     x,y,bh,bh2:longint;
     w:longint;
     end;
     arr1=array[0..maxn]of longint;
     arr2=array[0..maxn]of longint;
     arr3=array[0..maxn]of point;

var p:array[0..maxn]of point;
    y,w,num,st,ed:array[0..maxn]of longint;
    sum1,sum2,sum3,n,ans,tot,a,b,c:longint;

procedure qsort(l,r:longint;var a:arr1);
var i,j,x,y:longint;
begin
  i:=l;j:=r;
  x:=a[(l+r)shr 1];
  repeat
    while a[i]>x do inc(i);
    while a[j]<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 qsort(l,r:longint;var a:arr3);
var i,j,x:longint;y:point;
begin
  i:=l;j:=r;
  x:=a[(l+r)shr 1].y;
  repeat
    while a[i].y>x do inc(i);
    while a[j].y<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;

function find(x,n:longint):longint;
var l,r,mid:longint;
begin
  l:=1;r:=n;
  while l<r do
   begin
     mid:=(l+r)shr 1;
     if w[mid]=x then exit(mid);
     if w[mid]<x then r:=mid-1
                 else l:=mid+1;
   end;
  exit(l);
end;

function find(x:longint):longint;
var l,r,mid:longint;
begin
  l:=1;r:=sum2;
  while l<r do
   begin
     mid:=(l+r)shr 1;
     if y[mid]=x then exit(mid);
     if y[mid]<x then r:=mid-1
                 else l:=mid+1;
   end;
  exit(l);
end;

procedure init;
var i,j,k,l:longint;
    ff:boolean;
begin
  read(n,a,b,c);
  for i:=1 to n do
   begin
     read(p[i].x,p[i].y);
     p[i].w:=p[i].x*a+p[i].y*b;
     y[i]:=p[i].y;
     w[i]:=p[i].w;
   end;
  qsort(1,n,y);
  qsort(1,n,w);
  qsort(1,n,p);
  sum2:=1;
  for i:=2 to n do
   if y[sum2]<>y[i] then
    begin
      inc(sum2);
      y[sum2]:=y[i];
    end;
  sum3:=1;
  for i:=2 to n do
   if w[sum3]<>w[i] then
    begin
      inc(sum3);
      w[sum3]:=w[i];
    end;
  for i:=1 to n do
   begin
    p[i].bh:=find(p[i].w,sum3);
    p[i].bh2:=find(p[i].y);
   end;
  fillchar(st,sizeof(st),0);
  fillchar(ed,sizeof(ed),0);
  fillchar(num,sizeof(num),0);
  for i:=1 to n do
   begin
     if (i=1)or(p[i].bh2<>p[i-1].bh2) then st[p[i].bh2]:=i;
     if (i=n)or(p[i].bh2<>p[i+1].bh2) then ed[p[i].bh2]:=i;
   end;
  ans:=0;w[0]:=maxlongint;
  for i:=1 to n do
   begin
     tot:=0;l:=0;
     for j:=1 to n do
      if (p[j].y>=p[i].y)and(p[j].x>=p[i].x)and
      (p[j].w<=c+p[i].w)then
       begin
         inc(tot);
         inc(num[p[j].bh]);
       end;
     while (w[l]>p[i].w+c)and(l<=sum3) do
      begin
         dec(tot,num[l]);
         num[l]:=0;
         inc(l);
      end;
     if ans<tot then ans:=tot;
     for j:=p[i].bh2+1 to sum2 do
      begin
        if y[j]+c/b<p[i].y then break;
        ff:=false;
        for k:=st[j] to ed[j] do
         if (p[k].x>=p[i].x)and(p[k].w<=c+p[i].x*a+y[j]*b) then
          begin
            inc(tot);
            inc(num[p[k].bh]);
            ff:=true;
          end;
        if not ff then continue;
        while (w[l]>p[i].x*a+y[j]*b+c)and(l<=sum3) do
         begin
           dec(tot,num[l]);
           num[l]:=0;
           inc(l);
         end;
        if ans<tot then ans:=tot;
      end;
     while l<=sum3 do
      begin
        num[l]:=0;
        inc(l);
      end;
   end;
  write(ans);
end;

begin
  init;
end.


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

历史上的今天

评论

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

页脚

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