HDU 4336 Card Collector 做题笔记

题意

有 $n$ 种卡片，每次购买有 $p_i$ 的概率买到第 $i$ 种，求使得每种都买到的期望购买次数。

$1 \leq n \leq 20$

题解

考虑 Min - Max 容斥。
此时，$\displaystyle E\left(\min\left(S\right)\right) = \frac1{\sum\limits_{i \in S} p_i}$。
因为，买卡正好买到集合 $S$ 中的概率就是 $\displaystyle \sum\limits_{i \in S} p_i$，而期望次数就是它的倒数。

直接套用 Min - Max 容斥公式即可。
$$E\left(\max\left(S\right)\right) = \sum\limits_{T \subseteq S, T \neq \emptyset} \left(-1\right)^{\left\lvert T \right\rvert - 1} E\left(\min\left(T\right)\right)$$

代码

// Please submit with C++17! It's best to use C++20 or higher version.
// By Koicy (https://koicy.ly)
// rbtree (i@koicy.ly)
// This is my kingdom code.

// #define EFILE ""
#include <algorithm>
#include <array>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <utility>
#include <vector>
#define _CONSOLE 0

using namespace std;
using tp = long long;
constexpr tp ZERO = 0, ONE = 1, INF32 = -1u >> 2, INF = -1ull >> 2;

// :/

void MIST() {
}

double tar;
tp n;
vector<double> p;

void STRUGGLING([[maybe_unused]] tp TEST_NUMBER) {
  while (cin >> n) {
    tar = 0;
    p.resize(n);
    for (tp i = 0; i < n; ++i) cin >> p[i];
    for (tp i = 1, ei = 1ll << n; i < ei; ++i) {
      double sum = 0;
      tp cnt = 0;
      for (tp j = 0; j < n; ++j) {
        if (i >> j & 1) { ++cnt; sum += p[j]; }
      }
      if (cnt % 2 == 0) sum *= -1;
      tar += 1 / sum;
    }
    cout << fixed << setprecision(6) << tar << '\n';
  }
}

#include <fstream>

signed main() {
  tp t = 0, _t = 1;
  cin.tie(0)->sync_with_stdio(0);
#if !_CONSOLE
#ifdef _LOCAL
  static ifstream _in("input.txt");
  cin.rdbuf(_in.rdbuf());
#else
#ifdef EFILE
  static ifstream _in(EFILE ".in");
  static ofstream _out(EFILE ".out");
  cin.rdbuf(_in.rdbuf());
  cout.rdbuf(_out.rdbuf());
#endif
#endif
#endif
  // cin >> _t;
  MIST();
  while (t < _t) STRUGGLING(++t);
  return 0;
}

//*/

---

• 分类： 做题笔记
• 最后更新于：2024-02-01 10:38:12^UTC+8
• 标签： Min - Max 容斥