Topic link

The question :

There are... On the ground n Planting sticks , There are two types , One type is recognizable , One type is unrecognizable , Each stick has a weight .

When you find something recognizable , Then you won't pick up this stick in the future , If it's not recognizable , Then you might pick up .

Ask the expectation that all the sticks will be collected .

Ideas :

This topic draws lessons from this article :Aladdin and the Magical Sticks

First , At first, it seems that , and LightOj 1027  A Dangerous Maze It's kind of like , It's just , This is to go through all the doors .

Let's start with a classic question :

Stamp collection issues (Coupon Collector Problem)WiKi Information

The proof process of expectation of geometric distribution

When solving the stamp collection problem , We need to use geometric distribution expectation when we calculate expectation from probability , So the proof process of expectation of geometric distribution is given here . It's very concise , There are a lot of examples to understand .

Through the questions above , We can assume that , We are now facing a n Face dice , Every side of the dice is random ( It's like an unrecognizable stick ), Ask for the expected number of times that all faces will be seen ( Let's just look at the top side )

that , The solution to the problem is :

H[n] = (1 + 1/2 + 1/3 + 1/4 + ... + 1/n),   This is it. The first part of harmonic series n term .

This value is approximately equal to Euler constant about :0.57721566490153286060651209.( But it's a time when n An approximation to infinity , It's not a substitute for concrete H[n], For example, when n = 1 || 2 when )

And what we're looking for is the expected weight , According to the linear property of expectation E(XY) = E(X)*E(Y)

therefore , The total weight expectation is equivalent to The weight expectation of each time * The number of expectations .

n Face to face , The expected number of times each face appears at least once is :E(x) = n * H[n], that , The expected number of times a given face appears at least once is E(z) = E(x)/n = H[n].

therefore , Assume that this n When all sticks are unrecognizable, the expected weight is :

Ea = E(w) * E(x), E(w) For the expectation of weight = The average of the weights .

however , this n Some of the sticks are recognizable , So subtract the extra expectations .

Let's first calculate the expected number of times a recognizable stick needs to be recognized , The answer is 1.

When there are six balls in the box , Using no return sampling , How many times do you expect to draw six balls ? This is a fixed value , by 6.

therefore , The extra part of every stick is (H[n] - 1) * w[i].w[i] For the weight of some recognizable stick .

set up , The average weight of all sticks is Wn

Suppose there is k A recognizable stick , The average value of its weight is Wk

So , The answer for : Ea - Eb = Wn * n * H[n] - k * Wk * (H[n] - 1)

Simplification : E = (Wn * n - k * Wk) * H[n] + k * Wk.

Code :

 #include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <string>
#include <vector>
#include <fstream>
#include <iterator>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define eps 1e-6
#define MAXN 5050
#define MAXM 100
#define dd cout<<"debug"<<endl
#define pa {system("pause");}
#define p(x) printf("%d\n", x)
#define pd(x) printf("%.7lf\n", x)
#define k(x) printf("Case %d: ", ++x)
#define s(x) scanf("%d", &x)
#define sd(x) scanf("%lf", &x)
#define mes(x, d) memset(x, d, sizeof(x))
#define do(i, x) for(i = 0; i < x; i ++)
#define dod(i, x, l) for(i = x; i >= l; i --)
#define doe(i, x) for(i = 1; i <= x; i ++)
int n;
double h[MAXN];
void init()
{
h[] = ;
for(int i = ; i < MAXN; i ++)
h[i] = h[i - ] + 1.0 / i;
} int main()
{
int T;
int kcase = ;
init();
scanf("%d", &T);
while(T --)
{
scanf("%d", &n);
int a, b;
double ans = ;
for(int i = ; i < n; i ++)
{
scanf("%d %d", &a, &b);
ans += a * (b == ? : h[n]);
}
printf("Case %d: %.5lf\n", ++ kcase, ans);
}
return ;
}

LightOj_1342 Aladdin and the Magical Sticks More articles about

  1. LightOJ 1342 Aladdin and the Magical Sticks [ Thoughts ]

    Topic link : http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=27050 --------------------------- ...

  2. LightOJ 1342 Aladdin and the Magical Sticks expect ( Conclusion question )

    Subject portal The question :n A stick , Every stick has a weight , There are recognizable sticks and unrecognized sticks , Every time you draw a stick , It accumulates the weighted value , If it's a recognizable stick, don't put it back , The unidentified stick is put back , Ask each stick to be drawn at least once , The expectation of weight ...

  3. KUANGBIN Take you fly

    KUANGBIN Take you fly The whole topic is arranged https://www.cnblogs.com/slzk/articles/7402292.html Topic 1 Simple search POJ 1321  Chessboard problem     //201 ...

  4. kuangbin Take you fly Probability expectation

    If you can't push forward, push backward ! Classical problems : Birthday paradox Replace it with its mutually exclusive events :m personal , The probability that everyone's birthday is different ≤ 0.5 The minimum number of people . This is a distortion of the stamp collection problem : The probability of each stamp appearing at least once Less than or equal to 0.5 Stamp collection issues ...

  5. [kuangbin Take you fly ] project 1-23 Summary of the list of topics

    [kuangbin Take you fly ] project 1-23 Topic 1 Simple search  POJ 1321  Chessboard problem POJ 2251 Dungeon MasterPOJ 3278 Catch That CowPOJ 3279 Fli ...

  6. ACM--[kuangbin Take you fly ]-- project 1-23

    Topic 1 Simple search POJ 1321  Chessboard problem POJ 2251 Dungeon MasterPOJ 3278 Catch That CowPOJ 3279 FliptilePOJ 1426 Find T ...

  7. Codeforces Round #654 (Div. 2) A~E Answer key

    LINK:CF R 654 div2 Preface :F The topic is a topic of segment tree classification I didn't watch the game It didn't feel interesting after the game So it's goofing off . A note : For the first time, write a general title of a game Maybe I played a bad game The title is not difficult. ...

  8. Codeforces Round #654 (Div. 2)

    Match Links :https://codeforces.com/contest/1371 A. Magical Sticks The question Yes $n$ A stick , Length from $1$ To $n$, You can connect two sticks at a time , ...

  9. LightOJ 1341 - Aladdin and the Flying Carpet ( Unique decomposition theorem + Prime screening )

    http://lightoj.com/volume_showproblem.php?problem=1341 Aladdin and the Flying Carpet Time Limit:3000 ...

Random recommendation

  1. ASP.NET Form verification implementation analysis

    First , Configuration, of course  Web.config, stay  <system.web>  Lower setting : <authentication mode="Forms"> <form ...

  2. obtain PC Or all of the mobile devices IP Address

    Whether it's PC Or mobile devices , It's possible to have several at the same time IP Address ( If you have multiple network cards ), This article describes how to obtain PC Or all of the mobile devices IP Address . // Get all IP Address public static void get_ip(){ ...

  3. Scalaz(15)- Monad: Dependency injection -Reader besides Cake

    We can use Monad Reader To implement dependency injection (dependency injection DI or IOC) function .Scala The more commonly used in the world does not attach any Framework The way of dependency injection can be said to be Cake ...

  4. load ComboBox Control

    /// <summary> /// Loading companies /// </summary> /// <param name="cbbCompany">Combo ...

  5. add to SecondaryNameNode

    Many people on the Internet are wrong in their writing process , The key configuration is not written . SecondaryNameNode There are two ways to start One : Throughout hdfs When the system starts , stay namenode On the implementation start-dfs.sh be namenode ...

  6. chrome Disable a website js Script execution

      1 First, open Google browser . as follows 2 Click on the top right corner , Open the menu and go to [ Set up ] 3 After opening , The first interface doesn't have this , To scroll to the last click [ Display advanced Settings ...] 4 On the second page , Click on [ Privacy settings ]->[ Content design ...

  7. python—— modular

    One . The import module Python The reason why it is more and more widely used , To a certain extent, it also depends on the fact that it provides a large number of modules for programmers to use , If you want to use modules , You need to import . There are several ways to import modules : 1 import module 2 fr ...

  8. EF Core Take advantage of Mysql Data synchronization of data storage under concurrent access

    Little story Before I start this article , Let's have a little story , Pure fiction ( The real logic of saving money is not that ) After Xiao Liu's salary , Hurry to the bank with the cash , Ready to save the money , And at the same time , Liu's wife Liu Sao knows Xiao Liu's character , Know the day when he gets paid , also ...

  9. 【 Android Development 】Facebook How engineers improve them Android Client's

    The source of the original text is : Facebook    Source of translation :penkzhou    Welcome to share the original to Bole headlines As the world's largest social network ,Facebook Of Android Clients are faced with a variety of environments ( Geographical environment .Andro ...

  10. poj 3159

    Difference constraint And I forgot who said it , Anyway, I remember someone saying , Any difference constrained problem can be transformed into a graph At least that's what it looks like right now I started spfa+queue Overtime Read other people's blogs to know how to use spfa+stack, I feel like I.Q. has dropped by another one ...