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_1\)； 然后在找所有\(D_1\)的因子，用\(D_1\)除，直到得到1； 问除的次数的期望值；

题解：

dp转移方程 \[ dp[n] = (\sum_{d|n}{dp[d]}+num)/(num-1), num为n的因子个数，d \ne n \]

这篇博客有详细推导。

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;
}