【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;
}

286 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. 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!

  3. 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!

  4. 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.

  5. 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!

  6. 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.

  7. 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.

  8. 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!

  9. 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!

  10. 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.

  11. 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.

  12. 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

  13. 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.

  14. Hey there! I just wanted to ask if you ever have any trouble with hackers?

    My last blog (wordpress) was hacked and I ended
    up losing several weeks of hard work due to no back up. Do you have any methods to stop hackers?

  15. Pretty nice post. I just stumbled upon your weblog and wanted to say that I have reallyenjoyed surfing around your blog posts. In any caseI will be subscribing to your rss feed and Ihope you write again very soon!

  16. [url=https://amoxicillin24.com/]amoxicillin 250mg[/url] [url=https://levitra100.com/]levitra generic[/url] [url=https://suhagra911.com/]suhagra 100[/url] [url=https://xenical365.com/]xenical otc australia[/url] [url=https://dapoxetine911.com/]dapoxetine buy online india[/url] [url=https://sildenafil48.com/]sildenafil prescription[/url] [url=https://tretinoin2019.com/]tretinoin prescription[/url] [url=https://metformin100.com/]metformin generic[/url] [url=https://synthroid100.com/]synthroid 100[/url] [url=https://azithromycin24.com/]azithromycin 250mg[/url]

  17. I know this if off topic but I’m looking into starting my own blog and was curious what all is required to get set up? I’m assuming having a blog like yours would cost a pretty penny? I’m not very internet savvy so I’m not 100 positive. Any suggestions or advice would be greatly appreciated. Thanks|

  18. First off I want to say wonderful blog! I had a quick question in which I’d like to ask if you don’t mind. I was curious to find out how you center yourself and clear your head before writing. I’ve had a hard time clearing my mind in getting my thoughts out. I do take pleasure in writing but it just seems like the first 10 to 15 minutes tend to be wasted just trying to figure out how to begin. Any suggestions or hints? Cheers!|

  19. You’ve made some really good points there. I checked on the net for additional information about the issue and found most individuals will go along with your views on this web site.|

  20. Excellent beat ! I would like to apprentice while you amend your web site, how can i subscribe for a blog site? The account helped me a acceptable deal. I had been a little bit acquainted of this your broadcast offered bright clear idea

  21. Interesting blog! Is your theme custom made or did you download it from somewhere? A theme like yours with a few simple tweeks would really make my blog stand out. Please let me know where you got your theme. Thanks|

  22. This is the perfect site for anyone who wishes to understand this topic. You realize so much its almost hard to argue with you (not that I really would want to…HaHa). You certainly put a new spin on a topic which has been discussed for many years. Great stuff, just great!|

  23. Hi there, You have performed a great job. I’ll certainly digg it and in my opinion suggest to my friends. I am confident they will be benefited from this site.|

Leave a Reply to rabbit vibrators Cancel reply

Your email address will not be published. Required fields are marked *