AGC028 B Removing Blocks

题面

给出一个序列,每个点都有一个权值,一开始他们都是连通的。

Snuke将执行以下操作N次:

  • 选择一个点并将其移除,移除这个点所用的代价为此时他所在的块内所有点的权值和(包括自己),将这个点移除之后原本所在的块会因为其被删除而被分成两个块。

对于所有可能的 $N!$ 个选择方案,算出他们的代价总和。
继续阅读

BZOJ4720 换教室

题解

发现是一个比较简单的期望dp题,一开始想用一个状态$f[i][j]$表示前$i$个数取$j$个的期望,然后用一个数组记录是否申请以帮助转移,后来发现实际上如果某一个状态选择申请,那后面的状态也可能由当前状态的不申请情况转移过来,那也可以比较简单的设计新状态,$f[i][j][0/1]$,第三位表示当前状态选/不选的期望。
继续阅读

BZOJ4318 OSU!

题意

给定一个序列,每个位置为 $\texttt{o}$ 的几率为 $p_i$ ,为 $\texttt{x}$ 的几率为 $1 – p_i$ 。对于一个 $\texttt{ox}$ 序列,连续 $x$ 长度的 $\texttt{o}$ 会得到 $x^3$ 的收益,问最终得到的 $\texttt{ox}$ 序列的期望收益是多少?

题解

这题和20181106的考试题很像( $x^2$ 变成了$x^3$),属于升级版,和BZOJ3450有一定联系。
可以将题目转化一下,变成以每个点为右端点的区间长度的期望的立方的和。
设 $g[i]$ 为以 $i$ 位置为右端点的的期望的立方的和。
继续阅读