Codeforces Round #604 (Div. 1)

前言

离橙名最近的一场

题解

A - Beautiful Regional Contest

金牌只给题数最多的，然后尝试把剩下两组分成两份，每一份都比金牌人数多。

B - Beautiful Sequence

左边 $12$ 中间 $23$ 右边 $34$ 这样构造。

C - Beautiful Mirrors with queries

令 $dp[i]$ 表示为从 $i$ 到 $n+1$ 的期望天数。

$dp[1]=p_1*dp[2]+(1-p_1)*dp[1]+1$ ，那么显然后 $dp[2]=dp[1]-\frac{1}{p_1}$
$dp[2]=p_2*dp[3]+(1-p_2)*dp[1]+1$ ，显然有 $dp[3]=dp[1]-\frac{1}{p_1p_2}-\frac{1}{p_2}$
规律显然， $dp[n+1]=0=dp[1]-\frac{1}{p_1...p_n}-\frac{1}{p_2...p_n}...-\frac{1}{p_n}$
修改无非就是把一个段切成很多个段，分别求上述值然后求和。预处理后缀积及其后缀和，用 $set$ 即可维护。