LightOj_1342 Aladdin and the Magical Sticks

题目链接

题意:

  地上有n种棍子, 其中有两种类型, 一种类型是可识别, 一种类型是不可识别, 每个棍子都有一个权值。

  当你捡到可识别的, 那么你以后就不会再捡这个棍子, 如果是不可识别的, 那么你有可能还会捡。

  问将所有棍子收集完的权值的期望。

思路:

  此题借鉴参考了此篇文章:Aladdin and the Magical Sticks

  首先, 这个题初看起来, 和LightOj 1027  A Dangerous Maze有点像, 只不过, 这里是要将所有的门都走遍。

  先引入一个经典的问题:

邮票收集问题(Coupon Collector Problem)WiKi资料

几何分布期望的证明过程

  求解邮票收集问题时, 由概率求期望时需要用到几何分布期望, 因此这里给出了几何分布期望的证明过程。 很简洁明了, 还有大量例子结合理解。

  通过上面的问题, 我们可以假设, 我们现在面对的是一个n面的骰子, 骰子的每面都是随机出现的(相当于是不可识别的棍子), 求问将所有面都被看完所期望的投掷次数(假设只看最上面那一面)

  那么, 问题的解就是:

            H[n] = (1 + 1/2 + 1/3 + 1/4 + ... + 1/n),  这就是调和级数的前n项。

            这个值近似等于欧拉常数约为:0.57721566490153286060651209。(不过这是一个当n接近无穷时的近似值, 并不能代替具体的H[n], 比如当 n = 1 || 2时)

  而所求的是期望的权值, 根据期望的线性性质E(XY) = E(X)*E(Y) 

  所以, 总的权值期望就等价于 每次的权值期望 * 次数的期望。

  n个面, 每个面至少出现一次的期望次数是:E(x) = n * H[n],那么, 某个指定的面至少出现一次的期望次数就是E(z) = E(x)/n = H[n]。

  因此, 假设这n个棍子都是不可识别的时候所期望的权值为:

                            Ea = E(w) * E(x), E(w)为权值的期望 = 权值的平均值。

  但是, 这n个棍子里还有一些是可以识别的, 因此还要减去多余的期望。

  先来计算一下可识别的棍子所需要的期望的次数, 这个答案为1。

  当有六个球在箱子里, 采用不放回抽样, 你将六个球抽出来所期望的次数是多少?这是一个固定的值, 为6。

  因此, 每个棍子多出来的部分就是(H[n] - 1) * w[i]。w[i]为某个可识别的棍子的权值。

  设, 所有棍子的权值平均值为Wn

  假设有k个可识别的棍子, 其权值平均值为Wk

  So , 答案为: Ea - Eb = Wn * n * H[n] - k * Wk * (H[n] - 1)

     化简: E = (Wn * n - k * Wk) * H[n] + k * Wk。

代码:

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <ctime>
 6 #include <set>
 7 #include <map>
 8 #include <list>
 9 #include <queue>
10 #include <string>
11 #include <vector>
12 #include <fstream>
13 #include <iterator>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17 #define LL long long
18 #define INF 0x3f3f3f3f
19 #define MOD 1000000007
20 #define eps 1e-6
21 #define MAXN 5050
22 #define MAXM 100
23 #define dd cout<<"debug"<<endl
24 #define pa {system("pause");}
25 #define p(x) printf("%d\n", x)
26 #define pd(x) printf("%.7lf\n", x)
27 #define k(x) printf("Case %d: ", ++x)
28 #define s(x) scanf("%d", &x)
29 #define sd(x) scanf("%lf", &x)
30 #define mes(x, d) memset(x, d, sizeof(x))
31 #define do(i, x) for(i = 0; i < x; i ++)
32 #define dod(i, x, l) for(i = x; i >= l; i --)
33 #define doe(i, x) for(i = 1; i <= x; i ++)
34 int n;
35 double h[MAXN];
36 void init()
37 {
38     h[0] = 0;
39     for(int i = 1; i < MAXN; i ++)
40         h[i] = h[i - 1] + 1.0 / i;
41 }
42 
43 int main()
44 {
45     int T;
46     int kcase = 0;
47     init();
48     scanf("%d", &T);
49     while(T --)
50     {
51         scanf("%d", &n);
52         int a, b;
53         double ans = 0;
54         for(int i = 0; i < n; i ++)
55         {
56             scanf("%d %d", &a, &b);
57             ans += a * (b == 1? 1 : h[n]);
58         }
59         printf("Case %d: %.5lf\n", ++ kcase, ans);
60     }
61     return 0;
62 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券