题目传送门: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])混用了吧?
Hello! Do you know if they make any plugins to help with Search Engine Optimization? I’m trying to get my blog to rank for some
targeted keywords but I’m not seeing very good results.
If you know of any please share. Many thanks!
Your style is very unique compared to other people I’ve read stuff from.
I appreciate you for posting when you have the opportunity, Guess I’ll just book mark this page.
I could not refrain from commenting. Very well written!
I’ve been browsing online more than 2 hours today, yet I never found any interesting article like yours.
It’s pretty worth enough for me. In my view, if all site owners and
bloggers made good content as you did, the web
will be much more useful than ever before.
Hello there! I know this is kind of off topic but I was wondering if you knew where I could find a captcha plugin for my comment form?
I’m using the same blog platform as yours and I’m having difficulty finding one?
Thanks a lot!
Hello, everything is going perfectly here and ofcourse every one is sharing
information, that’s truly good, keep up writing.
Fantastic beat ! I would like to apprentice while you
amend your site, how can i subscribe for a blog website?
The account aided me a acceptable deal. I had been a little bit acquainted of this your broadcast offered bright clear idea
Good web site you have here.. It’s difficult to find good quality
writing like yours these days. I honestly appreciate people like you!
Take care!!
Hi, Neat post. There is an issue along with your site in web explorer, may check this?
IE still is the marketplace chief and a good component of other folks will omit your magnificent writing because of this problem.
Nice blog right here! Also your web site lots up fast!
What host are you using? Can I get your associate link for your host?
I desire my site loaded up as fast as yours lol
This is really interesting, You’re a very skilled blogger.
I have joined your feed and look forward to seeking more of your
wonderful post. Also, I’ve shared your site
in my social networks!
Hi, Neat post. There’s a problem with your website in web explorer, could check this?
IE still is the marketplace leader and a big part of people will pass over your excellent writing
because of this problem.
An outstanding share! I’ve just forwarded this onto a coworker who had
been doing a little research on this. And he in fact bought me lunch
due to the fact that I found it for him… lol.
So let me reword this…. Thanks for the meal!!
But yeah, thanks for spending some time to discuss
this subject here on your site.
It’s an remarkable post designed for all the web users;
they will take benefit from it I am sure.
It is perfect time to make some plans for the future and it is time to be happy.
I’ve read this post and if I could I want to suggest
you few interesting things or advice. Maybe you can write next articles referring to this article.
I wish to read even more things about it!
I am really impressed along with your writing abilities as well as with the format in your blog.
Is that this a paid theme or did you customize it your self?
Anyway keep up the excellent quality writing, it’s uncommon to peer
a great weblog like this one today..
Hurrah! At last I got a web site from where I be capable of
truly get useful data concerning my study and knowledge.
Heya! I just wanted to ask if you ever have any problems with hackers?
My last blog (wordpress) was hacked and I ended up losing a few months of hard work due to no data backup.
Do you have any solutions to stop hackers?
Highly energetic post, I liked that a lot. Will there be a part 2?
Asking questions are genuinely nice thing if you are not understanding something completely, however this article presents
pleasant understanding yet.
Everything is very open with a clear clarification of the challenges.
It was really informative. Your site is very useful. Thank you for sharing!
Thanks for sharing your thoughts about sling tv. Regards
Please let me know if you’re looking for a article writer
for your site. You have some really good articles and I think I would be a good asset.
If you ever want to take some of the load off, I’d absolutely love to write
some content for your blog in exchange for a link back to mine.
Please blast me an e-mail if interested. Thanks!
It’s genuinely very difficult in this full of activity life to listen news on TV, thus I simply use the web for that purpose,
and get the most recent information.
Hi there, just wanted to tell you, I liked this post. It was helpful.
Keep on posting!
Hello, yeah this paragraph is genuinely fastidious and I have learned
lot of things from it about blogging. thanks.
Thank you ever so for you blog article.Really looking forward to read more. Want more.