网站建设案例收费情况,长沙网站开发微联,网站建设项目步骤,wordpress 访问量过大【CTSC2017】游戏
problem
UOJ299
solution
定义 Xi:X_i:Xi: 当前已知条件第 iii 局的状态 1/01/01/0#xff08;胜/败#xff09;。
将 XiCiX_iC_iXiCi 记为事件 AiA_iAi。
假设现在已知条件共有 sss 个#xff0c;即#xff1a;第 k1∼sk_{1\sim s}k1∼s…【CTSC2017】游戏
problem
UOJ299
solution
定义 Xi:X_i:Xi: 当前已知条件第 iii 局的状态 1/01/01/0胜/败。
将 XiCiX_iC_iXiCi 记为事件 AiA_iAi。
假设现在已知条件共有 sss 个即第 k1∼sk_{1\sim s}k1∼s 局的胜负状态。
期望不妨拆成求和每一局获胜的概率。
那么答案为 ∑i1nP(Xi1∣Ak1Ak2...Aks)\sum_{i1}^nP(X_i1\Big|A_{k_1}A_{k_2}...A_{ks})∑i1nP(Xi1∣∣∣Ak1Ak2...Aks)
P(Xi1∣Ak1Ak2...Aks)P(Xi1⋅Ak1...Aks)P(Ak1...Aks)P(X_i1\Big|A_{k_1}A_{k_2}...A_{ks})\frac{P(X_i1·A_{k_1}...A_{k_s})}{P(A_{k_1}...A_{k_s})}P(Xi1∣∣∣Ak1Ak2...Aks)P(Ak1...Aks)P(Xi1⋅Ak1...Aks)
P(Ak1...Aks)P(Ak1)P(Ak2∣Ak1)P(Ak3∣Ak1Ak2)...P(Aks∣Ak1...Aks−1)P(A_{k_1}...A_{k_s})P(A_{k_1})P(A_{k_2}|A_{k_1})P(A_{k_3}|A_{k_1}A_{k_2})...P(A_{k_s}|A_{k_1}...A_{k_{s-1}})P(Ak1...Aks)P(Ak1)P(Ak2∣Ak1)P(Ak3∣Ak1Ak2)...P(Aks∣Ak1...Aks−1)
因为每一局的胜负概率只和上一局有关所以 P(Ak3∣Ak1Ak2)P(Ak3∣Ak2)P(A_{k_3}|A_{k_1}A_{k_2})P(A_{k_3}|A_{k_2})P(Ak3∣Ak1Ak2)P(Ak3∣Ak2)
即P(Ak1...Aks)P(Ak1)P(Ak2∣Ak1)P(Ak3∣Ak2)...P(Aks∣Aks−1)P(A_{k_1}...A_{k_s})P(A_{k_1})P(A_{k_2}|A_{k_1})P(A_{k_3}|A_{k_2})...P(A_{k_s}|A_{k_{s-1}})P(Ak1...Aks)P(Ak1)P(Ak2∣Ak1)P(Ak3∣Ak2)...P(Aks∣Aks−1)
假设 k1k2...kjikj1...ksk_1k_2...k_jik_{j1}...k_sk1k2...kjikj1...ks
类似地P(Xi1Ak1...Aks)P(Ak1)...P(Akj∣Xi1)P(Xi1∣Akj1)...P(Aks∣Aks−1)P(X_i1A_{k_1}...A_{k_s})P(A_{k_1})...P(A_{k_j}|X_i1)P(X_i1|A_{k_{j1}})...P(A_{k_s}|A_{k_{s-1}})P(Xi1Ak1...Aks)P(Ak1)...P(Akj∣Xi1)P(Xi1∣Akj1)...P(Aks∣Aks−1)
所以 P(Xi1∣Ak1Ak2...Aks)P(Akj∣Xi1)P(Xi1∣Akj1)P(Akj1∣Akj)P(X_i1\Big|A_{k_1}A_{k_2}...A_{ks})\frac{P(A_{k_j}|X_i1)P(X_i1|A_{k_{j1}})}{P(A_{k_{j1}}|A_{k_j})}P(Xi1∣∣∣Ak1Ak2...Aks)P(Akj1∣Akj)P(Akj∣Xi1)P(Xi1∣Akj1)
答案为 ∑i1nP(Akj∣Xi1)P(Xi1∣Akj1)P(Akj1∣Akj)\sum_{i1}^n\frac{P(A_{k_j}|X_i1)P(X_i1|A_{k_{j1}})}{P(A_{k_{j1}}|A_{k_j})}∑i1nP(Akj1∣Akj)P(Akj∣Xi1)P(Xi1∣Akj1)
也就是说已知结果将 nnn 局游戏划分成了若干段区间每段的贡献计算的先决条件都是一样的。
也就是说每个区间的答案为 ∑ikj1ikj1−1P(Akj∣Xi1)P(Xi1∣Akj1)P(Akj1∣Akj)\sum_{ik_j1}^{ik_{j1}-1}\frac{P(A_{k_j}|X_i1)P(X_i1|A_{k_{j1}})}{P(A_{k_{j1}}|A_{k_j})}∑ikj1ikj1−1P(Akj1∣Akj)P(Akj∣Xi1)P(Xi1∣Akj1)
设 Q(r∣l):Q(r|l):Q(r∣l): 第 lll 局 RRR 赢的情况下第 rrr 局 RRR 赢的概率∼l\sim l∼l 则表示第 lll 局 RRR 输。
显然有Q(l1∣l)p[l1]Q(l1\Big|l)p[l1]Q(l1∣∣∣l)p[l1]再考虑计算 Q(l2∣l)Q(l2\Big|l)Q(l2∣∣∣l)。 Q(l2∣l)Q(l2∣l1)⋅Q(l1∣l)Q(l2∣∼(l1))⋅Q(∼(l1)∣l)p[l2]⋅p[l1]q[l2]⋅(1−p[l1])Q(l2\Big|l)Q(l2\Big|l1)·Q(l1\Big|l)Q(l2\Big|\sim(l1))·Q(\sim(l1)\Big|l)\\p[l2]·p[l1]q[l2]·(1-p[l1]) Q(l2∣∣∣l)Q(l2∣∣∣l1)⋅Q(l1∣∣∣l)Q(l2∣∣∣∼(l1))⋅Q(∼(l1)∣∣∣l)p[l2]⋅p[l1]q[l2]⋅(1−p[l1]) 同理可计算出Q(l2∣∼l),Q(∼(l2)∣l),Q(∼(l2)∣∼l)Q(l2\Big|\sim l),Q(\sim (l2)\Big|l),Q(\sim (l2)\Big|\sim l)Q(l2∣∣∣∼l),Q(∼(l2)∣∣∣l),Q(∼(l2)∣∣∣∼l)
发现这其实是两个矩阵相乘的结果即 fl1⋅fl2f_{l1}·f_{l2}fl1⋅fl2
fi[1−qiqi1−pipi]f_{i}\begin{bmatrix}1-q_i\quad\quad q_i\\1-p_i\quad\quad p_i\end{bmatrix}fi[1−qiqi1−pipi]
可以继续这么归纳下去计算 Q(r∣l)Q(r\Big|l)Q(r∣∣∣l) 等相关信息无非就是一个连续区间的矩阵相乘后某个位置的结果。
∑ikj1ikj1−1P(Akj∣Xi1)P(Xi1∣Akj1)P(Akj1∣Akj)\sum_{ik_j1}^{ik_{j1}-1}\frac{P(A_{k_j}|X_i1)P(X_i1|A_{k_{j1}})}{P(A_{k_{j1}}|A_{k_j})}∑ikj1ikj1−1P(Akj1∣Akj)P(Akj∣Xi1)P(Xi1∣Akj1)用线段树维护矩阵 fff。
分母就是 fff 矩阵从 kjk_{j}kj 一直乘到 kj1k_{j1}kj1。
分子就是 fff 矩阵乘到 iii 位置时只乘第二列表示胜利可以新定义一个矩阵 gig_igi。
gi[0qi0pi]g_{i}\begin{bmatrix}0\quad\quad q_i\\0\quad\quad p_i\end{bmatrix}gi[0qi0pi]在乘到 iii 位置时变成乘 gig_igi。
同样用线段树维护gnowflson∗grsonglson∗frson;fnowflson∗grsong_{now}f_{lson}*g_{rson}g_{lson}*f_{rson};f_{now}f_{lson}*g_{rson}gnowflson∗grsonglson∗frson;fnowflson∗grson
最后就是具体实现问题了。
考虑插入两个哨兵 0,n10,n10,n1初始局面答案就是一整个区间。
有涉及到询问当前已知条件中的前驱 lll 后继 rrr 问题就需要用 STL 实现。
加点就用答案减去区间 (l,r)(l,r)(l,r) 的贡献再加上区间 (l,i)(l,i)(l,i) 和区间 (i,r)(i,r)(i,r) 的贡献。
删点就用答案减去区间 (l,i)(l,i)(l,i) 和区间 (i,r)(i,r)(i,r) 的贡献再加上区间 (l,r)(l,r)(l,r) 的贡献。
code
#include map
#include cstdio
#include cstring
#include algorithm
using namespace std;
struct matrix {double c[2][2];// double * operator [] ( int x ) { return c[x]; }matrix() { memset( c, 0, sizeof( c ) ); }friend matrix operator ( matrix u, matrix v ) {matrix ans;for( int i 0;i 2;i )for( int j 0;j 2;j )ans.c[i][j] v.c[i][j] u.c[i][j];return ans;}friend matrix operator * ( matrix u, matrix v ) {matrix ans;for( int i 0;i 2;i )for( int j 0;j 2;j )for( int k 0;k 2;k )ans.c[i][j] u.c[i][k] * v.c[k][j];return ans;}void print() {for( int i 0; i 2; i ) {for( int j 0; j 2; j )printf( %.3f , c[i][j] );printf( \n );}}
};
#define maxn 200005
struct node { matrix f, g; }t[maxn 2];
int n, m;
char type;
double ans;
double p[maxn], q[maxn];
map int, bool x;#define lson now 1
#define rson now 1 | 1
#define mid ( ( l r ) 1 )node operator ( node x, node y ) {node ans;ans.f x.f * y.f;ans.g x.g * y.f x.f * y.g;return ans;
}void build( int now, int l, int r ) {if( l r ) {t[now].f.c[0][0] 1 - q[l];t[now].f.c[0][1] t[now].g.c[0][1] q[l];t[now].f.c[1][0] 1 - p[l];t[now].f.c[1][1] t[now].g.c[1][1] p[l];// printf( (%d):\n, l );// t[now].f.print();t[now].g.print();return;}build( lson, l, mid );build( rson, mid 1, r );t[now] t[lson] t[rson];// printf( { %d } [%d, %d] ::\n, now, l, r );// t[now].f.print(); t[now].g.print();
}node query( int now, int l, int r, int L, int R ) {if( L l and r R ) return t[now];if( R mid ) return query( lson, l, mid, L, R );else if( mid L ) return query( rson, mid 1, r, L, R );else return query( lson, l, mid, L, R ) query( rson, mid 1, r, L, R );
}double Ask( int l, int r ) {node now query( 1, 0, n 1, l 1, r );// now.f.print(); now.g.print();return now.g.c[x[l]][x[r]] / now.f.c[x[l]][x[r]];
}int main() {scanf( %d %d %c %lf, n, m, type, p[1] );for( int i 2;i n;i ) scanf( %lf %lf, p[i], q[i] );p[0] q[0] x[0] 1, x[n 1] 0;build( 1, 0, n 1 );ans Ask( 0, n 1 );// printf( %f\n, ans );while( m -- ) {char opt[10]; int i, c;scanf( %s, opt );if( opt[0] a ) {scanf( %d %d, i, c );auto r x.lower_bound( i );auto l r;l --;x[i] c;ans - Ask( l - first, r - first );ans Ask( l - first, i );ans Ask( i, r - first );}else {scanf( %d, i );auto r x.upper_bound( i );auto l r;l --, l --;ans - Ask( l - first, i );ans - Ask( i, r - first );ans Ask( l - first, r - first );x.erase( l );}printf( %f\n, ans );}return 0;
}
