首页 > 代码库 > bzoj4318 OSU!
bzoj4318 OSU!
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4318
【题解】
考虑连续的1的个数不好维护,我们维护每个点的贡献。
考虑当$i$选了1,才会有贡献,如果前面有$p$个连续的1,贡献是$(p+1)^3 - p^3 = 3p^2 + 3p + 1$。
设$i$前面连续的1的个数的期望为$x_i$,连续的1的个数的平方的期望为$y_i$。
考虑$x_i$,$y_i$的转移:
显然$x_i = (x_{i-1} + 1) * a_i$,$y_i = (y_{i-1} + 2x_i + 1) * a_i$。
那么每个点贡献$f_i = 3y_{i-1} + 3x_{i-1} + 1$,求和即可。
复杂度$O(n)$。
这道题算期望的方式很妙,分开来考虑每个点贡献。
# include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int N = 1e5 + 10; const int mod = 1e9+7; inline ld getld() { static double x; scanf("%lf", &x); return (ld)x; } inline void putld(const ld& x) { printf("%.1lf\n", (double) x); } int n; ld a[N], x[N], y[N], f[N]; int main() { cin >> n; for (int i=1; i<=n; ++i) a[i] = getld(); for (int i=1; i<=n; ++i) { x[i] = (x[i-1] + 1) * a[i]; y[i] = (y[i-1] + 2.0 * x[i-1] + 1) * a[i]; f[i] = (3.0 * y[i-1] + 3.0 * x[i-1] + 1) * a[i]; } ld ans = 0.0; for (int i=1; i<=n; ++i) ans += f[i]; putld(ans); return 0; }
bzoj4318 OSU!
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。