[kuangbin带你飞]专题二十一 概率&期望

A Dangerous Maze

B - Discovering Gold

给你一个数N,代表有N个点,每个点上有一定数量的黄金,你有一个6面的骰子,投到x就走x步,如果超过了N,就再投一次,让你求获得黄金数量的期望值。

题解:

我们可以算出来走每个位置的概率,用这个位置的价值乘以概率,加起来就是期望了。对于一每个点,都可以从在他前面和它的距离<= 6的点转移过来,但是要考虑到,最后面几个点在转移的时候不是乘1/6。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <algorithm>
#include <string.h>
#include <stdio.h>
using namespace std;
#define ll long long

int main(int argc, char const *argv[])
{
int T, n;
double p[105];
int a[105];

scanf("%d", &T);

for (int t = 1; t <= T; t++) {
scanf("%d", &n);
memset(p, 0, sizeof p);
p[0] = 1.0;
p[n-1] = 1.0;

for (int i = 0; i < n; i++) {
scanf("%d", a+i);
}

for (int i = 1; i < n-1; i++) {
for (int j = i-6 < 0 ? 0 : i-6; j < i; j++) {
if (j+6 < n) {
p[i] += p[j]/6;
} else {
p[i] += p[j]/(n-j-1);
}
}
}
double ans = a[0];
if (n > 1) ans += a[n-1];
for (int i = 1; i < n-1; i++) ans += p[i]*(double)a[i];
printf("Case %d: %.7lf\n", t, ans);
}
return 0;
}


Race to 1 Again

给出一个数字$D$
我们可以选择$1-D$中可以被$D$整除的数字,然后用$D$出得到一个新的数字$D_1$;
然后在找所有$D_1$的因子,用$D_1$除,直到得到1;
问除的次数的期望值;

题解:

dp转移方程

这篇博客有详细推导。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <stdio.h>
using namespace std;
#define ll long long
double dp[100005];
int main(int argc, char const *argv[])
{
int T, n;
dp[1] = 0;
for (int i = 2; i <= 100000; i++) {
dp[i] = 0;
int num = 0;
for (int j = 1; j*j <= i; j++) {
if (i % j == 0) {
dp[i] += dp[j];
num++;
if (i/j != j) {
num++;
dp[i] += dp[i/j];
}
}
}
dp[i] = (dp[i]+num)/(num-1);
}
scanf("%d", &T);

for (int t = 1; t <= T; t++) {
scanf("%d", &n);
printf("Case %d: %lf\n", t, dp[n]);
}
return 0;
}
文章作者: Sshpark
文章链接: http://sshpark.com.cn/2018/12/04/kuangbin带你飞-专题二十一-概率-期望/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Sshpark