CodeForces 54C-First Digit Law(数位,概率dp)

题意:

给你n个区间,在每个区间里各取一个数(随机取),求这n个数中超过K%的数是首位为1数的概率

分析:

dp[i][j]取前i个数,有j个是首位为1的数的概率

易知,dp[i][j]=dp[i-1][j]*(1-p[i])+dp[i-1][j-1]*p[i];

现在关键是求p[i],第i个区间首位为1的数出现的概率,用数位统计一下即可

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <complex>
#include <cassert>
#include <utility>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
#define lson l,m,rt<<1
#define pi acos(-1.0)
#define rson m+1,r,rt<<11
#define All 1,N,1
#define read freopen("in.txt", "r", stdin)
const ll  INFll = 0x3f3f3f3f3f3f3f3fLL;
const int INF= 0x7ffffff;
const int mod =  1000000007;
ll sum[20],a[20];
double dp[1010][1010],p[1010];
int bit[20],n,k;
void init(){
    sum[0]=1;
    for(int i=1;i<=20;++i)
        sum[i]=sum[i-1]*10;
}
ll countsum(int l){
    ll total=0;
    for(int i=0;i<=l;++i)
        total+=sum[i];
    return total;
}
//统计首位为1数的数量
ll countone(ll x){
    if(x==0)return 0;
    init();
    int len=0;
    while(x){
        bit[++len]=x%10;
        x/=10;
    }
    if(bit[len]>1){
        return countsum(len-1);
    }
    else{
        ll tmp=countsum(len-2);
        a[0]=0;
    for(int i=1;i<=len-1;++i)
        a[i]=a[i-1]+bit[i]*sum[i-1];
        tmp+=a[len-1]+1;
        return tmp;
    }
}
int main()
{
    ll l,r;
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;++i){
            scanf("%I64d%I64d",&l,&r);
            ll tmp=countone(r)-countone(l-1);
            //cout<<tmp<<endl;
            p[i]=1.0*tmp/(r-l+1);
            //cout<<p[i]<<endl;
        }
        dp[1][1]=p[1];
        dp[1][0]=1.0-p[1];
        for(int i=2;i<=n;++i)
        for(int j=0;j<=i;++j){
            dp[i][j]+=dp[i-1][j]*(1.0-p[i]);
            if(j>0)
            dp[i][j]+=dp[i-1][j-1]*p[i];
        }
        scanf("%d",&k);
        double ans=0.0;
        for(int j=0;j<=n;++j)
            if(j>=(1.0*n*k/100))
                ans+=dp[n][j];
        printf("%.15lf\n",ans);
    }
return 0;
}
时间: 08-16

CodeForces 54C-First Digit Law(数位,概率dp)的相关文章

Codeforces Div.301D Bad Luck Island(概率dp+记忆化搜索)

一道概率dp问题. 题目链接:http://codeforces.com/contest/540/problem/D 题目大意:一个岛上有r个石头,s个剪子,p个布,他们之间随机挑出两个相遇,如果不是相同物种,就会有一个消失,分别求出最后这座岛上只剩下一个物种的概率. 我们用dp[i][j][k]来存储i个石头,j个剪刀,k个布时,某物种的存活概率,共dp三次,算出三个物种分别的概率. 首先,我们需要把对应想求的物种概率初始化,这里以石头为例,那么对于i从1到r,不难理解dp[i][0][0]=

Codeforces 148D Bag of mice:概率dp 记忆化搜索

题目链接:http://codeforces.com/problemset/problem/148/D 题意: 一个袋子中有w只白老鼠,b只黑老鼠. 公主和龙轮流从袋子里随机抓一只老鼠出来,不放回,公主先拿. 公主每次抓一只出来.龙每次在抓一只出来之后,会随机有一只老鼠跳出来(被龙吓的了...). 先抓到白老鼠的人赢.若两人最后都没有抓到白老鼠,则龙赢. 问你公主赢的概率. 题解: 表示状态: dp[i][j] = probability to win(当前公主先手,公主赢的概率) i:剩i只白

codeforces 167B Wizards and Huge Prize 概率dp

题意:给定n个对手,至少要击败其中 l 个人,现在有口袋容量为 k下面n个数字表示击败这个人的概率 下面n个数字(若为-1表示击败这个人可以获得一个金币,若>0则表示可以增加口袋容量为这个数字) 求:至少击败其中的l个人,且获得的总口袋容量 >= 获得的金币个数 的概率是多少.(即任何时候金币都不能放不下) 思路:设dp[i][j][k]表示当前前i个人已经战胜j个人,且剩余口袋容量为k的概率,简单的推下公式即可.有一点需要主要,可能一开始 剩余口袋容量<0后来大于0,所以要加一个常数不

Codeforces Round #105 (Div. 2) D 概率DP

题目 呃 琢磨了半天还是琢磨出来了,题意有些模糊哈,有w个白色物品,b个黑色物品,A,B轮着抽,A先开始,谁先抽到白色谁赢,若最终都没有抽到白色 则算B赢,抽出来的物品不会放回去,B抽完以后 物品还会有一个额外产生丢失,问A赢的概率为多少 依旧是以目标状态为边界,当前状态到目标状态所需要的概率为 方程 dp[i][j] 代表当前轮到A抽的时候,还有i个白色的j个黑色的A赢的概率为多少 则当前转移可能有四种 1:A抽到了白色的,那么直接赢了,接下来不需要继续,所以没有与其它状态方程有联系 2:A抽

CodeForces 540D Bad Luck Island 概率dp

CodeForces 540D 应该是简单概率dp,由于写得少显得十分蠢萌 求期望逆推,求概率正推,大概是这么个意思,贴一发留恋 #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define db double const int maxn=108; db dp[maxn][maxn][maxn]; int main() { int i,j,n,m,k,p; whi

Codeforces 148D Bag of mice (概率dp)

D. Bag of mice time limit per test:2 seconds memory limit per test:256 megabytes The dragon and the princess are arguing about what to do on the New Year's Eve. The dragon suggests flying to the mountains to watch fairies dancing in the moonlight, wh

Codeforces 518D Ilya and Escalator (概率dp)

Ilya and Escalator time limit per test: 2 seconds memory limit per test: 256 megabytes Ilya got tired of sports programming, left university and got a job in the subway. He was given the task to determine the escalator load factor. Let's assume that

Codeforces 28C [概率DP]

/* 大连热身D题 题意: 有n个人,m个浴室每个浴室有ai个喷头,每个人等概率得选择一个浴室. 每个浴室的人都在喷头前边排队,而且每个浴室内保证大家都尽可能均匀得在喷头后边排队. 求所有浴室中最长队伍的期望. 思路: 概率dp dp[i][j][k]代表前i个浴室有j个人最长队伍是k的概率. 枚举第i个浴室的人数.然后转移的时候其实是一个二项分布. */ #include<bits/stdc++.h> using namespace std; int jilu[55]; double dp[

POJ1644:To Bet or Not To Bet(概率DP)

Description Alexander Charles McMillan loves to gamble, and during his last trip to the casino he ran across a new game. It is played on a linear sequence of squares as shown below. A chip is initially placed on the Start square. The player then trie

CF 148D. Bag of mice[概率dp]

题目链接:http://codeforces.com/problemset/problem/148/D 题目大意:一袋子里有w个白老鼠,b个黑老鼠:A和B轮流抓老鼠(不放回),谁先抓到白老鼠,谁win:因为B粗鲁,每次抓完一只老鼠,会跑出来一只:A first: 求A win的概率: 题目分析: 此类概率dp的状态比较固定,dp(i , j )表示当前状态Awin的概率: 1:  dp[i][0],A win的概率为 1:dp[0][j] 概率为 0: 2:  dp[i][j]     如下四种