首页 > 代码库 > hihocoder1489 Legendary Items (微软2017年预科生计划在线编程笔试)

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>=1)
    {
        right=0;
        double nextp;
        if(num>=7) nextp=0;
        else nextp=startp/(1<<(num+1));
        left=getsum(all+1,num+1,nextp,sum);
    }
    else if(p==0)
    {
        left=0;
        right=getsum(all+1,num,q,sum);
    }
    else
    {
        right=getsum(all+1,num,p+q,sum*(1-p));
        double nextp;
        if(num>=8) nextp=0;
        else nextp=startp/(1<<(num+1));
        left=getsum(all+1,num+1,nextp,sum*p);
    }
    return left +right;
}
int main()
{
    double res;
    scanf("%lf %lf %d",&startp,&q,&n);
    startp/=100;
    q/=100;
    res=getsum(0,0,startp,1);
    printf("%.2lf\n",res);
    return 0;
}

 

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

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

其实我们发现图中那两个标号 1 的节点子树是一样的,它们获取下一个物品的情况和期望都是一样的。我本来在考虑不同情况下拿到第一个,开始拿第二个,第二个和第一个是不是独立的?但是其实所有情况下拿到第一个的概率总和是1,所以无论 dfs 的哪一个分支,最后都会到同一个初始概率去获取第二个,所以获取第二个的期望与第一个是独立可加的。

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

2*50%*25% + 3*50%*75%*100% + 3*50%*100%*25% + 4*50%*100%*75%*100% = 3.25

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

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

那么期望的计算式可以写成Ei=Σpk?lk,其中pk表示做了lk个任务后拿到i个奖励的概率 
Pi表示?P2i?% 
接着考虑Ei+1=Σpk?lk 
=Pi+1?Σpk?(lk+1) 
+(1?Pi+1)?(Pi+1+Q%)?Σpk?(lk+2) 
+(1?Pi+1)?(1?Pi+1?Q%)?(Pi+1+2Q%)?Σpk?(lk+3)+... 
直到Pi+1+kQ%超过1结束 
于是用ci=Σpk 
Ei+1=Σpk?lk 
=Pi+1?(Ei+ci) 
+(1?Pi+1)?(Pi+1+Q%)?(Ei+2ci) 
+(1?Pi+1)?(1?Pi+1?Q%)?(Pi+1+2Q%)?(Ei+3ci)+... 

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

 

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

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

设C为一个常数,X和Y是两个随机变量。以下是数学期望的重要性质:
1.E(C)=C
2.E(CX)=CE(X)
3.E(X+Y)=E(X)+E(Y)
4.当X和Y相互独立时,E(XY)=E(X)E(Y)
性质3和性质4可以推到到任意有限个相互独立的随机变量之和或之积的情况。
上面是数学期望的性质,是可以直接相加的两个期望。所以这道题也不难理解了。
技术分享
这是数学期望期望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+5;
const int INF=0x3f3f3f3f;
double ans=0;
double num[105] = {0};
int n,p,q;

int main()
{
    scanf("%d%d%d",&p,&q,&n);
    for(int pre = 0 ; pre <= 100 ; ++ pre )
    {
        int cnt = 0;
        double p1 = 1;
        while(1)
        {
            double xq = ( pre + cnt * q) / 100.0;
            if( pre + cnt * q >= 100 )
            {
                num[pre] += ( cnt + 1 ) * p1 ;
                break;
            }
            num[pre] += p1 * xq * ( cnt + 1 );
            p1 *= ( 1 - xq );
            cnt++;
        }
    }

    int pre = p;
    for(int i = 1 ; i <= n ; ++ i )
    {
        if( pre == 0 )
        {
            ans += ( n - i + 1 ) * num[0];
            break;
        }
        ans += num[pre];
        pre >>= 1;
    }

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

 

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