NC14734 比赛

题目地址：

https://ac.nowcoder.com/acm/problem/14734

基本思路：

这道题的思路比较明了，我们先通过题目说的三种情况算出每道题的真正通过率： $AC[i] = 1 - (1 - a[i]) * (1 - b[i]) * (1 - c[i])$ ；然后我们可以使用 $dfs$ $/$ 状态枚举 $/$ $dp$ 等方法计算出答案，但是我们发现因为每道题只有对错两种可能，而且只有12题，所以我们直接状压枚举出所有可能状态，然后对于每个状态里正确题目的数量分别统计答案就是了。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define ll long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int maxn = 50;
double a[maxn],b[maxn],c[maxn];
double AC[maxn],ans[maxn];
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++){
    AC[i] = 1.0 - (1.0 - a[i]) * (1.0 - b[i]) * (1.0 - c[i]);//实际的正确率;
  }
  for(int i = 0 ; i < (1 << 12) ; i++){//状态枚举;
    double res = 1.0; int cnt = 0;//cnt记录正确题目数;
    for(int j = 0 ; j < 12 ; j++) {
      if ((i >> j) & 1) { res *= AC[j]; cnt++; }
      else res *= (1.0 - AC[j]);
    }
    ans[cnt] += res;
  }
  for(int i = 0 ; i <= 12 ; i++) printf("%.6lf ",ans[i]);
  puts("");
  return 0;
}