AGC007C Pushing Balls —— 期望的神题
2024-10-20 16:24:06
题意: 序列上按顺序交错有 \(n\) 个球和 \(n+1\) 个洞,即 \(hole_1,ball_1,hole_2,ball_2,\dots,ball_n,hole_{n+1}\),相邻两个位置的距离形成一个首项为 \(s\) 公差为 \(d\) 的等差数列,接下来有 \(n\) 次操作,每次操作会随机选一个球并将其随机向左推或向右推。容易发现最后每个球都会滚进一个洞中。求所有球滚动的总距离的期望。
发现 1:所谓的等差数列可以转化为每个距离都相同。
注意到对于任意一种推球的方式,考虑与它恰好对称的推球方式,可以发现,对于每个球来说,它们在两次推球的过程中走过距离的平均值为一定值 \(s+(n-1)/2*d\)!于是可以认为每相邻两个位置的距离均为此定值。
发现 2:对于各种情况,可以将每个位置的距离取期望后再进行计算。
注意到总期望距离可认为 \(\sum_{state} p_{state}d_it_i=\sum_i E[i]t_i\),其中 \(t_i\) 为每个状态中 \(i\) 被覆盖的次数,\(p_{state}\) 为状态 \(state\) 出现的概率,\(d_i\) 为该状态中空隙 \(i\) 的距离。于是这个距离可以期望化。
通过以上两个发现,可以注意到每次操作后仍然可以转化为每个空隙都有一个期望,发现除了首尾以外所有空隙期望长度均相同,且首尾两个空隙平均下来也是对的,就可以视为所有位置长度都相同,随便推推狮子即可。
时间复杂度 \(O(n)\)。
本题两个发现可谓精妙绝伦啊~~~
最新文章
- MySQL主从复制(Master-Slave)与读写分离(MySQL-Proxy)实践
- window 内核详尽分析
- [转]HTTPS那些事(一)HTTPS原理
- MYSQL 博客
- SQL Server 跨库连接
- perl 递归地遍历目录下的文件
- 文件打包bundle
- 局域网连接SQL Server数据库配置
- poj2155一个二维树状数组
- 配置web.xml文件用于配置tomcat
- 带你深入理解STL之Stack和Queue
- 配置vscode同步大神玺哥的配置
- Mybatis Hibernate->;MyBatis
- python 闭包用法
- es修改数据类型
- swftools安装教程
- C#Redis初识
- Spark GraphX实例(1)
- 【算法】MD5加密
- Windows:删除图标缓存
热门文章
- OpenJ_Bailian - 3424 Candies (差分约束)
- HTTP协议,会话跟踪,保存作用域,servlet类跳转
- 从0到1写一款自动为Markdown标题添加序号的Jetbrains插件
- qt调用quit()后未结束线程解决方案
- openstack中Keystone组件简解
- PostgreSQL 大对象导出报错问题分析
- 如何在JavaScript中使用高阶函数
- Job for redis-server.service failed because the control process exited with error code(Centos 7 设置Redis开机自启报错)
- ProxySQL 防火墙白名单
- logstash另类输出到es