题目链接：HDOJ - 5159
这道题的做法太多了..BC的第二题也是可以非常水的..
算法一
我在比赛的时候写的算法是这样的..
预处理出所有的答案，然后对于每个询问直接输出。
询问 (a, b) 记作 (a, b) 。
(a, b) 的答案是由 (a, b-1) 的答案推出的。
(a, 1) 的答案是 1 到 a 的平均数，着十分显然。
如果 b > 1 ，那么我们就考虑在第 b 次，我们抽到每种牌的概率都是 1/a ，然后这张牌之前 b-1 次没被抽到的概率为 ((a-1)/a)^(b-1) ，那么第 b 次新获得的期望得分就是
Sum(1~a) * ((a-1)/a)^(b-1) * (1/a) 。然后这个值加上 (a, b-1) 的答案就是 (a, b) 的答案了。
【代码】
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm> using namespace std; typedef double DB; const int MaxN = 100000 + 5, MaxM = 5 + 2; DB Ans[MaxN][MaxM]; int main()
{
int T, a, b;
scanf("%d", &T);
DB t;
for (int i = 1; i <= 100000; ++i) {
for (int j = 1; j <= 5; ++j) {
if (j == 1) {
Ans[i][j] = (DB)(1 + i) / 2.0;
t = (DB)(i - 1) / (DB)i;
continue;
}
Ans[i][j] = Ans[i][j - 1] + (DB)(1 + i) / 2.0 * t;
if (j == 5) continue;
t *= (DB)(i - 1) / (DB)i;
}
}
for (int Case = 1; Case <= T; ++Case) {
scanf("%d%d", &a, &b);
printf("Case #%d: %.3lf\n", Case, Ans[a][b]);
}
return 0;
}
算法二
这种算法是对于 (a, b) 直接求，写起来简单多了。
我们考虑每一张牌，它在 b 次之内如果被抽到了，得分就会加上它的值，那么它在 b 次之内有多大概率被抽到呢？
这个不好直接算，我们就考虑，b 次之内都没有被抽到的概率有多大呢？这个显然就是 ((a-1)/a)^(b) 。那么 b 次之内抽到它的概率就是 1 - ((a-1)/a)^b ，这个概率乘它的值就是这张牌对期望得分的贡献。
那么答案就是 Sum(1~a) * (1 - ((a-1)/a)^b) 。
【代码】
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm> using namespace std; typedef double DB; const int MaxN = 100000 + 5, MaxM = 5 + 2; DB Ans[MaxN][MaxM]; DB Solve(int a, int b) {
DB t = 1;
for (int i = 1; i <= b; ++i) t *= (DB)(a - 1) / a;
t = 1 - t;
return (DB)(1 + a) * (DB)a / 2.0 * t;
} int main()
{
int T, a, b;
scanf("%d", &T);
for (int Case = 1; Case <= T; ++Case) {
scanf("%d%d", &a, &b);
printf("Case #%d: %.3lf\n", Case, Solve(a, b));
}
return 0;
}