CodeForces 441 E.Valera and Number（概率DP）

60 阅读 0 评论 40 点赞

我是靠谱客的博主怕孤单大侠，最近开发中收集的这篇文章主要介绍CodeForces 441 E.Valera and Number（概率DP），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Description
//input: integers x, k, p
a = x;
for(step = 1; step <= k; step = step + 1){
rnd = [random integer from 1 to 100];
if(rnd <= p)
a = a * 2;
else
a = a + 1;
}

s = 0;

while(remainder after dividing a by 2 equals 0){
a = a / 2;
s = s + 1;
}
给出x,k,p，问s的期望值
Input
输入三个整数x,k,p(1<=x<=1e9,1<=k<=200,0<=p<=100)
Output
输出s的期望值，相对误差和绝对误差均不能超过1e-6
Sample Input
1 1 50
Sample Output
1.0000000000000
Solution
dp[i][j][k][l]表示第i步，a的二进制表示后八位是j，第九位是k，从第九位开始连续的和第九位相同的数的个数为l的概率
第i轮，a有p的概率乘2，有q=1-p的概率加1
一：乘2：
1.j的第八位是1，若第九位是1，那么乘2后从第九位还是1，连续相同的数的个数就变成k+1；若第九位是0，那么乘2后第九位变成1，连续相同的数的个数就是1
2.j的第八位是0，若第九位是1，那么乘2后第九位变成0，连续相同的数的个数就是1；若第九位是0，那么乘2后第九位还是0，连续相同的数的个数就变成k+1
二：加1
1.j是255，那么加1之后会进位，如果第九位是1，那么进位后第九位变成0，连续相同的数的个数变成1；如果第九位是0，那么进位后第九位变成1，连续相同的数的个数也变成1
2.j小于255，那么加1之后不会影响第九位的值和从第九位开始连续相同的数的个数
在知道了所有dp值之后，只需要统计每种状态的二进制表示后连续0的个数即可，能够用到第九位及之后的0必须前八位都是0，所以dp[K][0][0][k]状态对答案贡献就是8+k，dp[K][0][1][k]状态对答案贡献就是8，而对于其他的状态，后八位不是0，介于1~255之间，设为i，暴力求出i二进制表示后面连续1的个数cnt即为该状态对答案的贡献
Code

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<ctime>
using namespace std;
double dp[222][256][2][255],p,q;
int X,K; 
int main()
{
    while(~scanf("%d%d%lf",&X,&K,&p))
    {
        p/=100.0;
        q=1.0-p;
        int a[33],res=0,n=X%256;
        while(X)a[res++]=X%2,X/=2;
        memset(dp,0,sizeof(dp));
        if(res<9)dp[0][n][0][0]=1;
        else
        {
            int cnt=1;
            for(int i=9;i<res;i++)
                if(a[i]==a[i-1])cnt++;
                else break;
            dp[0][n][a[8]][cnt]=1;
        }
        for(int i=0;i<K;i++)
            for(int j=0;j<=255;j++)
                for(int k=0;k<=240;k++)
                {
                    if(j&128)
                    {
                        dp[i+1][(j<<1)%256][1][1]+=dp[i][j][0][k]*p;
                        dp[i+1][(j<<1)%256][1][k+1]+=dp[i][j][1][k]*p;
                    }
                    else
                    {
                        dp[i+1][(j<<1)%256][0][k+1]+=dp[i][j][0][k]*p;
                        dp[i+1][(j<<1)%256][0][1]+=dp[i][j][1][k]*p;
                    }
                    if(j==255)
                    {
                        dp[i+1][0][1][1]+=dp[i][j][0][k]*q;
                        dp[i+1][0][0][k]+=dp[i][j][1][k]*q;
                    }
                    else 
                    {
                        dp[i+1][j+1][0][k]+=dp[i][j][0][k]*q;
                        dp[i+1][j+1][1][k]+=dp[i][j][1][k]*q;
                    }
                }
        double ans=0;
        for(int k=0;k<=240;k++)ans+=dp[K][0][0][k]*(8+k)+dp[K][0][1][k]*8;
        for(int i=1;i<=255;i++)
        {
            int temp=i,cnt=0;
            while(temp%2==0)cnt++,temp/=2;
            for(int j=0;j<2;j++)
                for(int k=0;k<=240;k++)
                    ans+=dp[K][i][j][k]*cnt;
        }
        printf("%.10fn",ans);
    }
    return 0;
}