題目鏈接：HDOJ - 5159

?

這道題的做法太多了..BC的第二題也是可以非常水的..

?

算法一

我在比賽的時(shí)候?qū)懙乃惴ㄊ沁@樣的..

預(yù)處理出所有的答案，然后對(duì)于每個(gè)詢問直接輸出。

詢問 (a, b) 記作 (a, b) 。

(a, b) 的答案是由 (a, b-1) ?的答案推出的。?

(a, 1) 的答案是 1 到 a 的平均數(shù)，著十分顯然。

如果 b > 1 ，那么我們就考慮在第 b 次，我們抽到每種牌的概率都是 1/a ，然后這張牌之前 b-1 次沒被抽到的概率為 ((a-1)/a)^(b-1) ，那么第 b 次新獲得的期望得分就是

Sum(1~a) * ((a-1)/a)^(b-1) * (1/a) 。然后這個(gè)值加上 (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; }

?

算法二

這種算法是對(duì)于 (a, b) 直接求，寫起來簡(jiǎn)單多了。

我們考慮每一張牌，它在 b 次之內(nèi)如果被抽到了，得分就會(huì)加上它的值，那么它在 b 次之內(nèi)有多大概率被抽到呢？

這個(gè)不好直接算，我們就考慮，b 次之內(nèi)都沒有被抽到的概率有多大呢？這個(gè)顯然就是 ((a-1)/a)^(b) 。那么 b 次之內(nèi)抽到它的概率就是 1 - ((a-1)/a)^b ，這個(gè)概率乘它的值就是這張牌對(duì)期望得分的貢獻(xiàn)。

那么答案就是 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; }

　　

?

轉(zhuǎn)載于:https://www.cnblogs.com/JoeFan/p/4216705.html

總結(jié)

以上是生活随笔為你收集整理的[BC Round#26] Card 【各种水】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。