NC14734 比赛_牛客博客

题意

你在打比赛，这场比赛总共有12个题

对于第i个题，你的队伍有a[i]的几率解决她

如果解决不了她呢？

由于所有人讨论的都很大声

所以你有b[i]的概率从左边那个队那里听会这个题的做法

有c[i]的概率从右边那个队那里听会这个题的做法

请问最终你们队伍解出0-12题的概率分别是多少

分析

设 $p_i$ 表示第 $i$ 题过的概率。
那么做出恰好 $i$ 题（题号为 $b_1,b_2,...b_i$ ）的概率就为 $[\prod\limits_{i\in b}p_i][\prod\limits_{i \notin b}(1-p_i)]$ 。也就是枚举做出的题的集合即可。
那么怎么算出 $p_i$ 呢？

自己能做出来，概率为 $a_i$
自己做不出来，通过作弊做出来了，概率为 $(1-a_i)*p$ ， $p$ 为通过作弊做出来的概率，可以用 $1$ 减去不能通过作弊做出来的概率求出 $p$ ，即 $p=1-(1-b_i)(1-c_i)$

复杂度 $O(12*2^{12})$ = $O(1)$ （bushi

代码如下

#include <bits/stdc++.h>
double a[13], b[13], c[13], p[13], ans[13], t;
int main(){
    int i, j, n, m, cnt;
    for(i = 0; i < 12; i++) scanf("%lf", &a[i]);
    for(i = 0; i < 12; i++) scanf("%lf", &b[i]);
    for(i = 0; i < 12; i++) scanf("%lf", &c[i]);
    for(i = 0; i < 12; i++){
        t = 1 - (1 - b[i]) * (1 - c[i]);
        p[i] = a[i] + (1 - a[i]) * t;
    }
    for(i = 0; i < (1 << 12); i++){
        t = 1; cnt = 0;
        for(j = 0; j < 12; j++){
            if(1 << j & i) cnt++, t *= p[j];
            else t *= (1 - p[j]);
        }
        ans[cnt] += t;
    }
    for(i = 0; i <= 12; i++) printf("%.6lf\n", ans[i]);
    return 0;
}