【NOIP2018模拟赛2018.8.28】 chance

题目

---

题解

–这道题是dp哟，是不是很隐秘
就是因为最后的答案是对k%及其以上的所有情况的概率求和
如果直接dfs肯定会爆
所以可以考虑dp
设f[i][j]：在前i个袋子里取出j个目标球的概率
转移很简单：
f[i][j+1]+=f[i-1][j]*p[i];
f[i][j]+=f[i-1][j]*(1-p[i]);
n^2时间复杂度

剩下的就是怎么快速求出每个袋子里取出目标球的概率了（p[i]）
直接L到R枚举是不可行的
我们可以发现对于L到R里，包含的整段目标球区间都是可以算出来的
比如：
1000~1999 共有1000个
10000~19999 共有10000个
所以我们可以设一个x（10^k），每次查询x和x*2是否在L到R内就行了
注意边界情况的处理就好了，很恶心的

---

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=2005;

int n,k;
long long l,r;
double p[MAXN];
double f[MAXN][MAXN];
double ans;

double hehe(long long l,long long r){
    long long fm=r-l+1;
    long long fz=0;
    long long x=1;
    while(x*2<=l){
        if(x<=l&&x*2>l)
            break;
        x*=10;
    }
    bool flag=0;
    if(x<=l&&x*2>l){
        if(x*2<r)
            fz+=x*2-l;
        else{
            flag=1;
            fz+=r-l;
            if(r<x*2)
                fz++;
        }
    }
    if(!flag){
        while(x*2<=r){
            if(x>l)
                fz+=x;
            x*=10;
        }
        if(x<=r&&x*2>r)
            fz+=r-x+1;
    }
    return (double)fz/fm;
}

int main(){
//  freopen("chance.in","r",stdin);
//  freopen("chance.out","w",stdout);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&l,&r);
        p[i]=hehe(l,r);
    }
    f[1][1]=p[1];
    f[1][0]=1-p[1];
    for(int i=2;i<=n;i++){
        for(int j=0;j<i;j++){
            f[i][j+1]+=f[i-1][j]*p[i];
            f[i][j]+=f[i-1][j]*(1-p[i]);
        }
    }
    int x=n*k/100;
    if(x<(double)n*k/100)
        x++;
    for(int i=x;i<=n;i++)
        ans+=f[n][i];
    printf("%.7lf",ans);
    return 0;
}