专栏文章

期望

2025/07/06 20:41个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论: 0 条
当前快照: 1 份
快照标识符: @mioyxl1p
此快照首次捕获于: 2025/12/03 03:25
此快照最后确认于: 2025/12/03 03:25

P1365

设 $dp[i]$ 表示第 $i$ 位的期望， $len$ 为最长的长度

当是 $s[i]$ 为 $o$ 时 $dp[i]=dp[i-1]+[(len+1)^2-len^2]$ $= dp[i-1]+len*2+1$ $len=len+1$

当是 $s[i]$ 是 $x$ 时 $dp[i]=dp[i-1]$ $len=0$ 当是 $?$ 时 $dp[i]=dp[i-1]+\frac {[(len+1)^2-len^2]+1+0}{2}$ $len=\frac {len+1}{2}$

这个

len

本质上就是最长长度的期望

同理CF235B

这道题有些变化，维护变成了三次方，一样考虑加上新增的贡献

dp[i]=dp[i-1]+[(len+1)^3-len^3]

=dp[i-1]+len^2*3+len*3+1

注意这里的

len

是长度的期望，所以不能直接用一次项的的平方来计算，而是要用上面的展开来计算

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...