MX718 模拟赛记录

__ryp__ · 2024-07-18 15:36:26 · 个人记录

题目里头说 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 的欧拉回路。跑就完了。

题意：给定 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 的所有肯定也不选；反之不一定。

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