JZTXT

【每日一题】Problem 476B. Dreamoon and WiFi

发布时间 2023-06-29 01:42:37作者: HelloEricy

原题

解决思路

数学

不管 recv 字符串如何，最终的结果一定满足以下条件：

  1. '+' 数量与 send 字符串相同
  2. '-' 数量与 send 字符串相同

因此，当 send 中的 '+' 多时，需要 '?' 满足；反之，'?' 需要补充 '-'
到此，将原问题转换成 组合问题

#include <bits/stdc++.h>

int cal(int n, int m) {
  if (n < m) {
    return -1;
  }

  int num, den; num = den = 1;
  for (int i = 1; i <= n - m; ++i) num *= i;
  for (int i = n; i > m; --i) den *= i;
  return den / num;
}

int main() {
  std::string send, recv;
  std::cin >> send >> recv;

  int oriPos, oriNeg, curPos, curNeg, miss;
  oriPos = oriNeg = curPos = curNeg = miss = 0;
  for (int i = 0; i < send.size(); ++i) {
    if (send[i] == '+') ++oriPos;
    else ++oriNeg;

    if (recv[i] == '+') ++curPos;
    else if (recv[i] == '?') ++miss;
    else ++curNeg;
  }

  int diff = 0;
  if (oriPos >= curPos) diff = oriPos - curPos;
  else diff = oriNeg - curNeg;

  double ans = 0;
  if (miss == 0 && diff == 0) ans = 1;
  else if (diff <= miss) ans = cal(miss, diff) / std::pow(2, miss);

  std::cout << std::setprecision(12) << ans << std::endl;
  return 0;
}
误区
  1. 需要确保小数点的位数足够
  2. 只有当前后的 '+' 和 '-' 都一样时，结果才是 100%，其他情况下结果不是 0 就是需要计算排列结果