首页 > 代码库 > ACdream原创群赛(13)のwuyiqi退役专场 F The Arrow
ACdream原创群赛(13)のwuyiqi退役专场 F The Arrow
F
首先是要理解概率求期望这种题目是用递归来解的!
大概规律就是:
完成事件A的期望是Ea,一次完成的概率是pa,那么
Ea = pa * Ea + (1 + Ea) * (1 - pa)
如果有好多种可能,比方说完成一个事件A的同时,也有诸如事件B的概率期望pb,Eb,事件C的概率期望pc,Ec等等等等,那么就分别写出来:
Ea = pa * Ea + (1 + Ea) * (~pa) + pb * (1 + Eb) + pc * (1 + Ec) + ...
其中~pa是除了这些已知的事件发生概率以外,的概率,也就是~pa = 1 - pa - pb - pc - ...
所以这个题的期望递推公式就是
E1 = 1/6 * E1 + 5/6 * (1 + E1)
E2 = 1/6 * E2 + 1/6 * (1 + E1) + 4/6 * (1 + E2)
E3 = 1/6 * E3 + 1/6 * (1 + E1) + 1/6 * (1 + E2) + 3/6 * (1 + E3)
E4 = 1/6 * E4 + 1/6 * (1 + E1) + 1/6 * (1 + E2) + 1/6 * (1 + E3) + 2/6 * (1 + E4)
E5 = 1/6 * E5 + 1/6 * (1 + E1) + 1/6 * (1 + E2) + 1/6 * (1 + E3) + 1/6 * (1 + E4) + 1/6 * (1 + E5)
E6 = 1/6 * E6 + 1/6 * (1 + E1) + 1/6 * (1 + E2) + 1/6 * (1 + E3) + 1/6 * (1 + E4) + 1/6 * (1 + E5)
E7 = 1/6 * (1 + E1) + 1/6 * (1 + E2) + 1/6 * (1 + E3) + 1/6 * (1 + E4) + 1/6 * (1 + E5) + 1/6 * (1 + E6)
E8 = 1/6 * (1 + E2) + 1/6 * (1 + E3) + 1/6 * (1 + E4) + 1/6 * (1 + E5) + 1/6 * (1 + E6) + 1/6 * (1 + E7)
规律很明显。。。
/**** *COPYRIGHT NOTICE *Copyright (c) 2014 *All rights reserved *@author Shen *@name F *@file G:\My Source Code\比赛与日常练习\0608 - wuyiqi退役赛\F\F.cpp *@date 2014/6/8 20:21 */ //#pragma GCC optimize ("O2") //#pragma comment(linker, "/STACK:1024000000,1024000000") #define _CRT_SECURE_NO_WARNINGS #include <cmath> #include <cstdio> #include <string> #include <cstring> #include <iomanip> #include <iostream> #include <algorithm> using namespace std; /*//STL #include <map> #include <vector> #include <list> #include <stack> #include <deque> #include <queue> */ /*//Computational Geometry #include <complex> #define x real() #define y imag() typedef complex<double> point; */ typedef long long int64; const double p6 = 1.0 / 6.0; double res[100005]; int t, q; void init() { int i = 1, j = 7; double tmp = 36.0; for (; j < 100005; i++, j++) { res[j] = p6 * (6.0 + tmp); tmp = tmp + res[j] - res[i]; } } void solve() { scanf("%d", &q); printf("%.2lf\n", res[q]); } int main() { res[1] = res[2] = res[3] = res[4] = res[5] = res[6] = 6; init(); scanf("%d", &t); while (t--) solve(); return 0; }