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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ3652]大新闻  

2015-04-23 17:22:48|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3652: 大新闻

一开始不会……
后来就会了
然后似乎精度还有些问题……但是似乎是数据弱?过掉了

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int scan(){int i=0;scanf("%d",&i);return i;}
typedef long double ld;
//typedef __float128 ld;
//typedef double ld;
typedef long long ll;
const int N = 100;
const ld eps = 1e-23;
ll n;
int list[N];
ld P;
ld f[N][2][2], gl[N][2][2],one;
ll two[N];
ld get1(){
int i,j,k,l1,l2,n1,n2;
memset(f,0,sizeof(f));
memset(gl,0,sizeof(gl));
gl[list[0]+1][1][1] = one;
for(i=list[0];i;i--){
for(l1=0;l1<2;l1++)
for(l2=0;l2<2;l2++)
if(gl[i+1][l1][l2] > 0){
for(j=0;j<2;j++){
if(l1){
if(j<list[i])n1=0;
else if(j==list[i])n1=1;
else continue;
}else n1=0;
for(k=0;k<2;k++){
if(l2){
if(k<list[i])n2=0;
else if(k==list[i])n2=1;
else continue;
}else n2=0;
gl[i][n1][n2] += gl[i+1][l1][l2];
f[i][n1][n2] += f[i+1][l1][l2] + gl[i+1][l1][l2] * two[i-1] * (j^k);
}
}
}
}
ld re=0,agl=0;
for(l1=0;l1<2;l1++)
for(l2=0;l2<2;l2++)
re += f[1][l1][l2],agl+=gl[1][l1][l2];
// printf("%.5f\n",(double)(agl*one));
return re*one;
}
ld get2(){
int i,j,k,l1,l2,n1,n2;
memset(f,0,sizeof(f));
memset(gl,0,sizeof(gl));
gl[list[0]+1][1][1] = one;
for(i=list[0];i;i--){
for(l1=0;l1<2;l1++)
for(l2=0;l2<2;l2++)
if(gl[i+1][l1][l2] > 0){
for(j=0;j<2;j++){
if(l1){
if(j<list[i])n1=0;
else if(j==list[i])n1=1;
else continue;
}else n1=0;

if(l2){
k = j^1;
if(k<list[i])n2=0;
else if(k==list[i])n2=1;
else k=0,n2=1;
}else k = j^1,n2 = 0;

gl[i][n1][n2] += gl[i+1][l1][l2];
f[i][n1][n2] += f[i+1][l1][l2] + gl[i+1][l1][l2] * two[i-1] * (j^k);
}
}
}
ld re=0;
for(l1=0;l1<2;l1++)
for(l2=0;l2<2;l2++)
re += f[1][l1][l2];
return re;
}
void initialize(ll n){
one = 1./n;n--;
for(list[0]=0;n;n/=2)list[++list[0]] = (n&1);
//for(int i=1;i*2<=list[0];i++)swap(list[i],list[list[0]-i+1]);
}
int main(){
// freopen("in.txt","r",stdin);
int i,j;
for(two[0]=i=1;i<=60;i++)two[i] = two[i-1]*2;
cin >> n >> P;
initialize(n);
ld ans[2];
ans[0] = get1();
ans[1] = get2();
// printf("%.6f %.6f\n",(double)ans[0],(double)ans[1]);
ans[0] = ans[0] * (1-P) + ans[1] * P;
printf("%.6f\n",(double)ans[0]);
return 0;
}

题解:
第一问可以这么做:考虑每一位是独立的,所以计算出每一位选的概率x,异或值=1的概率就是x*(1-x) + (1-x)*x
但是这样第二问就没法做了,因为每一位并不是独立的,选了这一位可能会影响后面的位置(有上限限制)。
换个角度(From SRM656 Div1 Easy)来考虑第一问,我们类似一般数位dp,同时生成这两个数,f[i][j][k]表示从top~i这么多位已经确定,两个数的限制状态分别是j,k时的期望(再开一个数组记录一下概率),每次转移同时枚举两个数应该是什么。
第二问就可以类似地做了,只不过其中一个数不再是枚举,而是根据当前情况直接得到。
注意第一问因为一个单位的概率是1/(n^2)所以精度很容易挂……
  评论这张
 
阅读(5)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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