• 周五. 4月 26th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

【YBTOJ】【CF235B】【Luogu P1365】Let's Play Osu!

admin

11月 28, 2021

题目大意:

(n) 次点击要做,成功了就是 o,失败了就是 x,分数是按 combo 计算的,连续 (a) 个 combo 就有 (a imes a) 分,combo 就是极大的连续o

思路:

(f_i) 表示前 (i) 秒期望分数,(g_i) 表示前 (i) 秒期望连续 combo。

方程显然:

[g_i=(g_{i-1}+1)p
]

[f_i=f_{i-1}+left((g_{i-1}+1)^2-{g_{i-1}}^2ight)p=f_{i-1}+(2g_{i-1}+1)p
]

(p) 表示当前为 o 的概率。

代码:

const int N = 100010;

int n;
double x, f[N][2];

int main()
{
	scanf ("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf ("%lf", &x);
		f[i][0] = f[i - 1][0] + (2 * f[i - 1][1] + 1) * x;
		f[i][1] = (f[i - 1][1] + 1) * x;
	}
	printf ("%.15lf", f[n][0]);
	return 0;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注