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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1071][SCOI2007]组队  

2015-03-18 11:41:52|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1071: [SCOI2007]组队

感觉非常厉害的题……

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 5100;
int n,m,cot,mx[2];
ll A,B,C;

struct Point{Point(ll a=0,ll b=0){x=a;y=b;s=x+y;}ll x,y,s;}data[2][N];
bool cmpx(const Point&a,const Point&b){return a.x<b.x;}
bool cmps(const Point&a,const Point&b){return a.s<b.s;}
int check(int k,int i){
return mx[0]<=data[k][i].y&&data[k][i].y<=mx[1];
}
int main(){
int i,j,a,b;
scanf("%d%lld%lld%lld",&n,&A,&B,&C);
for(i=1;i<=n;i++){
scanf("%d%d",&a,&b);
data[0][i]=data[1][i]=Point(a*A,b*B);
}
sort(data[0]+1,data[0]+1+n,cmpx);
sort(data[1]+1,data[1]+1+n,cmps);
int ans=0;
for(j=1;j<=n;j++){
mx[0] = data[0][j].y;
mx[1] = data[0][j].y+C;
int l,r;cot=0;
l=r=1;
for(i=1;i<=n;i++){
while(r<=n && data[1][r].s-(data[0][i].x+data[0][j].y)<=C)
cot += check(1,r++);
while(l<=n && data[0][l].x < data[0][i].x)
cot -= check(0,l++);
ans = max(ans,cot);
}
}
printf("%d\n",ans);
return 0;
}

别看时限这么紧……N^2和N^2logN居然都能过……
题目是让找出一个直角三角形使得包括点尽可能多
我们把x=x*A,y=y*B
大概就是说先随便枚举一下最小的y(顺序无所谓)
此时点就被限制到了[miny,miny+C]这么一个界里
然后先按照x+y序把合法的加进去(相当于右移三角形斜边)
然后再把<x的踢掉,(相当于右移三角形左边的直角边)
因为y被界确定了,所以可以发现这么做非常科学……

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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