bzoj 3450 期望分数
2024-10-14 21:29:58
自己只能想到O(n^2)的:
dp[i][j] 表示 以i结尾,长度为j的o串的概率,然后在每次遇到x的时候算分数.
正解是:
dp[i]表示前i个的答案,d[i]表示以i结尾的期望长度.
推的时候它用d[i]*d[i]-d[i-1]*d[i-1]来算新增的贡献,有点不明白为什么可以这样(平方的期望应该不等于期望的平方才对吧).
哪天问问jason_yu.
这道题,假如我们已经确定了问号的内容,那么我们怎么求该种情况的分数的?
它等于:ans = sigma d[i]*d[i]-d[i-1]*d[i-1] ( if d[i]=d[i-1]+1 ) = sigma 2*d[i-1]+1 ( d[i+1]=d[i]+1 )
其中d[i]表示以i结尾的最长的o的长度,
所以本题答案就是 E( sigma d[i]*d[i]-d[i-1]*d[i-1] (d[i]=d[i-1]+1) ) = E( sigma 2*d[i-1]+1 (d[i]=d[i-1]+1) )
而上面那个d[i]=d[i-1]+1的等价条件是第i格不是x,这个可以在转移时候判断,于是答案变成了一些2*d[i-1]+1的期望的和.
最新文章
- 遍历Map的方法
- ubuntu下命令杂项
- Vim 强大的配置
- css3属性flex弹性布局设置三列(四列)分布样式
- 让Web API支持$format参数的方法
- C++ 创建和遍历二叉树
- Scrum项目5.0
- 在Ios里UIWebView参入js
- react与jQuery对比,有空的时候再翻译一下
- [statsvn]-svn代码量统计
- 文艺编程 Literate Programming
- ASP.NET网站运行常见错误以及解决方法(持续更新)
- JAVA框架面试题
- Dora.Interception,为.NET Core度身打造的AOP框架 [4]:与依赖注入框架的无缝集成
- Python字典(Dictionary)
- 1095 Anigram单词
- Basler和Matrox的配置及调试
- Kotlin语言学习笔记(3)
- 解疑网络监控卡壳 视觉体验400ms延时
- Failed to abandon session scope: Connection timed out