本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-18 15:36:26

7 月 18 日模拟赛

A

题目里头说 $S_i = 1$ 当且仅当 $i \equiv b \pmod m$，我们就知道一个串中如果两个 $1$ 的距离不是 $m$ 就肯定无解。场上没有理解这个充要条件，以为是必要，被捆爆了。

判完段内的无解，我们就把问题转化为了：对于每个 $S_i$ 有一个 $z_i$ 表示其第一个 $1$，这显然是小于 $m$ 的。我们于是建出 $[0, m)$ 的所有点，表示当前长度模掉 $m$ 的值。

对于每一个串，我们需要从 $b - z_i \bmod m$ 转移过来，然后转移到 $b - z_i + \lvert S\rvert\bmod m$。

于是问题就转化为了一条从 $0$ 到 $0$ 的欧拉回路。跑就完了。

B 跳蚤市场

题意：给定 $l_i, r_i, v_i$，对方可任取 $w_i\in [l_i, r_i]$，我们可以选一个集合 $S$，这之后 $v_i$ 被选中的概率是

$$\dfrac {w_i}{w_0 + \sum_S w_i}$$

我们要求最大化这个 $v_i$ 的总期望。

我们考虑如果选某个数 $j$ 更优，就说明

$$\dfrac{\sum_S v_iw_i}{\sum_S w_i} \lt \dfrac{\sum_S v_iw_i + v_jw_j}{\sum_S w_i + w_j}$$

整理一下得到

$$\dfrac{\sum_S v_iw_i}{\sum_S w_i} \lt v_j$$

非常美妙的柿子！我们于是得知，如果 $v_i$ 不能选，那么小于 $v_i$ 的所有肯定也不选；反之不一定。

因为值域小，我们可以用线段树二分来完成。

C 约会