神乎其技

UnyieldingTrilobite · 2023-02-01 22:29:14 · 题解

非常美丽的一道题，奇诡且简洁。

我们考虑给每个想法都赋上一个权值，然后通过简单 dp 计算出每个题目所能包含到的想法的权值的最小值（也称作这个题目的权值）。如此一来，我们发现，假设一个题目包含的想法总数是 x，那么最后它的权值就是这 x 个想法的权值的最小值。注意到，如果想法的权值是在某一个区间上均匀随机的，那么根据期望的基本知识，这个题目最后权值的期望将会落在这个区间最左的 x+1 分点上。如此一来，我们根据大数定律，以频率代替概率计算出一个大致的期望，观察它的位置即可得到 x。由于有足足四分之一的容错，口胡一下还是问题不大的。

代码巨大好写。

#include <bits/stdc++.h>
#define int long long
using namespace std;
using namespace views;
constexpr int T = 150;
signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  vector<tuple<int, int, int, int>> es(n);
  for (auto& [w, u, v, s] : es | drop(m)) cin >> u >> v, --u, --v, s = 0;
  default_random_engine rnd(random_device{}());
  for (int t = T; t; --t) {
    for (auto& [w, u, v, s] : es | take(m)) w = rnd();
    for (auto& [w, u, v, s] : es | drop(m))
      s += w = min(get<0>(es[u]), get<0>(es[v]));
  }
  for (auto& [w, u, v, s] : es | drop(m))
    cout << fixed << setprecision(0) << rnd.max() * T * 1. / s - 1 << '\n';
  return cout << flush, 0;
}