题解 SP1026 【FAVDICE - Favorite Dice】

# $\mathcal{Description}$ 一个$n$面的骰子，求期望掷几次能使得每一面都被掷到 输入有$T$组数据，每次输入一个$n$ 输出保留两位小数 # $\mathcal{Solution}$ 设$f[i]$表示已经掷到过$i$面，__还__ 期望掷多少次骰子使每一面都被掷到 现在掷一次骰子，有两种情况 1. 有$\frac{i}{n}$的概率掷到已经掷到过的面，此时仍然还要掷$f[i]$次骰子 2. 有$\frac{n-i}{n}$的概率掷到没掷到过的面，此后就掷到过$i+1$个面了，还需掷$f[i+1]$次骰子 需要注意的是，无论是掷到以上哪种情况，都需要掷一次骰子 所以有 $f[i]=\frac{i}{n}f[i]+\frac{n-i}{n}f[i+1]+1$ 将其化简 $f[i]=f[i+1]+\frac{n}{n-i}$ # $\mathcal{Code}$ ```cpp /******************************* Author:Morning_Glory LANG:C++ Created Time:2019年07月21日 星期日 14时51分18秒 *******************************/ #include <cstdio> #include <fstream> using namespace std; const int maxn = 1005; //{{{cin struct IO{ template<typename T> IO & operator>>(T&res){ res=0; bool flag=false; char ch; while((ch=getchar())>'9'||ch<'0') flag|=ch=='-'; while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^'0'),ch=getchar(); if (flag) res=~res+1; return *this; } }cin; //}}} int T,n; double f[maxn];//f[i] -> 有了i个面，变成拥有n个面的期望 int main() { freopen("p1026.in","r",stdin); freopen("p1026.out","w",stdout); cin>>T; while (T--){ cin>>n; f[n]=0; for (int i=n-1;i>=0;--i) f[i]=f[i+1]+1.0*n/(n-i); printf("%.2lf\n",f[0]); } return 0; } ```