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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ2244][SDOI2011]拦截导弹  

2015-03-08 10:56:06|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2244: [SDOI2011]拦截导弹

比较裸的题
搞了好久- -
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int N = 5e4+100;
const double eps = 1e-10;
int n,m,tmp[N],list[N],ans,f[2][N];
struct Data{Data(int aa=0,int bb=0){a=aa;b=bb;}int a,b;}data[N];
int scan(){
char cc=' ';int re=0,fh=1;while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+')cc=getchar(),fh=1;if(cc=='-')cc=getchar(),fh=-1;
while('0'<=cc&&cc<='9'){re=re*10+cc-'0';cc=getchar();}return re*fh;
}
int tree[N],ke[N];
double num[N],ti[2][N],allnum;
void push(int x,int val,double nums){
for(;x<=list[0];x+=x&-x){
if(val > tree[x])tree[x]=val,num[x]=0;
if(tree[x] == val)num[x]+=nums;
}
}
void clear(int x){
for(;x<=list[0];x+=x&-x)tree[x]=0,num[x]=0;
}
void get(int x,int &re,double &nums){
re=nums=0;
for(;x;x-=x&-x){
if(tree[x] > re)re=tree[x],nums=0;
if(tree[x] == re)nums+=num[x];
}
}
int type;
bool cmp(int A,int B){
Data &a=data[A],&b=data[B];
if(a.a!=b.a)return a.a<b.a;
return a.b<b.b;
}
void solve(int l=1,int r=n){
if(l==r)return;
int mid = (l+r)/2,i,j,lf;double ln;
solve(l,mid);
for(i=mid+1;i<=r;i++)tmp[i]=ke[i];
sort(tmp+mid+1,tmp+r+1,cmp);
j=l;
for(i=mid+1;i<=r;i++){
for(;data[ke[j]].a<=data[tmp[i]].a && j<=mid;j++){
push(data[ke[j]].b,f[type][ke[j]],ti[type][ke[j]]);
}
get(data[tmp[i]].b,lf,ln);
if(lf){
if(f[type][tmp[i]] < lf+1){
f[type][tmp[i]]=lf+1;
ti[type][tmp[i]]=ln;
}else if(f[type][tmp[i]] == lf+1)ti[type][tmp[i]]+=ln;
}
}
for(i=l;i<=mid;i++)clear(data[ke[i]].b);
solve(mid+1,r);
merge(ke+l,ke+mid+1,ke+mid+1,ke+r+1,tmp+l,cmp);
for(i=l;i<=r;i++)ke[i]=tmp[i];
}
int main(){
//freopen("in.txt","r",stdin);
int i,j,a,b;
n = scan();
for(i=1;i<=n;i++){
a=scan();b=scan();
data[i]=Data(-a,-b);
list[++list[0]] = -b;
ke[i]=i;
ti[0][i]=ti[1][i]=1;
f[0][i]=f[1][i]=1;
}
sort(list+1,list+1+list[0]);
list[0] = unique(list+1,list+1+list[0]) - list - 1;
for(i=1;i<=n;i++)data[i].b = lower_bound(list+1,list+1+list[0],data[i].b)-list;
//for(i=1;i<=n;i++)printf("%d %d\n",data[i].a,data[i].b);printf("\n");
solve();

for(i=1;i<=n;i++){
data[i].a = - data[i].a;
data[i].b = list[0] - data[i].b+1;
ke[i]=n-i+1;
}type=1;
//for(i=1;i<=n;i++)printf("%d ",ke[i]);printf("^\n");
//for(i=1;i<=n;i++)printf("%d %d\n",data[i].a,data[i].b);printf("\n");
ans=1;
solve();
for(i=1;i<=n;i++){
if(type && f[0][i] > ans)ans = f[0][i],allnum=ti[0][i];
else if(type && f[0][i] == ans)allnum+=ti[0][i];
}
/*
for(i=1;i<=n;i++)printf("%d ",f[0][i]);printf("\n");
for(i=1;i<=n;i++)printf("%d ",f[1][i]);printf("\n");
for(i=1;i<=n;i++)printf("%.2lf ",ti[0][i]);printf("\n");
for(i=1;i<=n;i++)printf("%.2lf ",ti[1][i]);printf("\n");
*/
printf("%d\n",ans);
//printf("%.3lf\n",allnum);
for(i=1;i<=n;i++){
if(f[0][i]+f[1][i]-1 == ans)printf("%.5f ",ti[0][i]*ti[1][i]/allnum);
else printf("%.5f ",0.0);
}
return 0;
}

题解:
分治
首先求第一个答案就是一个二维最长偏序……分治一下log^2
然后求第二问,每个点的ans = 经过这个点的方案数/总方案数
经过点i的方案数 = 从左边来的方案数*从右边来的方案数 ,这个在分治的同时搞出来就行了
分治写得有点蛋疼……
因为感觉方案数会爆所以我用的是double存的
  评论这张
 
阅读(331)| 评论(1)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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