SP1026 FAVDICE - Favorite Dice 题解
题意:
多组询问。
一个 \(n(1\le n \le 1000)\) 面的骰子,求期望掷几次能使得每一面都被掷到。
前置知识:一件事有 \(\frac{1}{p}\) 的概率完成,则期望要做 \(p\) 次。
那么这题就很简单了。设 \(f_i\) 表示扔出 \(i\) 个点数的期望步数,则 \[ f_i = f_{i-1} + \frac{n}{n-(i-1)} \] 后面那个就是 \(i-1\) 个点数的时候有 \(\frac{n-(i-1)}{n}\) 的概率扔出其他的点数,所以期望就是倒数。
时间复杂度 \(\mathcal{O}(n)\)
代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())
void solve()
{
int n; cin >> n; double r = 0;
for(int i = 1; i <= n; i++) r += (double)n / (n - (i - 1));
cout << r << '\n';
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cout << fixed << setprecision(2);
int qwq; cin >> qwq; while(qwq--) solve();
return 0;
}
题外话:
好耶,这次居然 20 分钟就做出来了。