郑州网站推广方案,seo快速排名外包,有的网站网速慢,网站管理程序题目链接#xff1a;HDOJ - 5159 这道题的做法太多了..BC的第二题也是可以非常水的.. 算法一 我在比赛的时候写的算法是这样的.. 预处理出所有的答案#xff0c;然后对于每个询问直接输出。 询问 (a, b) 记作 (a, b) 。 (a, b) 的答案是由 (a, b-1) 的答案推出的。 (a, 1) …题目链接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 algorithmusing 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 algorithmusing 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;
}转载于:https://www.cnblogs.com/JoeFan/p/4216705.html
