hdu 5159 Card (期望)-白红宇

hdu 5159 Card (期望)

阅读量：5098 次

发布时间：2019-06-13

本文共 2263 字，大约阅读时间需要 7 分钟。

Problem Description

There are x cards on the desk, they are numbered from 1 to x. The score of the card which is numbered i(1<=i<=x) is i. Every round BieBie picks one card out of the x cards，then puts it back. He does the same operation for b rounds. Assume that the score of the j-th card he picks is

Input

Multi test cases，the first line of the input is a number T which indicates the number of test cases.

In the next T lines, every line contain x,b separated by exactly one space.

[Technique specification] All numbers are integers. 1<=T<=500000 1<=x<=100000 1<=b<=5

Output

Each case occupies one line. The output format is Case #id: ans, here id is the data number which starts from 1，ans is the expectation, accurate to 3 decimal places. See the sample for more details.

Sample Input

      2 2 3 3 3 

Sample Output

      Case #1: 2.625 Case #2: 4.222 
Hint
 For the first case, all possible combinations BieBie can pick are (1, 1, 1),(1,1,2),(1,2,1),(1,2,2),(2,1,1),(2,1,2),(2,2,1),(2,2,2) For (1,1,1),there is only one kind number i.e. 1, so the sum of different score is 1. However, for (1,2,1), there are two kind numbers i.e. 1 and 2, so the sum of different score is 1+2=3. So the sums of different score to corresponding combination are 1，3，3，3，3，3，3，2 So the expectation is (1+3+3+3+3+3+3+2)/8=2.625 

Source

题意：

桌子上有a张牌，每张牌从1到a编号，编号为i(1<=i<=a)的牌上面标记着分数i , 每次从这a张牌中随机抽出一张牌，然后放回，执行b次操作，记第j次取出的牌上面分数是 Sj, 问b次操作后不同种类分数之和的期望是多少。

思路：

设Xi代表分数为i的牌在b次操作中是否被选到,Xi=1为选到，Xi=0为未选到那么期望EX=1*X1+2*X2+3*X3+…+x*XxXi在b次中被选到的概率是1-(1-1/x)^b那么E(Xi)= 1-(1-1/x)^b那么EX=1*E(X1)+2*E(X2)+3*E(X3)+…+x*E(Xx)=(1+x)*x/2*(1-(1-1/x)^b)

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 using namespace std; 8 int main() 9 {10 int t;11 scanf("%d",&t);12 double x,b;13 int ac=0;14 while(t--)15 {16 scanf("%lf%lf",&x,&b);17 double ans=0;18 double p=1-pow((1-1.0/x),b);19 double num=(1+x)*x*1.0/2;20 ans=num*p;21 printf("Case #%d: ",++ac);22 printf("%.3lf\n",ans);23 }24 return 0;25 }

View Code

转载于:https://www.cnblogs.com/UniqueColor/p/4743623.html

你可能感兴趣的文章