首页 > 其他分享 >列队春游|概率期望|题解

列队春游|概率期望|题解

时间:2024-05-29 20:01:14浏览次数:23  
标签:PP 题解 305 len 春游 ti 列队 now define

题面

image
image
image
image

解析

前言,此处所述为\(O(n^2)\)算法,暂时未推出\(O(n)\)的算法,后续可能会更新。
题意非常明白,不多赘述。
我们去考虑单个位置的概率,维护每个人放在该位置对该位置期望的贡献。
以这个思想作为切入点,我们思考,对于一个序列来说,如果它的长度是定的。
设总人数为n,当前我们考虑的人是now,身高用h[]表示,小于等于他身高的人数用ti[]维护。
我们要维护某一个人的视野严格扩展到len的概率&&期望,毕竟我们是要去算对应点的期望的,若概率为PP[],期望为E[]。
用ed[]去存储这个人最长的视野(=1+ti[h[now]-1]).
则\(E[now][len]=len×PP[now][len]\)
在这个时候也可以知道,我们这个人now搁在某个点i处时,当其左侧人数大于等于比其矮的人数,设该点期望为F[].
则\(F[i]=Σ^{now=1}_ {n}(len/n×Σ_{ti[h[now]]}^{len=1}E[now][len])\)
对于一个人now,它能够看到前方视野长为>=len时,概率为P[]。
则\(P[now][len]=A_{ti[h[now]-1]}^{len=1} /A_n^{len}\)
为什么要这个式子,思考在我们把这个人放到某个位置上时,如果他左边的人数k小于等于比这个人小的人的数量。
那么这时我们只用让这些在他左侧的人比他小就好,也就是说,我们这个时候计算长度==k的概率,他是等于我们上面的这个P[]的(因为剩余位不必考虑,不用拿一个比他高的人管住边界)
所以这个P就可以用来处理部分边界问题,上面那个E的表达式就可以通过这个去扩展。
\((ti[h[now]]>=len)E[now][len]=len×PP[now][len]\)
\((ti[h[now]]<len)E[now][len]=len×P[now][len]\)
现在所有东西的未知量只剩下PP[],考虑到这个视野情况事件组内部互斥。
所以\(PP[now][len]=P[now][len]-P[now][len+1]\)
(注:这个式子是自己后面推出来的,还有一种表达方式是从其定义入手,
\(PP[now][len]=P[now][len]×(n-ti[h[now-1]]-1)/(n-len-1)\),代码中用的是这个)
这样我们可以发现,如果依着这个打法维护好这些量之后,这个算法复杂度是\(O(n^3)\).
(注:三层循环,一层是位置,一层是人,一层是视野范围)
这不太理想,虽然说这个数据范围他是允许实现的。
所以考虑优化,我们思考其实一个人放在不同位置他在不受限制时他提供给一点的期望是固定的。
那么我们可以维护一个类似前缀和的算法,我们考虑用EE[]去维护它。
那么\(EE[now][len]=Σ_{len}^{k=1}E[now][k]\)
但是仔细一想,这样怎么处理他左边人数比他小的情况?那就再来个EEE[]数组维护吧。
\(EEE[now][len]=EE[now][len-1]+P[now][len]×len\)
这样,我们的F[]的转移式子就变成了:
\(F[i]=Σ^{now=1}_ {n}EEE[now][min(ed[now],len)]\)
\(ans=Σ^{i=1}_ {n}F[i]\)
方法比较蠢,但问题确实解决了。

#include<bits/stdc++.h>
#define ll long long
#define qr qr()
#define pa pair<int,int>
#define fr first
#define sc second
#define lc tree[rt].ls
#define rc tree[rt].rs
using namespace std;
const int N=2e5+200;
int n,num[N],tot,head[N],ti[1050],ed[305];
long double f[305],p[305][305],ans,pp[305][305],e[305][305],ee[305][305],eee[305][305];
struct node{
  int t,w,nx;
}edge[N];
struct What_can_I_say{
  int ls,rs,l,r,mx;
}tree[N<<2];
inline int qr
{
  int x=0;char ch=getchar();bool f=0;
  while(ch>57||ch<48)
  {
    if(ch=='-')f=1;
    ch=getchar();
  }
  while(ch<=57&&ch>=48)x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
  return f?-x:x;
}
void add(int f,int t,int w)
{
  edge[++tot]={t,w,head[f]};
  head[f]=tot;
}
void init()
{
	n=qr;
	for(int i=1;i<=n;++i)num[i]=qr,++ti[num[i]];
	for(int i=1;i<=1000;++i)ti[i]+=ti[i-1];
	for(int now=1;now<=n;++now)ed[now]=1+ti[num[now]-1];
	for(int now=1;now<=n;++now)
	{
		p[now][1]=1;
		pp[now][1]=1;
		for(int len=2;len<=ed[now];++len)
		{
			p[now][len]=p[now][len-1]*(ti[num[now]-1]-len+2);
			p[now][len]/=(n-1-len+2);
			if(n-ed[now])
			{
				pp[now][len]=p[now][len]*(n-ti[num[now]-1]-1)/(n-len);
				pp[now][1]-=pp[now][len];
			}
		}
		for(int len=1;len<=ed[now];++len)
		{
			e[now][len]=pp[now][len]*len;
			if(ed[now]^n)
			{
				ee[now][len]=ee[now][len-1]+e[now][len];
				eee[now][len]=ee[now][len-1]+p[now][len]*len;
			}
			else eee[now][len]=len,ee[now][len]=len;
		}
	}
	for(int i=2;i<=n;++i)
		for(int now=1;now<=n;++now)
			f[i]+=eee[now][min(ed[now],i)];
	for(int i=2;i<=n;++i)ans+=f[i];
	printf("%.2Lf",ans/n+1);
	// for(int i=1;i<=n;++i)printf("%.2Lf ",ee[i][1]);
	// 	putchar('\n');
	// for(int i=1;i<=n;++i)printf("%.2Lf ",ee[i][2]);
	// 	putchar('\n');
	// for(int i=1;i<=n;++i)printf("%.2Lf ",ee[i][3]);
	// 	putchar('\n');
	// for(int i=1;i<=n;++i)printf("%.2Lf ",pp[i][1]);
	// 	putchar('\n');
	// for(int i=1;i<=n;++i)printf("%.2Lf ",pp[i][2]);
	// 	putchar('\n');
	// for(int i=1;i<=n;++i)printf("%.2Lf ",pp[i][3]);
	// 	putchar('\n');
	// for(int i=1;i<=n;++i)printf("%.2Lf ",p[i][1]);
	// 	putchar('\n');
	// for(int i=1;i<=n;++i)printf("%.2Lf ",p[i][2]);
	// 	putchar('\n');
	// for(int i=1;i<=n;++i)printf("%.2Lf ",p[i][3]);
	// 	putchar('\n');
}
int main()
{
  #ifndef ONLINE_JUDGE
  freopen("in.in","r",stdin);
  freopen("out.out","w",stdout);
  #endif
  init();
  return 0;
}

标签:PP,题解,305,len,春游,ti,列队,now,define
From: https://www.cnblogs.com/shining-like-stars/p/18220003

相关文章

  • 【23NOIP提高组】题解
    T1:词典 #include<bits/stdc++.h>usingnamespacestd;inlineintread(){ intx=0,f=1;charch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9�......
  • P10528 [XJTUPC2024] 崩坏:星穹铁道 题解
    头图无语了,猜猜WA哪了不要真头图崩坏:星穹铁道题链这么简单做不对不许玩崩铁!题目大意给你行动的总次数\(n\)和初始战技点数量\(k\),以及编队里四名角色的行动类型,求不同行动方式的方案数。类型如下:思路先考虑dp,分角色类型讨论。设\(f_{i,k}\)表示第\(i......
  • [BZOJ2720 Violet 5]列队春游(概率期望+组合数学)
    列队春游问题描述输入格式:输出格式:样例输入:3123样例输出:4.33提示思路根据期望的线性性质,我们可以枚举每种可能的视野,然后求和对于每种视野,其期望为该种视野的视野长度*该种视野的概率设某个小朋友的视野期望为\(ans\),她的视野长度为\(L\)由于前面......
  • DockerDesktop中启动jenkins容器时提示:Can not write to /var/jenkins_home/copy_ref
    场景Windows10(家庭版)中DockerDesktop(docker)的配置、安装、修改镜像源、使用:https://blog.csdn.net/BADAO_LIUMANG_QIZHI/article/details/139264096按照以上教程搭建之后想要运行jenkins容器,所以执行如下指令dockerrun-d--namejenkins-p18088:8080-v/jenkinshome:......
  • CCF-CSP真题《202403-1 词频统计》思路+python满分题解
    哇q(≧▽≦q),第一次写博客,请大家多多关照○| ̄|_ 看到没啥人提供202403的第一题解题思路及python代码,刚好写完,心血来潮想分享解题思路,就写下了这篇博客,有其他的编码版本,欢迎大家一起探讨呀(虽然我是算法菜鸟┗(T﹏T)┛,但有问题,我会尽力回答的!!!)好了废话不多说,上解题思路!大概想了......
  • P6049 燔祭 题解
    题意:计算满足如下条件的带标号有根树数量:这棵树一共有\(n\)个节点。每个节点都有一个整数权值,且在区间\([1,m]\)内。每个节点的权值都不大于其父节点的权值。\(n,m\le400\)思路:好题。对于这种计数问题,肯定第一眼会想到\(dp\),我们设\(f_{n,m}\)表示\(n\)个点......
  • ICPC2024昆明邀请赛 J The Quest for El Dorado 题解
    QuestionTheQuestforElDorado有一个王国,有\(n\)个城市和\(m\)条双向铁路连接这些城市。第\(i\)条铁路由第\(c_i\)家铁路公司运营,铁路的长度为\(l_i\)。你想要环游这个国家,从城市\(1\)出发。为了你的旅行,你购买了\(k\)张火车票。第\(i\)张火车票用两个整数\(......
  • 题解/算法 {C. Goose Goose Duck}
    题解/算法{C.GooseGooseDuck}@LINK:https://codeforces.com/gym/105184;令A[N]表示这N个人的区间;比如答案是[a,b,c,d]那么他一定满足:A[a].lef<=0<=A[a].rig,A[b].lef<=1<=A[b].rig,A[c].lef<=2<=A[c].rig,…贪心;对于最开头的人来说,令集合S:......
  • 题解/算法 {J - Iris‘ Food}
    题解/算法{J-Iris’Food}@LINK:https://codeforces.com/gym/105184;比如最终答案是:10...01...12...23...3,则其值为1*10^?+(1...1)*10^?+(2...2)*10^?...;因此,如何求2....2这个值(长度为1e9),使用矩阵优化DP,DP定义为:DP[i]:长度为i的2...2的大......
  • 【问题解答】渲染农场的 10 个常见问题,助您轻松上手
    渲染农场是3D动画和效果图设计领域的强大工具。它们提供使复杂场景和动画所需的计算能力。在本文中,小编将解答有关渲染农场的10个常见问题,为初学者和经验丰富的专业人士提供见解和指导。1.渲染农场值得吗?渲染农场有多种益处,尤其是在提高3D项目的效率和节约成本方面。这里以......