CSP-S 2024 简单题

以下均为考场做法。

T1 决斗 (duel)

考虑贪心，按照攻击力 \(a_i\) 排序，从小到大使用所有怪物进行攻击，每只怪物攻击一个在场且能击杀的怪物中，攻击力最大的一个。这样显然最优，因为每一次攻击都被完美的利用到了。

于是设 \(c_x\) 表示满足 \(a_i = x\) 的 \(i\) 的个数。按照 \(x\) 从小到大扫，维护一个变量 \(cnt\) 表示当前的怪物数量，初始为 \(0\)，每次相当于 \(cnt \gets \max(cnt - c_x, 0) + c_x\)。表示先用攻击力为 \(x\) 的怪物击杀其他怪物，再加入这些怪物。

这样也可以证明答案为 \(\max c_x\)。考查 \(c\) 的单调栈即可。时间复杂度 \(O(n)\)。

T2 超速检测 (detect)

首先考虑将物理问题转化为 OI 问题。对于每辆车 \(i\) 求一个 \([l_i, r_i]\)，表示 \(i\) 在路过第 \(l_i\) 至 \(r_i\) 个测速仪时超速，然后就比较好做了。

考场推法是这样的：一辆车，初始位置为 \(d\)，初速度为 \(v_0\)，加速度为 \(a\)，则 \(t\) 秒后速度为 \(v_t = v_0 + at\)，我们尝试写出一个方程 \(v_0 + at = V\)，然后一定是一段前缀或者后缀合法。

先判掉一些 \(\text{Corner Case}\)：若 \(v_0 > V\) 且 \(a > 0\)，则后面全部超速。若 \(v_0 \le V\) 且 \(a < 0\)，则永远不会超速。若 \(a = 0\)，则只需考察是否有 \(v_0 > V\)，同样可以规约到上面两种情况之一。

否则 \(v_0 +at = V\) 不会失效。解出 \(t = \frac{V - v_0}{a}\)。考虑在 \(0 \sim t\) 秒内的位移为 \(x = v_0t + \frac{1}{2} at^2\)。\(t\) 秒后位置为 \(d + v_0t + \frac{1}{2} at^2\)。代入 \(t\)，得到 \(d + v_0(\frac{V - v_0}{a}) + \frac{1}{2}a(\frac{V - v_0}{a})^2 = d + \frac{V^2 - {v_0}^2}{2a}\)，在测速仪的数组上二分这个位置即可。

最后考虑最前面讲的抽象问题怎么做。第一问显然是满足 \(l_i \le r_i\) 的 \(i\) 的个数。第二问考虑贪心，将所有区间 \([l_i, r_i]\) 按照右端点排序，每次能拖就拖，不能拖就在 \(r_i\) 处放一个测速仪，这个应该是简单的。

时间复杂度 \(O(n \log n)\)。

T3 染色 (color)

将红色和蓝色的涂色看成划分为两个子序列。容易想到设 \(f_{i, x, y}\) 表示，考虑了前 \(i\) 个位置，第一个序列结尾为 \(x\)，第二个序列结尾为 \(y\) 的最大收益。

由于两个序列不区分，且放完 \(i\) 时一定有一个子序列的结尾为 \(a_i\)，所以这个状态有一维是多余的，设 \(f_{i, x}\) 表示考虑前 \(i\) 个位置，一个序列结尾为 \(x\)，另一个序列结尾为 \(a_i\) 的最大收益即可。

考虑 \(f_{i, x}\) 到 \(f_{i + 1, y}\) 的转移，有两种可能：

• \(a_{i + 1}\) 和 \(a_i\) 在一个子序列，则这一步的收益为 \([a_{i + 1} = a_i] a_{i + 1}\)，这是一个只与 \(i\) 有关的值。
• \(a_{i + 1}\) 和 \(x\) 在一个子序列，则这一步的收益为 \([a_{i + 1} = x] a_{ i + 1}\)。

对于第一种转移，相当于一个全局加。对于第二种转移，注意到对于任意的 \(x\) 都会转移到 \(f_{i + 1, a_i}\)，则我们只关心值最大的那个。分类讨论，\(a_{i + 1} = x\) 的情况只需做单点查。而 \(a_{i + 1} \neq x\) 的情况我们只关心全局 \(\max\)。于是对全局加打 \(tag\)，然后维护全局 \(\max\) 即可。

时间复杂度 \(O(n \log n)\)，其中 \(\log n\) 仅用于离散化。