Chaos Slover 补档计划 - 概率与期望

2015.11.10 11:28 Tue| 7 visits oi_2016| ChaosSlover补档计划| Text

BZOJ3036 绿豆蛙的归宿

简单的期望入门题。大概求起点到终点的距离更为方便。

 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
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;

#define N 100005

int n, m, head[N], vis[N], out[N];
double f[N];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

struct graph
{
    int next, to, val;
    graph() {}
    graph(int _next, int _to, int _val)
    : next(_next), to(_to), val(_val) {}
} edge[N * 2];

inline void add(int x, int y, int z)
{
    static int cnt = 0;
    edge[++cnt] = graph(head[x], y, z);
    head[x] = cnt;
}

void dfs(int x)
{
    if (vis[x]) return;
    vis[x] = 1;
    for (int i = head[x]; i; i = edge[i].next)
        dfs(edge[i].to), f[x] += (f[edge[i].to] + edge[i].val) / out[x];
}

int main()
{
    cin >> n >> m;
    for (int x, y, z, i = 1; i <= m; ++i)
        x = read(), y = read(), z = read(),
        add(x, y, z), ++out[x];
    vis[n] = 1;
    dfs(1);
    cout << fixed << setprecision(2) << f[1] << endl;
    return 0;
}

BZOJ3143 [Hnoi2013]游走

妈妈我终于会写高斯消元了!

对于这道题,我们要考虑求出经过图中每一条边的期望次数,然后便可以很简单地计算出答案了。

设 outi 表示结点 i 的出边条数,Ei 表示到达结点 i 的期望次数,E(u,v) 表示经过边 (u,v) 的期望次数。

首先可以得到:

(若 u=n 或 v=n ,则相应的一项不能计入期望)。

考虑如何求每一个结点的期望到达次数。可以列出如下方程组:

由于点 1 在最开始就被访问了一次,因此到达次数需要加上1。点 n 只在最后被访问了一次,因此到达次数一定为1。这个方程组可以用高斯消元解出。

 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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>
using namespace std;

#define N 505

int n, m, head[N], x[N * N], y[N * N], out[N];
double f[N][N], val[N * N], ans;

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

struct graph
{
    int next, to;
    graph() {}
    graph(int _next, int _to)
    : next(_next), to(_to) {}
} edge[N * N];

inline void add(int x, int y)
{
    static int cnt = 0;
    edge[++cnt] = graph(head[x], y);
    head[x] = cnt;
}

void gauss()
{
    for (int i = 1; i <= n; ++i)
    {
        int t = 0;
        for (int j = i; j <= n; ++j)
            if (fabs(f[j][i]) > 1e-9) { t = j; break; }
        if (t != i)
            for (int j = 1; j <= n + 1; ++j)
                swap(f[i][j], f[t][j]);
        for (int j = i + 1; j <= n; ++j)
            if (f[j][i])
            {
                double t = f[j][i] / f[i][i];
                for (int k = i; k <= n + 1; ++k)
                    f[j][k] -= t * f[i][k];
            }
    }
    for (int i = n; i; --i)
    {
        f[i][n + 1] /= f[i][i];
        for (int j = i - 1; j; --j)
            f[j][n + 1] -= f[j][i] * f[i][n + 1];
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
        x[i] = read(), y[i] = read(),
        add(x[i], y[i]), add(y[i], x[i]), ++out[x[i]], ++out[y[i]];
    out[n] = 0;
    for (int i = 1; i < n; ++i)
        f[i][i] = -1;
    for (int i = 1; i < n; ++i)
        for (int j = head[i]; j; j = edge[j].next)
            if (edge[j].to != n)
                f[i][edge[j].to] = 1.0 / out[edge[j].to];
    f[1][n + 1] = -1;
    f[n][n] = f[n][n + 1] = 1;
    gauss();
    for (int i = 1; i <= m; ++i)
    {
        if (x[i] != n)
            val[i] += f[x[i]][n + 1] / out[x[i]];
        if (y[i] != n)
            val[i] += f[y[i]][n + 1] / out[y[i]];
    }
    sort(val + 1, val + m + 1);
    for (int i = 1; i <= m; ++i)
        ans += (m - i + 1) * val[i];
    cout << fixed << setprecision(3) << ans << endl;
    return 0;
}

BZOJ2510&4204 弱取球游戏

很容易看出来是矩阵乘法,转移矩阵如下。

时间复杂度 O(N^3*log(K))。

观察上面的转移矩阵,其第 i 行(i>1)可由第 i-1 行右移得到。并且它自乘多少次之后也都会满足这一性质。因此只需要记录这个矩阵的第一行元素即可,转移的复杂度降为了 O(N^2*log(K))。

然而数据中没有 n=1 的情况,差评。

 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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;

#define N 1005

int n, m, k;

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

struct matrix
{
    double t[N];
    matrix() { memset(t, 0, sizeof t); }
    friend matrix operator *(const matrix &a, const matrix &b)
    {
        matrix re;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                re.t[i] += a.t[j] * b.t[(i - j + n) % n];
        return re;
    }
    matrix &operator *=(const matrix &x) { return *this = *this * x; }
    friend matrix pow(matrix x, int k)
    {
        matrix re;
        re.t[0] = 1;
        while (k)
        {
            if (k & 1) re *= x;
            x *= x; k >>= 1;
        }
        return re;
    }
    friend ostream &operator <<(ostream &out, const matrix &x)
    {
        for (int i = 0; i < n; ++i)
            out << x.t[i] << '\n';
        return out;
    }
} mat, ans;

int main()
{
    cin >> n >> m >> k;
    for (int i = 0; i < n; ++i)
        ans.t[i] = read();
    cout << fixed << setprecision(3);
    if (n == 1) { cout << ans; return 0; }
    mat.t[0] = 1.0 * (m - 1) / m, mat.t[1] = 1.0 * 1 / m;
    cout << ans * pow(mat, k);
    return 0;
}

BZOJ2878 [Noi2012]迷失游乐园

题目中给的一定是一棵树或一棵基环树,且基环树的环大小不超过 20。

一份无比详细的题解 http://www.cnblogs.com/Tunix/p/4561493.html

如果是一棵树,那么直接两遍 DFS 即可;

如果是一棵基环树,那么对于环上的每一棵树,down 数组的求法和树的情况没有区别。但求 up 时,发现环上的树的根结点并非没有 up 值,而是 up 值可以由其他的树转移来。这样我们需要先求出来环上每一个结点的 up 值,之后求树中 up 值时和只有一棵树的情况大同小异。

求环上结点的 up 值的时候分咽着顺时针走和逆时针走两种路径。分别遍历这一个环,在 O(P^2) (P 为环上结点数)的时间内求解就好了。对于结点 x,当在环上遍历到某一个结点 y 的时候会发现分别有 1/(son[y]+1) 和 son[y]/(son[y]+1) 的可能性接着走环上的边或走到 y 的子树中去。然而当 y 再继续在环上走一步就会到达 x 的时候,就一定不会继续走到 x 了,只有进入到子树中的可能性。这样就可以在环上转移了。

  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
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <bits/stdc++.h>
using namespace std;

#define N 100005

bool circle[N];
int n, m, ex, ey, ez, f[N], head[N], deep[N], fa[N], val[N], size[N];
double up[N], down[N];
vector<int> cir, cirval;

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

struct graph
{
    int next, to, val;
    graph() {}
    graph(int _next, int _to, int _val)
    : next(_next), to(_to), val(_val) {}
} edge[N * 2];

inline void add(int x, int y, int z)
{
    static int cnt = 0;
    edge[++cnt] = graph(head[x], y, z);
    head[x] = cnt;
}

int find(int x)
{
    if (x == f[x]) return x;
    return f[x] = find(f[x]);
}

void predfs(int x)
{
    deep[x] = deep[fa[x]] + 1;
    size[x] = 0;
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].to != fa[x] && !circle[edge[i].to])
            ++size[x], val[edge[i].to] = edge[i].val, fa[edge[i].to] = x,
            predfs(edge[i].to);
}

void getdown(int x)
{
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].to != fa[x] && !circle[edge[i].to])
        {
            getdown(edge[i].to);
            down[x] += (down[edge[i].to] + edge[i].val) / size[x];
        }
}

void getup(int x)
{
    if (x == 1) goto tag;
    if (fa[x] == 1)
        up[x] = val[x] + (down[fa[x]] * size[fa[x]] - val[x] - down[x]) / (size[fa[x]] - 1);
    else
        up[x] = val[x] + (down[fa[x]] * size[fa[x]] - val[x] - down[x] + up[fa[x]]) / size[fa[x]];
    tag: 
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].to != fa[x])
            getup(edge[i].to);
}

void getup2(int x)
{
    if (circle[x]) goto tag2;
    if (circle[fa[x]])
        up[x] = val[x] + (down[fa[x]] * size[fa[x]] - val[x] - down[x] + up[fa[x]] * 2) / (size[fa[x]] + 1);
    else
        up[x] = val[x] + (down[fa[x]] * size[fa[x]] - val[x] - down[x] + up[fa[x]]) / size[fa[x]];
    tag2: 
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].to != fa[x] && !circle[edge[i].to])
            getup2(edge[i].to);
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) f[i] = i;
    for (int x, y, z, i = 1; i <= m; ++i)
    {
        x = read(); y = read(); z = read();
        int fx = find(x), fy = find(y);
        if (fx != fy) add(x, y, z), add(y, x, z), f[fx] = fy;
        else ex = x, ey = y, ez = z;
    }
    if (n != m)
    {
        predfs(1);
        getdown(1);
        getup(1);
        double ans = down[1];
        for (int i = 2; i <= n; ++i)
            ans += (up[i] + down[i] * size[i]) / (size[i] + 1);
        cout << fixed << setprecision(5) << ans / n << endl;
    }
    if (n == m)
    {
        predfs(ey);
        for (int i = ex; i != 0; i = fa[i])
            circle[i] = true, cir.push_back(i), cirval.push_back(val[i]);
        cirval[cirval.size() - 1] = ez;
        int tot = cir.size();
        for (int i = 0; i < tot; ++i)
            fa[cir[i]] = 0, predfs(cir[i]), getdown(cir[i]);
        for (int i = 0; i < tot; ++i)
        {
            double len = 0, p = 0.5;
            for (int j = 1; j < tot; ++j)
            {
                len = cirval[j - 1];
                if (j == tot - 1)
                    up[cir[0]] += p * (len + down[cir[j]]);
                else
                    up[cir[0]] += p * (len + down[cir[j]] * size[cir[j]] / (size[cir[j]] + 1));
                p /= (size[cir[j]] + 1);
            }
            len = 0; p = 0.5;
            for (int j = tot - 1; j; --j)
            {
                len = cirval[j];
                if (j == 1)
                    up[cir[0]] += p * (len + down[cir[j]]);
                else
                    up[cir[0]] += p * (len + down[cir[j]] * size[cir[j]] / (size[cir[j]] + 1));
                p /= (size[cir[j]] + 1);
            }
            rotate(cir.begin(), cir.begin() + 1, cir.end());
            rotate(cirval.begin(), cirval.begin() + 1, cirval.end());
        }
        for (int i = 0; i < tot; ++i)
            getup2(cir[i]);
        double ans = 0;
        for (int i = 1; i <= n; ++i)
            if (circle[i])
                ans += (up[i] * 2 + down[i] * size[i]) / (size[i] + 2);
            else
                ans += (up[i] + down[i] * size[i]) / (size[i] + 1);
        cout << fixed << setprecision(5) << ans / n << endl;
    }
    return 0;
}