【每日一题】比赛 题解

Description

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

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

如果解决不了她呢？

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

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

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

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

Solution1

首先我们可以计算出每道题做不出来的概率
然后因为只有 12 道题, 每道题要么做对要么做错, 我们可以做
当前做对的题数小于 的时候, 我们可以往对和不对的方向搜索
如果做对的题数等于 , 那么我们只能往不对的方向搜索

Code1

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 105 + 5;

double a[N], b[N], c[N];
double unsolve[N];
double ans;
void dfs(int pos, int now, int need, double p) {
  if(pos == 13) {
    if(now == need) {
      ans += p;
    }
    return ;
  }
  if(now < need) {
    dfs(pos + 1, now + 1, need, p * (1 - unsolve[pos]));
  }
  dfs(pos + 1, now, need, p * unsolve[pos]);
}
int main() {
  for(int i = 1; i <= 12; i++) cin >> a[i];
  for(int i = 1; i <= 12; i++) cin >> b[i];
  for(int i = 1; i <= 12; i++) cin >> c[i];
  for(int i = 1; i <= 12; i++) {
    unsolve[i] = (1 - a[i]) * (1 - b[i]) * (1 - c[i]);
  }
  for(int i = 1; i <= 13; i++) {
    ans = 0;
    dfs(1, 0, i - 1, 1);
    cout << fixed << setprecision(6) << ans << "\n";
  }
  return 0;
}

Solution2

这道题还可以用概率 来做
令 表示做到第 道题的时候做对 道的状态
显然有
注意初始化

Code2

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 105 + 5;

double a[N], b[N], c[N];
double unsolve[N];
double dp[15][15];
int main() {
  for(int i = 1; i <= 12; i++) cin >> a[i];
  for(int i = 1; i <= 12; i++) cin >> b[i];
  for(int i = 1; i <= 12; i++) cin >> c[i];
  for(int i = 1; i <= 12; i++) {
    unsolve[i] = (1 - a[i]) * (1 - b[i]) * (1 - c[i]);
  }
  dp[0][0] = 1;
  for(int i = 1; i <= 12; i++) {
    dp[i][0] = dp[i - 1][0] * unsolve[i];
    for(int j = 1; j <= i; j++) {
      dp[i][j] = dp[i - 1][j] * unsolve[i] + dp[i - 1][j - 1] * (1 - unsolve[i]);
    }
  }
  for(int i = 0; i <= 12; i++) {
    cout << fixed << setprecision(6) << dp[12][i] << "\n";
  }
  return 0;
}