题解 AT2170 【Pushing Balls】
litble
2018-10-19 16:35:53
[戳我= ̄ω ̄=](https://blog.csdn.net/litble/article/details/83089429)
我们来到操场的沙坑上,赶走在练习跳远的人,然后挖四个坑,然后找体育组借三个实心球放在四个坑直接,那么这些物品两两的初始距离是:
$d$,$d+x$,$d+2x$,$d+3x$,$d+4x$,$d+5x$
考虑一下不同的推球方法,当一个球进入一个坑后,就默不作声地用沙子将这个球埋起来,假装什么都没有发生过,将这些球重新编号。你会发现物品两两间距离有这么几种可能(表格头的编号是重编过的):
|情况|坑1与球1|球1与坑2|坑2与球2|球2与坑3|
|---|---|---|---|---|
|球1入坑1|$d+2x$ | $d+3x$ | $d+4x$ | $d+5x$ |
|球1入坑2|$3d+3x$ | $d+3x$ | $d+4x$ | $d+5x$ |
|球2入坑2|$d$ | $3d+6x$ | $d+4x$ | $d+5x$ |
|球2入坑3|$d$ | $d+x$ | $3d+9x$ | $d+5x$ |
|球3入坑3|$d$|$d+x$|$d+2x$|$3d+12x$|
|球3入坑4|$d$|$d+x$|$d+2x$|$d+3x$|
|期望|$\frac{8d+5x}{6}$ |$\frac{8d+15x}{6}$|$\frac{8d+25x}{6}$|$\frac{8d+35x}{6}$|
哇,好神奇啊,期望的物品间距离居然还是个等差数列~
你会对这个发现感到异常惊奇,但还是不要忘了把实心球挖出来还回去。
现在来观察,等差数列的第一项就是我们表格的**坑1与球1**这一列,你会发现不管初始用几个球,这一列只有前两行是$d+2x$和$3d+3x$,其他行都是$d$。所以$d'=d+\frac{2d+5x}{2n}$。至于公差,我们观察一下**球2与坑2**这一列,发现这一列的期望永远会是$d+x+\frac{2d+9x}{2n}$,所以公差$x'=x+\frac{4x}{2n}$。
这样我们做$n$次对$d$和$x$(其实还有$n$别忘了)的变换,即可得到答案。
oh,对,至于每种局面下的推球期望距离,应该是$d+\frac{2n-1}{2x}$,具体为什么自己推(zhǎo)一(guī)推(lǜ)吧。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define RI register int
typedef double db;
int n;db d,x,ans;
int main()
{
scanf("%d%lf%lf",&n,&d,&x);
db nn=n+n;
for(RI i=n;i>=1;--i) {
ans+=d+(nn-1)/2*x;
db dd=d+(2*d+5*x)/nn;
db xx=x+4*x/nn;
x=xx,d=dd,nn-=2;
}
printf("%.10lf\n",ans);
return 0;
}
```