题解 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;
}
```