洛谷P1654 OSU! 题解

题目链接：P1654 OSU!

题意：

osu 是一款群众喜闻乐见的休闲软件。

我们可以把osu的规则简化与改编成以下的样子:

一共有 $n$ 次操作，每次操作只有成功与失败之分，成功对应 $1$ ，失败对应 $0$ ，$n$ 次操作对应为 $1$ 个长度为 $n$ 的 01 串。在这个串中连续的 $X$ 个 $1$ 可以贡献 $X^3$ 的分数，这 $X$ 个 $1$ 不能被其他连续的 $1$ 所包含（也就是极长的一串 $1$ ，具体见样例解释）

现在给出 $n$ ，以及每个操作的成功率，请你输出期望分数，输出四舍五入后保留 $1$ 位小数。

输入格式：

第一行有一个正整数 $n$ ，表示操作个数。接下去 $n$ 行每行有一个 $[0,1]$ 之间的实数，表示每个操作的成功率。

输出格式：

只有一个实数，表示答案。答案四舍五入后保留 $1$ 位小数。

数据范围：

$1 \le n \le 10^5$

显然期望dp。但是这个贡献不太好计算。

因为它是一个整体去算的，而 dp 的过程中整体的信息会丢失。

因此我们考虑增加一个 $1$ 对原来的串的贡献。

$$\Delta = (x+1)^3 - x^3=3x^2 + 3x + 1$$

二项式定理易得上式。因此我们可以记录 $f_i,g_i,h_i$ 分别标记 $x,x^2$ 每一维的期望以及答案，则

$$f_i = (f_{i-1} + 1)\times p_i \\g_i = (g_{i-1} + 2f_{i-1} + 1)\times p_i \\h_i = h_{i-1} + (3g_{i-1}+3f_{i-1}+1)\times p_i$$

最后答案就是 $h_n$ 。时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5+15))

int n;
double p[N],x1[N],x2[N],ans[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1; i<=n; i++) cin >> p[i];
    for(int i=1; i<=n; i++)
    {
        x1[i] = (x1[i - 1] + 1) * p[i];
        x2[i] = (x2[i - 1] + 2 * x1[i - 1] + 1) * p[i];
        ans[i] = ans[i - 1] + (3 * (x1[i - 1] + x2[i - 1]) + 1) * p[i];
    }
    cout << fixed << setprecision(1) << ans[n] << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/blog/1215365487zyc/solution-p1654