「UOJ299」CTSC2017 游戏

杂题 / uoj
Word count: 2.2k   |   Reading time≈ 11 min

为数不多的贝叶斯定理题

Solution

首先要搞清楚这个题目的逻辑是什么，假设 A 事件发生的概率为 P(A)，事件 A’ 发生的概率是 P(A’)。并且发生A事件后还有 P(B) 的概率发生 B 事件，发生 A’ 事件后发生 P(B) 的概率是 P(B’)。那么假设 B 事件发生了，那么 A 发生的概率也会相应的做出变化。

虽然说起来很抽象，但是在现实中理解起来并不困难。假设中国人占世界总人口的 14%，并且他们有 99% 的概率会投票通过某项法案，剩下世界上的 86% 的人中，会投票通过某一下法案为 50%，那么假设我们从世界上的所有人当中选出了一个人，他投票通过了该法案，那么他是中国人的概率显然比 14% 要来的多，你随便想想也觉得很有道理不是么。

如果现在你理解的这个题的逻辑，那么你就会用到题目最后给你的那些公式了，在这里我也不作赘述。

现在考虑原问题，首先根据期望的线性性，我们把获胜的总数变成每一局获胜概率的和。

我们令事件 $R_i$ 表示第 $i$ 局游戏中 R 赢， $B_i$ 反之。

考虑如何计算一局游戏 $R_i$ 是多少。假设我们知道了一些游戏的赢家是谁，那么对于剩下的未知的游戏，显然他的胜率只和它前面以及后面第一个有结果的游戏有关。假设对于第 $i$ 局游戏（这局结果未知），他前面第一局游戏的结果是 A，后面第一局游戏是 B，那么这一句小 R 赢的概率就是 $P(R_i|AB)$ ，因为 AB 已经发生了，并且对这一局游戏的结果有影响。我们展开这个式子

现在考虑这个式子如何计算。

我们构造出一个向量 $[P(R_i), P(B_i), S_{R_i}, S_{B_i}]$ ，其中表示考虑了这个区间的 $[l, i]$ 之间的游戏，当前游戏两个人获胜的概率以及在这一局 小B 或小R 获胜的前提下小 R 之前获胜局数的期望（也就是概率和）。

显然我们可以构造出转移矩阵

那么我们发现，原本的式子 $P(B|A)$ 和 $P(R_iB|A)$ 都是在 A 发生的前提下的，于是我们的初始矩阵就可以根据 A 来赋值，然后我们乘上AB区间的转移矩阵，最后 $P(B|A)$ 就是 $P(R_i)$ 或 $P(B_i)$，$P(R_iB|A)$ 就是 $\frac{S_{B}}{P(B)}$ 。于是我们只要维护出一个区间的矩阵积即可。

于是你又注意到的题目最底下的一句话，这个题不能矩阵求逆，于是你只能写一个线段树，为了避免精度误差。

具体实现的时候有点卡常，因为正常的做法矩阵好像是 $2\times2$ 的，但是我的做法矩阵是 $4\times4$ 的，稍微用心卡一卡就可以了。

Code

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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <map>
#include <set>
#include <ctime>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cctype>
#include <string>
#include <numeric>
#include <cstring>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std ;
#define int long long
#define rep(i, a, b) for (ll i = (a); i <= (b); ++i)
#define per(i, a, b) for (ll i = (a); i >= (b); --i)
#define loop(it, v) for (auto it = v.begin(); it != v.end(); it++)
#define cont(i, x) for (ll i = head[x]; i; i = edge[i].nex)
#define clr(a) memset(a, 0, sizeof(a))
#define ass(a, cnt) memset(a, cnt, sizeof(a))
#define cop(a, b) memcpy(a, b, sizeof(a))
#define lowbit(x) (x & -x)
#define all(x) x.begin(), x.end()
#define SC(t, x) static_cast <t> (x)
#define ub upper_bound
#define lb lower_bound
#define pqueue priority_queue
#define mp make_pair
#define pb push_back
#define pof pop_front
#define pob pop_back
#define fi first
#define se second
#define y1 y1_
#define Pi acos(-1.0)
#define iv inline void
#define enter putchar('\n')
#define siz(x) ((ll)x.size())
#define file(x) freopen(x".in", "r", stdin),freopen(x".out", "w", stdout)
typedef double db ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair <ll, ll> pii ;
typedef vector <ll> vi ;
typedef vector <pii> vii ;
typedef queue <ll> qi ;
typedef queue <pii> qii ;
typedef set <ll> si ;
typedef map <ll, ll> mii ;
typedef map <string, ll> msi ;
const ll maxn = 2e5 + 100 ;
const ll inf = 0x3f3f3f3f ;
const ll iinf = 1 << 30 ;
const ll linf = 2e18 ;
const ll mod = 998244353 ;
const double eps = 1e-7 ;
template <class T = ll> T chmin(T &a, T b) { return a = min(a, b);}
template <class T = ll> T chmax(T &a, T b) { return a = max(a, b);}
template <class T = ll> iv red(T &x) { x -= mod, x += x >> 31 & mod;}
template <class T = ll> T read()
{
    T f = 1, a = 0;
    char ch = getchar() ;
    while (!isdigit(ch)) { if (ch == '-') f = -1 ; ch = getchar() ; }
    while (isdigit(ch)) { a =  (a << 3) + (a << 1) + ch - '0' ; ch = getchar() ; }
    return a * f ;
}

ll n, m;

char tmp[5];

db p[maxn], q[maxn], ans;

ll tim;

struct matrix
{
    db a[4][4];
    db *operator [](ll x)
    {
        return a[x];
    }
    void clear()
	{
        rep(i, 0, 3) rep(j, 0, 3) a[i][j] = 0;
    }
    matrix(){clear();}
    matrix(db x)
    {
        clear();
        rep(i, 0, 3) a[i][i] = x;
    }
    matrix(db p, db q)
    {
        a[0][3] = a[1][3] = a[2][0] = a[2][1] = a[3][0] = a[3][1] = 0;
        a[0][0] = a[0][2] = a[2][2] = p;
        a[1][0] = a[1][2] = a[3][2] = q;
        a[0][1] = a[2][3] = 1 - p;
        a[1][1] = a[3][3] = 1 - q;
    }
    friend matrix operator * (matrix a, matrix b)
    {
        matrix ret;
        rep(i, 0, 3) rep(j, 0, 3) rep(k, 0, 3) ret[i][j] += a[i][k] * b[k][j];
        return ret;
    }
    matrix operator *= (matrix a)
    {
        (*this) = (*this) * a;
        return *this;
    }
}
a[maxn];

struct node
{
    ll l, r;
    matrix val;
}
tr[maxn << 3];

#define ls (tot << 1)
#define rs (ls | 1)
#define mid ((tr[tot].l + tr[tot].r) >> 1)

void maintain(ll tot)
{
    tr[tot].val = tr[ls].val * tr[rs].val;
}

void build(ll tot, ll l, ll r)
{
    tr[tot].l = l, tr[tot].r = r;
    if(l == r) return (void)(tr[tot].val = a[l] = matrix(p[l], q[l]));
    build(ls, l, mid), build(rs, mid + 1, r);
    maintain(tot);
}

matrix query(ll tot, ll l, ll r)
{
    if(tr[tot].l >= l && tr[tot].r <= r) return tr[tot].val;
    if(l > mid) return query(rs, l, r);
    if(r <= mid) return query(ls, l, r);
    return query(ls, l, r) * query(rs, l, r);
}

ll b[maxn];

db f[maxn];

db get_sum(ll l, ll r)
{
    if(l > r) return f[l] = 0;
    ll pos = 1 - b[l - 1];
    matrix ret = query(1, l, r);
    if(r == n) return f[l] = ret[pos][2] + ret[pos][3];
    ret *= a[r + 1];
    if(b[r + 1] == 1) return f[l] = ret[pos][2] / ret[pos][0] - 1.0;
    return f[l] = ret[pos][3] / ret[pos][1];
}

si s;

signed main()
{
    // file("main");
    n = read(), m = read();
    scanf("%s", tmp + 1);
    scanf("%lf", &p[1]);
    rep(i, 2, n) scanf("%lf %lf", &p[i], &q[i]);
    build(1, 1, n);
    s.insert(0), s.insert(n + 1), b[0] = 1;
    ans = get_sum(1, n);
    while(m --)
    {
        scanf("%s", tmp + 1);
        ll x = read();
        if(tmp[1] == 'a')
        {
            ll y = read();
            ans += y;
            ll pre = *(-- s.lb(x)), suf = *s.ub(x);
            ans -= f[pre + 1];
            s.insert(x);
            b[x] = y;
            ans += get_sum(pre + 1, x - 1) + get_sum(x + 1, suf - 1);
        }
        else
        {
            ans -= b[x];
            ll pre = *(-- s.lb(x)), suf = *s.ub(x);
            ans -= f[pre + 1] + f[x + 1];
            s.erase(s.find(x));
            ans += get_sum(pre + 1, suf - 1);
        }
        printf("%.6lf\n", ans);
    }
    return 0;
}
  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2020-2022 naitir
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信