Agc007_C Pushing Balls

题目大意

在一条直线上有$N$个球和$N+1$个洞，每两个球之间有一个洞，每两个洞之间有一个球，最左端和最右端都是洞，其中产生的$2N$个间隔满足从左到右是等差数列。你每次随机选择一个未被推进洞的球，将它随机向左或向右推动直到遇见一个洞，这时求会滚进洞内填满这个洞，接下来的球会正常从这个洞上方经过，显而易见不会有球撞到球或走出边界的情况，求所有任一方案所有球移动距离的期望。

题解

人类智慧题

将题目转化为有$2N$个区间，每次可以拿走$2$个相邻的端点并获得端点距离的贡献

考虑移动一次后剩下的$2N-2$个区间，单独考虑每一个区间，假设第$1$个区间，设首项为$X$，公差为$K$。

若我们拿走$2N$个区间中的第$1$个，则第一个区间会从$X$增加为$X+2K$，即长度变成了原序列中的第$3$个区间。

若我们拿走$2N$个区间中的第$2$个，则第一个区间会从$X$增加为$3X+3K$，即长度变成了原序列中的前$3$个区间。

其余情况第一个区间不变，则第一个区间期望增加$\frac{2X+5K}{2N}$。

同理，发现每个区间变化的期望会形成一个等差数列，那么$2N-2$个区间仍然能构成一个等差数列。

我们只要不断维护这一等差数列，维护首项末项公差，每次对答案的贡献是首项与末项的平均数。

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

#define DB double

#define M 400020

using namespace std;

int read(){

	int nm=0,fh=1; char cw=getchar();

	for(;!isdigit(cw);cw=getchar()) if(cw=='-') fh=-fh;

	for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');

	return nm*fh;

}

LL n,tot,d[M];

DB ans,fs,ed,k,dt;

int main(){

	n=read(),fs=read(),k=read();

	ed=fs+k*(n*2-1);

	for(int i=(n<<1);i;i-=2){

		ans+=((fs+ed)/2.0);

		fs+=(fs*2+k*5)/(i*1.0); dt;

		ed+=dt=(ed*2-k*5)/(i*1.0); dt;

		if(i>2) k=(ed-fs)/((i-2)*1.0-1.0);

	}

	printf("%.17lf\n",ans);

	return 0;

}

巴特西

Agc007_C Pushing Balls

最新文章

热门文章