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

 
 
 

日志

 
 

SCOI 2007 组队 ( bzoj1071 ) 扫描线  

2014-03-27 11:07:12|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

bzoj上此题10个点只有1s的时间

结果似乎都是n^2+卡常数过的(表示到目前为止 我也只会n^2的)

理论上应该存在nlogn的啊,不然为何只给1s。。。

-----------------------------------------------------------------------

神犇Mato的这个零回复的帖子极大地调动了我想nlogn的想法

http://tieba.baidu.com/p/1879243693?see_lz=1

-----------------------------------------------------------------------

并且做此题时 我又回想到了我A掉的第一道扫描线的题

——vijos上的 流星雨 那题(黑书上经典例题矿洞的数据加强版)

线段树/平衡树均可做到nlogn

不过那题是矩形 这题是直角三角形额

然后一点思路都没有

最后还是决定用O(n^2)先写过

不过居然还是调了好久(i、j用混了。。。)

-----------------------------------------------------------------------

希望有神犇来讲讲nlogn的方法额 我就只贴个 n^2 的算了(要1300ms。。。)

关键词 扫描线*2+队列(其实也不完全算的)+容斥

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define rep(i,n) for(int i=1;i<=n;++i)
#define imax(x,y) (x>y?x:y)
#define imin(x,y) (x<y?x:y)
using namespace std;
const int N=5010;
struct node
{
    int x,y;
}a1[N],a2[N];
struct node2
{
    int x,y,sum;
}
a3[N];
int q[N];
int n,tx,ty,ans=0;
int a,b,c;
bool cmp1(node aa,node bb)
{
    return aa.x<bb.x;
}
bool cmp2(node aa,node bb)
{
    return aa.y<bb.y;
}
bool cmp3(node2 aa,node2 bb)
{
    return aa.sum<bb.sum;
}
int main()
{
    freopen("team.in","r",stdin);
    freopen("team.out","w",stdout);
    scanf("%d",&n);
    scanf("%d%d%d",&a,&b,&c);
    rep(i,n)
    {
        scanf("%d%d",&a1[i].x,&a1[i].y);
        a2[i]=a1[i];
        a3[i].x=a1[i].x;
        a3[i].y=a1[i].y;
        a3[i].sum=a*a3[i].x+b*a3[i].y;
    }
    sort(a1+1,a1+1+n,cmp1);
    sort(a2+1,a2+1+n,cmp2);
    sort(a3+1,a3+1+n,cmp3);
    a1[0].x=a1[1].x-1;
    a1[0].y=a2[1].y-1;
    a2[0]=a1[0];
    int f1,t1,f2,t2,tmp;
    tx=a1[0].x;
    rep(i,n)
    if(a1[i].x!=tx)
    {
        tx=a1[i].x;
        ty=a2[0].y;
        t1=t2=f1=f2=0;
        rep(j,n)
        if(a2[j].y!=ty)
        {
            ty=a2[j].y;
            int s2=a*tx+b*ty;
            while(t1<n&&(a3[t1+1].sum-s2<=c))
            {
                ++t1;
                if(a3[t1].x<tx||a3[t1].y<ty)++f1;
            }
            while(t2<n&&a2[t2+1].y<ty)
            {
                ++t2;
                if(a2[t2].x<tx||a*(a2[t2].x-tx)>c)++f2;
            }
            tmp=(t1-f1)-(t2-f2);
            ans=imax(ans,tmp);
        }
    }
    printf("%d",ans);
    return 0;
}


  评论这张
 
阅读(158)| 评论(4)
推荐 转载

历史上的今天

评论

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

页脚

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