题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2318
网上绝大部分证明完全没有说清楚好吗? (╯‵□′)╯︵┻━┻
只有这一份题解才稍微正常一点:http://codeplay0314.coding.me/2015/07/10/BZOJ2318/
本地备份:http://oi.cyo.ng/wp-content/uploads/2016/08/12345687856456754.png
不过这一题的推式子还是很神的,有一定参考价值。
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cstdio> #include<cmath> #include<bitset> #define LL long long #define abs(x) ((x)>0?(x):-(x)) using namespace std; const int N = 1000+9; const int LIM = 1000; int n; double f[N],g[N],p,q; inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar(); return ret*f; } int main(){ int T=read(); while (T--) { n = min(read(), LIM); scanf("%lf%lf",&p,&q); f[0] = 0; g[0] = 1; for (int i=1;i<=n;i++) { if (f[i-1] > g[i-1]) p = 1 - p, q = 1 - q; f[i] = (p*g[i-1] + (1-p)*q*f[i-1]) / (1 - (1-p)*(1-q)); g[i] = (q*f[i-1] + (1-q)*p*g[i-1]) / (1 - (1-p)*(1-q)); if (f[i-1] > g[i-1]) p = 1 - p, q = 1 - q; } printf("%.6lf\n",f[n]); } return 0; }
值得一提的是,我最开始定义的g[i]为胜i个石子时,Bob先走,Bob的胜算是多少
这样写出来的方程是: \(\begin{array}{l}
{a_i} = \left\{ \begin{array}{l}
p(1 – {b_i}) + (1 – p)(1 – {b_{i – 1}}),{b_i} < {b_{i - 1}}\\
p(1 - {b_{i - 1}}) + (1 - p)(1 - {b_i}),{b_i} > {b_{i – 1}}
\end{array} \right.\\
{b_i} = \left\{ \begin{array}{l}
q(1 – {a_i}) + (1 – q)(1 – {a_{i – 1}}),{a_i} < {a_{i - 1}}\\
q(1 - {a_{i - 1}}) + (1 - q)(1 - {a_i}),{a_i} > {a_{i – 1}}
\end{array} \right.
\end{array}\)
但你会发现,这么推,推不出来QAQ
仔细想一想为什么,我觉得是f[i]与(1-f[i])混用了吧?