bzoj4318OSU &tyvj1952 Easy
2024-10-11 21:05:12
之前做tyvj1952Easy(给定一个序列,每个位置有一定的概率是1或0,求极长连续1的长度平方期望),用的做法是求出“全1子串的期望个数”.假如每一段极长连续1分别长x1,x2,x3…要求的答案为sigma{xi^2},全1子串的期望个数即为sigma{(xi+1)*xi/2},和sigma{xi}的期望(即1的个数的期望)加加减减就出来答案了。
Bzoj4318的题意同上,不过要求立方和的期望。做法是分别考虑每个位置的期望贡献。
即:111后加一个1的贡献为4*4-3*3=7,1111后加一个1的贡献为5*5-4*4=9
也就是说,在一段长度为x的1后面加一个1,贡献为(x+1)^3-x^3=3*x^2+3^x+1,只要算出在每个位置结尾的全1子串的长度期望和长度平方的期望即可。而全1子串的长度平方期望也可以考虑每个1的期望贡献2x+1,由长度的期望推出即可。
那么Tyvj1952也可以分别考虑每个位置的期望贡献(x+1)^2-x^2=2x+1了,只要维护在每个位置结尾的全1子串期望长度即可。
#include<cstdio> #include<cctype> int main(){ int n;scanf("%d",&n); char ch; double x1=,x2=,p; for(int i=;i<=n;++i){ while(ch=getchar(),!isgraph(ch)); if(ch=='?')p=0.5; else if(ch=='o')p=; else p=; x2+=p*(*x1+); x1=p*(x1+); } printf("%.4f\n",x2); return ; }
#include<cstdio> int main(){ int n;scanf("%d",&n); double x1=,x2=,x3=;//结尾连续长度的一次方和平方的期望以及总共的长度立方的期望 double x; for(int i=;i<=n;++i){ scanf("%lf",&x); x3+=(*x2+*x1+)*x; x2=x*(x2+*x1+); x1=x*(+x1);//x的概率,x1长度变为 x1+1;(1-x)的概率,长度变为0 } printf("%.1f\n",x3); return ; }
最新文章
- Hibernate学习之——搭建log4j日志环境
- 神奇的Bank系统之旅哦
- verilog阻塞与非阻塞的初步理解(三)
- sql server 2008 提示评估期已过的解决方法(升级无效)
- linux服务开机启动顺序
- js控制页面的全屏展示和退出全屏显示
- 用PHP尝试RabbitMQ(amqp扩展)实现消息的发送和接收
- zoj 1760 floyd构图+Dinic最大流
- PHP中统计目录中文件以及目录中目录的大小
- Firemonkey使用iOS的第三方静态库(Link Binary With Libraries)
- THML结构语义化之table/form
- tomcat 7 启动超时设置。。。实在太隐蔽了
- DHCP和TFTP服务
- 逆向---02.je &; jmp &; jnz 、OD调试
- 0x17二叉堆之超市
- leetcode1004
- linux命令学习之:rm
- 2019.01.02 bzoj3513: [MUTC2013]idiots(fft)
- 结对&;词频统计
- pandas练习(一)------ 了解数据
热门文章
- c#描述异常处理语句try、catch、finally执行时的相互关系
- Linux Linux程序练习十三(信号阻塞,捕获)
- Linux shell基础
- 【转】加快网站访问速度——Yslow极限优化
- 在线音乐网站【04】Part two 功能实现
- Pattern Recognition And Machine Learning读书会前言
- 理解JavaScript中的参数传递 - leetcode189. Rotate Array
- Android Stduio统计项目的代码行数
- 使用spring boot和thrift、zookeeper建立微服务
- [C#解惑] #2 对象的初始化顺序