AGC007C Pushing Balls
题意:\(N\)个坑,\(N+1\)个球,相间分布,距离为以\(d_1\)为首项,\(x\)为公差的等差数列。对于每次操作,随机选择一个未入坑的球,随机选择向左或向右,掉入第一个没有球的坑,定义一次操作的价值为球移动的距离。求\(N\)次操作的期望总价值。
分析:这是一道很好的期望题
其实\(idea\)还是比较妙的。
考虑转化问题:有\(2N+1\)个物品,每次随机删去相邻两个,求距离和的期望。
然后我们发现,若干次操作后段长仍为等差数列。
这个感性认知一下吧(能感觉到的请忽略这一段),初始时对于每个长为\(d_1+kx\)的段,删去两点后该段长度为\(3d_1+3kx\),那么所有非边界的两点删去后的长度为\(3d_1, 3d_1+3x,\dots,3d_1+3(2n-1)x\),加上任意两点删去可能性相当,所以第一次操作后仍是等差数列。然后后面肯定也是了对吧。
然后我们计算每一次操作后(当前有\(2N\)个点)的首项与公差的期望。
首项有三种可能:
1、删除编号为1、2的点,首项为\(d_1+2x\)
2、删除编号为2、3的点,首项为\(3d_1+3x\)
3、其他情况首项不变为\(d_1\)
根据全期望公式得到
\(d_1^{'}=\frac{1}{2n}*(d_1+2x)+\frac{1}{2n}*(3d_1+3x)+\frac{2n-2}{2n}*d_1\)
\(=\frac{(2n+2)d_1+5x}{2n}\)
公差有两种可能:
1、该段长不变为\(x\)
2、该段被取走为\(3x\)
\(x^{'}=\frac{(n+2)x}{2n}\)
每次计算答案即可
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
double n, a, x, ans=0.0;
cin >> n >> a >> x;
for (; n; n--)
{
ans+=a+(2*n-1)/2*x;
a=((2*n+2)*a+5*x)/(2*n);
x=(n+2)*x/n;
}
printf("%.10f\n",ans);
return 0;
}
转载于:https://www.cnblogs.com/ACMSN/p/10165611.html