首页 > 代码库 > hdu 4465 Candy

hdu 4465 Candy

2024-07-15 06:35:21   211人阅读

题意：

有两个箱子，每个箱子里面都有n个糖果,每次LazyChild会选一个箱子，并吃掉一个糖果，如果里面没有糖果，则去另一个箱子去吃

LazyChild 选第一个箱子的概率为 p，选择第二个箱子的概率为q=1-p

求：当LazyChild选择一个箱子时，里面没有糖果了，另一个箱子里糖果数量的期望

因为要使得一个箱子里的糖果数为0 ，所以选择的次数为n+k

（p+q）^(n+k)........(k=0,1,2...n-1)

此时的期望为 (2n-n-k)*C（n+k,k）*(p^k*q^n+p^n*q^k)

但是因为 求的是当LazyChild选择一个箱子时，里面没有糖果了，另一个箱子里糖果数量的期望，所以糖果数为0的那个箱子应该被选n+1次

所以期望应该为(2n-n-k)*C（n+k,k）*(p^k*q^(n+1)+p^(n+1)*q^k)

为了不超时，所以用了log对组合数进行优化（觉得叼叼的）

 1 #include<iostream> 2 #include<string> 3 #include<cstdio> 4 #include<vector> 5 #include<queue> 6 #include<stack> 7 #include<algorithm> 8 #include<cstring> 9 #include<stdlib.h>10 #include<cmath>11 using namespace std;12 #define pb push_back13 double fuck[201000];14 double cal(int n,int m){15     return fuck[n]-fuck[m]-fuck[n-m];16 }17 int main(){18     for(int i=1;i<=200000;i++)19         fuck[i]+=fuck[i-1]+log(1.0*i);20     int n,cas=0;21     double p,q,tmp1,tmp2;22     while(cin>>n>>p){23         q=1-p;24         double ans=0;25         tmp1=log(p),tmp2=log(q);26         for(int i=0;i<n;i++){27              ans+=exp(tmp1*(n+1)+tmp2*i+cal(n+i,i))*(n-i);28              ans+=exp(tmp1*i+tmp2*(n+1)+cal(n+i,i))*(n-i);29         }30         printf("Case %d: %.7lf\n",++cas,ans);31     }32 }

 


联系
我们