【BZOJ 4318】OSU!

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4318
神犇题解:https://oi.men.ci/bzoj-4318/

解题报告

设$p_i$为第$i$个操作成功的概率
设$E_{(i,x^3)}$为以第$i$个位置为结尾,$($极长$1$的长度$x)^3$的期望
$E_{(i,x^2)},E_{(i,x)}$分别表示$x^2,x$的期望

那么根据全期望公式,我们有如下结论:

$E_{(i,x^3)}=p_i \times E_{(i-1,(x+1)^3)}$
$E_{(i,x^2)}=p_i \times E_{(i-1,(x+1)^2)}$
$E_{(i,x)}=p_i \times (E_{(i-1,x)} + 1)$

不难发现只有第三个式子可以直接算
但我们还知道一个东西叫期望的线性,于是我们可以将前两个式子化为:

$E_{(i,x^3)}=p_i \times (E_{(i-1,x^3)} + 3E_{(i-1,x^2)} + 3E_{(i-1,x)} + 1)$
$E_{(i,x^2)}=p_i \times (E_{(i-1,x^2)} + 2E_{(i-1,x)} + 1)$

然后就可以直接维护,然后再根据期望的线性加入答案就可以辣!
时间复杂度:$O(n)$

另外,似乎直接算贡献也可以?
可以参考:http://blog.csdn.net/PoPoQQQ/article/details/49512533

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	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 n=read(); 
	double e1=0,e2=0,e3=0,ans=0,p;
	for (int i=1;i<=n;i++) {
		scanf("%lf",&p);
		ans += e3 * (1 - p);
		e3 = p * (e3 + 3 * e2 + 3 * e1 + 1);
		e2 = p * (e2 + 2 * e1 + 1);
		e1 = p * (e1 + 1);
	} 
	printf("%.1lf\n",ans+e3);
	return 0;
}

197 thoughts to “【BZOJ 4318】OSU!”

  1. I must thank you for the efforts you’ve put in penning this website. I am hoping to see the same high-grade content by you later on as well. In truth, your creative writing abilities has encouraged me to get my very own blog now 😉

  2. Hi there, I found your website via Google while looking for a related topic, your web site came up, it looks great. I’ve bookmarked it in my google bookmarks.

  3. I absolutely love your blog and find almost all of your post’s
    to be what precisely I’m looking for. can you offer guest writers to write content in your case?
    I wouldn’t mind writing a post or elaborating on most of the subjects you write related to here.
    Again, awesome web site!

  4. After I initially left a comment I appear to have clicked on the -Notify me when new comments are added- checkbox and from now on whenever a comment is added I get 4 emails with the same comment.
    Perhaps there is an easy method you can remove me from that
    service? Thanks a lot!

  5. Hey I know this is off topic but I was wondering if you knew of any widgets I could add to my
    blog that automatically tweet my newest twitter updates.
    I’ve been looking for a plug-in like this for quite some time and was hoping maybe
    you would have some experience with something
    like this. Please let me know if you run into anything.
    I truly enjoy reading your blog and I look forward to your new
    updates.

  6. First of all I want to say excellent blog! I had a quick question that I’d
    like to ask if you don’t mind. I was curious to find out how you
    center yourself and clear your thoughts before writing.
    I have had trouble clearing my thoughts in getting my thoughts out.
    I do enjoy writing however it just seems like the first
    10 to 15 minutes are usually wasted just trying
    to figure out how to begin. Any suggestions or tips?
    Appreciate it!

  7. After going over a few of the blog articles on your
    web page, I really like your technique of writing a blog.
    I book marked it to my bookmark website list and will be checking
    back soon. Please check out my website as well and let me know what you think.

  8. I really like your writing style, wonderful info, appreciate it for posting :D. “If a cluttered desk is the sign of a cluttered mind, what is the significance of a clean desk” by Laurence J. Peter.

  9. Wow that was strange. I just wrote an incredibly long comment but after I clicked
    submit my comment didn’t appear. Grrrr… well I’m not writing all that over again. Regardless,
    just wanted to say wonderful blog!

  10. Hey would you mind stating which blog platform you’re using?
    I’m looking to start my own blog in the near future
    but I’m having a difficult time choosing between BlogEngine/Wordpress/B2evolution and
    Drupal. The reason I ask is because your layout seems different then most blogs and I’m looking for something unique.
    P.S My apologies for getting off-topic but I had to ask!

  11. My partner and I stumbled over here different web address and thought I might check things out.
    I like what I see so i am just following you. Look forward
    to looking over your web page for a second time.

  12. Thank you for another great article. Where else could anybody get that type of info in such a perfect approach of writing? I’ve a presentation next week, and I am on the look for such information.

  13. Thank you a lot for sharing this with all people you really know what you’re talking about!
    Bookmarked. Kindly additionally seek advice from my site =).
    We can have a link alternate contract among us

  14. Greate pieces. Keep writing such kind of info on your page.
    Im really impressed by your site.
    Hi there, You have performed an excellent job. I’ll definitely digg it and in my
    view recommend to my friends. I’m confident they’ll be benefited
    from this website.

发表评论

电子邮件地址不会被公开。 必填项已用*标注