欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【NOIP2018模拟赛2018.8.28】 chance

程序员文章站 2024-02-11 13:20:10
...

题目

【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;
}
相关标签: 刷题之路