C/C++知识点之实战-神奇口袋
从安 2019-06-05 来源 : 阅读 305 评论 0

摘要:本篇文章主要讲述C/C++知识点之实战-神奇口袋,希望阅读本篇文章以后大家有所收获,帮助大家对相关内容的理解更加深入。

本篇文章主要讲述C/C++知识点之实战-神奇口袋,希望阅读本篇文章以后大家有所收获,帮助大家对相关内容的理解更加深入。

C/C++知识点之实战-神奇口袋

题目#

一个口袋中先放有ai(1≤ai,1≤i≤t)ai(1≤ai,1≤i≤t)个ii颜色的球。若在第ii次从中取到的球色为CiCi,则要向口袋中放入dd个与之同色的求,取到的球也要放回。每个球被取到的几率相同。

先给出Q={(xn,yn)}Q={(xn,yn)},询问全部满足在第xixi次取球时取到颜色yiyi的几率。

结论#

假设当前QQ中的xx有序。

结论一: QQ中xx离散后对结果无影响#

证明:

设在第kk次取球时,颜色cc的数目为a[c]a[c],球的总数为tottot。可以得出:

在第kk次取到cc的几率为Pk=a[c]totPk=a[c]tot 。又因为

· 在第kk次取到cc且在第k+1k+1次也取到的几率为P1=a[c]tot×a[c]+dtot+dP1=a[c]tot×a[c]+dtot+d。

· 在第kk次没取到cc,但在第k+1k+1取到的几率为P2=tot−a[c]tot×a[c]tot+dP2=tot−a[c]tot×a[c]tot+d。

故在第k+1k+1次取到cc的几率为Pk+1=P1+P2=(tot+d)×a[c](tot+d)tot=a[c]totPk+1=P1+P2=(tot+d)×a[c](tot+d)tot=a[c]tot。

即Pk=Pk+1Pk=Pk+1。再经过简单归纳,即可证明结论一成立。

结论二: QQ中yy的出现顺序对结果无影响#

证明:

设在第ii次取球时,颜色cc的数目为a[c]a[c],球的总数为tottot。对于yi,yi+1(1≤i<n)yi,yi+1(1≤i<n),有

· 若yi=yi+1yi=yi+1,显然无影响

· 若yi≠yi+1yi≠yi+1,则

· 交换之前两组(x,y)(x,y)都成立的几率为P1=a[yi]tot×a[yi+1]tot+dP1=a[yi]tot×a[yi+1]tot+d。

· 交换之后两组(x,y)(x,y)都成立的几率为P2=a[yi+1]tot×a[yi]tot+dP2=a[yi+1]tot×a[yi]tot+d。

发现P1=P2P1=P2,即此时也无影响。同样的,略作归纳可知本结论成立。

算法#

由以上两个结论的得出xx的顺序无影响,yy的循序也无影响。故可以直接在读入QQ时对yy依次处理即可。

注意此题需要用到高精度、GCD。为了方便处理,可以对分子分母进行分解。最终将两个数的各个因子合起来。

实例#

Copy

#include using namespace std;const int N=1010;const int P=200000;struct BigInt {
    int s[P],ws;
    BigInt(){s[1]=1;ws=1;}
    void Multi(int x) {
        for(int i=1;i<=ws;++i)s[i]=s[i]*x;
        for(int i=1;i<=ws;++i)s[i+1]+=s[i]/10,s[i]%=10;
        while(s[ws+1])++ws,s[ws+1]=s[ws]/10,s[ws]%=10;
    }
    void output(){for(int i=ws;i;--i) printf("%d",s[i]);}
}U,D;int t,n,d,tot,a[N];int cntp,pri[P],num[P];bool notp[P]={1,1};void addon(int x,int w) {
    for(int i=1; x&&i<=cntp; ++i) {
        while(x%pri[i]==0) num[i]+=w, x/=pri[i];
    }
}int main() {
    for(int i=2; i<P; ++i) {
        if(!notp[i]) pri[++cntp]=i;
        for(int j=1; j<=cntp&&pri[j]*i<P; ++j) {
            notp[i*pri[j]]=1;
            if(i%pri[j]==0) break;
        }
    }
    scanf("%d%d%d",&t,&n,&d);
    for(int i=1; i<=t; ++i) {
        scanf("%d",&a[i]);
        tot+=a[i];
    }
    for(int i=1,x,y; i<=n; ++i) {
        scanf("%d%d",&x,&y);
        if(!a[y]) {puts("0/1"); return 0;}
        addon(a[y],1);
        addon(tot,-1);
        a[y]+=d, tot+=d;
    }
    for(int i=1; i0; --num[i]) U.Multi(pri[i]);
        for(; num[i]<0; ++num[i]) D.Multi(pri[i]);
    }
    U.output();
    putchar('/');
    D.output();
    return 0;
}

 

本文由职坐标整理发布,学习更多的相关知识,请关注职坐标IT知识库!

本文由 @从安 发布于职坐标。未经许可,禁止转载。
喜欢 | 0 不喜欢 | 0
看完这篇文章有何感觉?已经有0人表态,0%的人喜欢 快给朋友分享吧~
评论(0)
后参与评论

您输入的评论内容中包含违禁敏感词

我知道了

助您圆梦职场 匹配合适岗位
验证码手机号,获得海同独家IT培训资料
选择就业方向:
人工智能物联网
大数据开发/分析
人工智能Python
Java全栈开发
WEB前端+H5

请输入正确的手机号码

请输入正确的验证码

获取验证码

您今天的短信下发次数太多了,明天再试试吧!

提交

我们会在第一时间安排职业规划师联系您!

您也可以联系我们的职业规划师咨询:

小职老师的微信号:13167058313
小职老师的微信号:13167058313

版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com,All Rights Reserved.
 沪公网安备 31011502005948号    ICP许可  沪B2-20190160

站长统计