BZOJ 2720: [Violet 5]列队春游
2021/5/24 10:58:11
本文主要是介绍BZOJ 2720: [Violet 5]列队春游,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
概率和期望+组合数学
这个题有On,n2,n3的做法,这里主要说一下n的线性做法。
我和chy研究了无数题解才明白
根据期望的线性性,枚举每种可能的视野,把期望分解成 每种视野的视野长度×这种视野的概率
就是 $\sum_{i=1}^n i\times P(i) $
然后我们可以给他做一个转化,看这个图
上面的公式相当于每次加一列,我们发现一行也是有序的,所以我们把他转化成累加每一行
就是\(\sum_{i=1}^n P(L>=i)\)
这个式子的含义就是对于每个i,视野长度不小于i的概率之和,然后再求和
我们可以根据每个视野枚举,先预处理出比它小的视野数(就是身高严格小于他的人数)s,然后对于每个视野就有
解释一下,相当于至少有s-1个排在他前面,从n个里面选s-1个,剩下的(除了他自己)乱排,最后把它和他前面的比它小的看成一个整体往里面插,就是乘s,除以全排列就是视野长度不小于i的概率。
这个式子显然可以化简,最后对于每个i的贡献是\(ans(i)=\frac{n+1}{n-s+1}\),过程不说了,根据排列组合公式展开上下消就行。
代码不长,重在理解
#include <bits/stdc++.h> using namespace std; int h[305];double d[305]; int main() { int n; cin>>n; for(int i=1;i<=n;i++) scanf("%d",&h[i]); sort(h+1,h+n+1); for(int i=1;i<=n;i++) { if(h[i]==h[i-1])d[i]=d[i-1]; else d[i]=i-1; } double ans=0; for(int i=1;i<=n;i++) ans+=(n+1)/(n-d[i]+1); printf("%.2lf",ans); return 0; }
这篇关于BZOJ 2720: [Violet 5]列队春游的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)