hihocoder1489 Legendary Items （微软2017年预科生计划在线编程笔试）

http://hihocoder.com/problemset/problem/1489

---

笔试题第一道，虽然说第一道都很水，但是我感觉这题不算特别水把。。这道题我就卡住了我记得，tle，最后只有30分，比较惨烈。我个人感觉这道题正解比较难想把，那时候太年轻，没有想到当item很大时，可以从第八道item开始就把初始p当成0来计算。。不过我试了一下，发现即使如此，还要计算每次的数学期望，反正我当时要是不知道，Ei和Ei+1之间的联系，应该还是算不出来。。我太麻瓜了。。

贴一下我tle代码，思路就是dfs这个概率树。。非常完美可惜不行。

#include <iostream>

#include<cstdio>

#include<cstring>

#include<string.h>

#include<algorithm>

#include<cmath>

using namespace std;

double startp,q;

int n;

double getsum(int all,int num,double p,double sum)

{

    double left,right;

    if(num==n) return sum*all;

    if(p>=)

    {

        right=;

        double nextp;

        if(num>=) nextp=;

        else nextp=startp/(<<(num+));

        left=getsum(all+,num+,nextp,sum);

    }

    else if(p==)

    {

        left=;

        right=getsum(all+,num,q,sum);

    }

    else

    {

        right=getsum(all+,num,p+q,sum*(-p));

        double nextp;

        if(num>=) nextp=;

        else nextp=startp/(<<(num+));

        left=getsum(all+,num+,nextp,sum*p);

    }

    return left +right;

}

int main()

{

    double res;

    scanf("%lf %lf %d",&startp,&q,&n);

    startp/=;

    q/=;

    res=getsum(,,startp,);

    printf("%.2lf\n",res);

    return ;

}

这题很关键的一点的就是，就是不同个数的期望是可以相加的。这个地方我一直很不明白，非常困惑，哇，要是我知道是这样，就直接相加了啊，谁还写dfs啊。。

http://www.mamicode.com/info-detail-1759090.html这个我看了这个博主给的解释：

我比较愚钝，还是不能非常理解。。相互独立的话，可是题意中给的式子是

意思是每个都是和做掉的任务个数是相关的，并且是累加的。。就是完成了1件传说后，已经完成了2个任务，然后下次就要从3开始算，并且概率还要相乘。。算的话看起来好像不是直接相加就好了。。当然博主说的很好也是对的。。只是我乍一看并不是非常理解。。

http://blog.csdn.net/sddyzjh/article/details/68950610还有这个博主，

直接用算的，求出Ei+1和Ei的关系，答案就很明显了。看了式子之后，发觉写的很好，很容易理解。应该可以根据这个规律直接code，博主给的代码也蛮好理解的。

其实有一个很明显的地方值得注意。其实我们可以发现Ei=Σpk∗lk跟概率论的数学期望很相似啊。这道题其实就是让我们求数学期望，我之前一直不知道在想什么，把绕来绕去。。我们可以发现Ei是绝对收敛的呀。要是k无限大，就是完成的任务无限多的时候，概率是趋于1的呀讲道理啊，就是完成任务无限多，不是肯定要完成传说任务的。

数学期望其实就是一个加权平均意思，这道题中的意思就是当给定了n，即要完成n个传说任务，加权平均一下，数学期望在这里表示的就是要完成平均多少个任务才能完成n个传说任务。数学期望在物理上就是一堆质点的重心，也就是加权平均。两个铁块已知重心的话，把他们重叠起来，在坐标轴上新的重心不就是两个重心的中点嘛，所以是可以直接相加的。

上面是数学期望的性质，是可以直接相加的两个期望。所以这道题也不难理解了。

这是数学期望期望E(X+Y)=E(X)+E(Y) 就是这道题的精髓，很特别，我开始不知道这个，就被dfs套牢了。。唉。悲伤的故事。。 数学果然是算法的灵魂。。好好学习。。天天向上。。

贴一下别人ac代码。。

#include<stdio.h>

#include<string.h>

#include<math.h>

#include<algorithm>

using namespace std;

const int maxn=1e6+;

const int INF=0x3f3f3f3f;

double ans=;

double num[] = {};

int n,p,q;

int main()

{

    scanf("%d%d%d",&p,&q,&n);

    for(int pre =  ; pre <=  ; ++ pre )

    {

        int cnt = ;

        double p1 = ;

        while()

        {

            double xq = ( pre + cnt * q) / 100.0;

            if( pre + cnt * q >=  )

            {

                num[pre] += ( cnt +  ) * p1 ;

                break;

            }

            num[pre] += p1 * xq * ( cnt +  );

            p1 *= (  - xq );

            cnt++;

        }

    }

    int pre = p;

    for(int i =  ; i <= n ; ++ i )

    {

        if( pre ==  )

        {

            ans += ( n - i +  ) * num[];

            break;

        }

        ans += num[pre];

        pre >>= ;

    }

    printf("%.2lf\n",ans);

    return ;

}