比赛
比赛
https://ac.nowcoder.com/acm/problem/14734
题解:
我以为求每个题目的通过概率.....
果断看错题
这个很多种做法,写一种最笨的做法,枚举
比如17=000000010001
嗯,然后就是0表示做不出来,1表示能做出来,相当于要枚举 个数,挺小的........
然后对于每个枚举数里面出现的1的个数求一下数量,就是这种情况下过题的数量,再把这个枚举数求出来的概率加到相应的过题的那个概率上
#include<bits/stdc++.h> using namespace std; double a[13],b[13],c[13],d[13],e[13],res[13]; signed main() { for(int i=0; i<12; i++) cin>>a[i]; for(int i=0; i<12; i++) cin>>b[i]; for(int i=0; i<12; i++) cin>>c[i]; for(int i=0; i<12; i++) d[i]=(1-(1-a[i])*(1-b[i])*(1-c[i])), e[i]=(1-a[i])*(1-b[i])*(1-c[i]); for(int i=0; i<(1<<12); i++) { int cnt=0; double t=1; for(int j = 0; j < 12; j++) { if((1<<j) & i) { cnt++; t *= d[j]; } else { t *= e[j]; } } res[cnt] += t; } for(int i = 0; i <= 12; i++) printf("%.6f\n",res[i]); }
然后还可以dp
对于每一个问题可以由前一个状态得到
比如前i个问题要解决j个,那么状态转移有以下情况
对于第i个问题如果解决那么就乘以前i-1个问题要解决j-1个的值
对于第i个问题如果没有解决那么就乘以前i-1个问题要解决j个的值
然后就是两层循环.....
注意开头取值
#include <cstdio> #include <cstring> using namespace std; double a[14],r[14],l[14],p[14],dp[15][15]; int main() { for(int i=1;i<=12;i++) scanf("%lf",&a[i]); for(int i=1;i<=12;i++) scanf("%lf",&l[i]); for(int i=1;i<=12;i++) scanf("%lf",&r[i]); p[0]=0; for(int i=1;i<=12;i++) p[i]=a[i]+(1-a[i])*(r[i]+l[i]-r[i]*l[i]); dp[0][0]=1,dp[0][1]=0; for(int i=1;i<=12;i++) for(int k=0;k<=i;k++) { if(k==0) dp[i][0]=dp[i-1][0]*(1-p[i]); else dp[i][k]=dp[i-1][k-1]*p[i]+dp[i-1][k]*(1-p[i]); } for(int i=0;i<=12;i++) printf("%.6f\n",dp[12][i]); } //code:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=20452021