【CF601C】Kleofáš and the n-thlon
Description
大概是说\(m\)个人参加\(n\)场比赛,每场一人有一个排名,每场没有两个人排名相同,一个人最后的得分是\(n\)场比赛的排名相加,现在已知其中一个人(叫做\(A\)好了)\(n\)场比赛的排名,求最后按照得分降序排列后,这个人的期望排名
Solution
这题一开始有点无从下手(流下蒟蒻的泪水)
那。。冷静分析一波,首先我们要求的答案应该是:总分\(<=\)自己得分(记为\(score\)好了)的期望人数+1
然后因为除去\(A\)这个人,其他的\(m-1\)个人的情况是相同的,期望人数可以由:概率*(m-1)来得到
那所以我们现在就只考虑一个人(剩下的\(m-1\)个人中的一个),要求这个人总分\(<=score\)的概率
我们记\(f[i][j]\)表示这个人经过\(i\)场比赛之后,总分为\(j\)的概率,那么我们可以得到转移式子:
\]
这里的\(rank[i]\)表示的是\(A\)在第\(i\)场比赛中的排名,这个转移的具体意义就是枚举这个人在第\(i\)场的排名,然后上界为\(min(m,j)\)是因为只有\(m\)个人,\(k!=rank[i]\)是因为没有两个人在同一场排名相同,所以这个人的排名不能是\(A\)在这场的排名
具体怎么求的话,我们可以把这个东西写成一个前缀和的形式,我们多开一个数组\(sum[i][j]=\sum\limits_{k=0}^{j-1}f[i][j]\),特别的所有的\(sum[i][0]=0\)
然后前缀和一下再把\(f[i][rank[i]]\)减掉就好了,最后的答案就是\(sum[n][score]*(m-1)+1\)
空间比较大所以可以考虑滚动数组,然后如果我没用long double的话。。好像会爆精度qwq可能是因为写挫了qwq(以及因为某种奇怪的原因cf上面好像。。直接printf一个long double会出锅qwq)
代码大概长这个样子
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=110,MX=100010;
long double p[2][MX],sum[2][MX];//sum[x]=\sum_{i=0}{x-1} p[i]
int rk[N];
int n,m,score;
int main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
#endif
scanf("%d%d",&n,&m);
score=0;
for (int i=1;i<=n;++i) scanf("%d",rk+i),score+=rk[i];
int pre=0,now=1,l,r;
p[0][0]=1;
for (int i=1;i<=n*m;++i) sum[0][i]=1;
if (m==1){printf("%d\n",1);return 0;}
for (int i=1;i<=n;++i){
memset(p[now],0,sizeof(p[now]));
sum[now][0]=0; sum[now][1]=0;
for (int j=1;j<=n*m+1;++j){
l=max(0,j-m),r=j;
p[now][j]+=(sum[pre][r]-sum[pre][l])/(1.0*(m-1));
if (j-rk[i]>=0)
p[now][j]-=p[pre][j-rk[i]]/(1.0*(m-1));
sum[now][j+1]=sum[now][j]+p[now][j];
}
swap(now,pre);
}
printf("%.15Lf\n",sum[pre][score]*(m-1)+1.0);
}
最新文章
- RabbitMQ Config
- 将博客搬至CSDN
- 第8章 文件系统管理(2)_挂载、fdisk分区及分配swap分区
- 第三篇——软件之殇,WE ARE THOUSANDS APART!
- seajs模块化作用理解(一句话)
- 利用UIActivityController调用ios系统自带的分享功能,实现微信发布多图的功能
- java complier compliance level问题引发的思考
- POJ 1699 Best Sequence(DFS)
- 第四篇、Tomcat 集群
- Java IO 概述
- 用邻接表实现DFS和BFS
- js 获取页面可视区域宽高
- net core 安装web模板
- 学习了解 Exchanger - 实现生产者消费者模型
- mac查看当前调用tcp的进程并关闭指定进程
- redis互斥锁简易设计原理【原】
- POJ 3264 Balanced Lineup(模板题)【RMQ】
- Centos7 Mysql5.7主从服务器配置
- java中的内存模型
- Android(或者Java)通过HttpUrlConnection向SpringMVC请求数据(数据绑定)
热门文章
- Unity —— 通过鼠标点击控制物体移动
- Hyperledger Fabric CouchDB as the State Database——使用CouchDB
- 做程序开发的你如果经常用Redis,这些问题肯定会遇到
- scrapy+selenium+chromedriver解析动态渲染页面
- Amazon Headlines Update on Activity in US West Coast Ports
- 直接抱过来dd大牛的《背包九讲》来做笔记
- CSS3:不可思议的border属性
- bat获取当前日期的前一天
- 【BioCode】将多个蛋白质序列分成单个的txt文档
- 使用Log4在测试过程中打印执行日志 及配置log4j.properties!