Day -∞

作为一个半路出家，$\text{whk} \gg \text{OI}$ 的人，停课是不可能停课的，这辈子都不可能停课的。只能在作业比较少的时候翘掉晚自习这样子。
Day -7 模拟 240.

前

监考老师不让带可乐。
考场有没开空调。
热死了。
后来监考老师给我拿了水。不过这是后话。

T1

一眼排序，贪心易证，解法显然。 但是也花了十几分钟，别问，问就是之前忘了处理相等的情况。

T2

第一眼看到第二问，这不是著名 NP-Hard 问题集合覆盖吗？ 于是去看 T3 了。 后来猛地一看样例解释，哦，区间覆盖啊，那没事了。 于是兴冲冲地想解法了。

ver.1 （错解）

受到样例解释的感染，超速临界点为 $p=d_i + {V^2-v_i^2 \over 2a_i}$，手工向上下舍入。
接下来分类讨论：

注：

• 后文所有区间均指该区间与 $\mathbb{Z}$ 的交集
• $\mathrm{LB}(x)$ = lower_bound(p+1, p+m+1, x) - p
  代表满足 $p_i\ge x$ 的最小的 $i$；
  区间化地，代表 $p_i\in[x,+\infty)$ 的左边界。
• $\mathrm{UB}(x)$ = upper_bound(p+1, p+m+1, x) - p
  代表满足 $p_i\gt x$ 的最小的 $i$；
  区间化地，代表 $p_i\in(x, +\infty)$ 的左边界。
• 之后会用到，$\mathrm{LB}(x)-1$ 代表 $p_i\in(-\infty, x)$ 的右边界。

• $a_i=0$
  • $v_i\le V$，无事发生
  • $v_i\gt V$，超速区间 $[d_i, +\infty)$，
    对应到摄像头上，即为 $\mathrm{LB}(d_i)$ ~ $m$
    $(LB(d_i)\ne m+1)$
• $a_i>0$
  • 超速区间 $(p,+\infty) = (\lfloor p\rfloor, +\infty)$
    对应到摄像头上，即为 $\mathrm{LB}(\lfloor p\rfloor)$ ~ $m$
    $(LB(p)\ne m+1)$
    然而这是错的！
• $a_i<0$
  最复杂的一集。
  • $v_i\le V$，无事发生
  • $v_i>V$，超速区间 $[d_i, p)=[d_i, \lceil p\rceil)$
    对应到摄像头上，即为 $\mathrm{LB}(d_i)$ ~ $\mathrm{LB}(\lceil p\rceil)-1$
    $(\mathrm{LB}(d_i)\le\mathrm{LB}(p)-1)$

第二问是一个贪心的模板。每个区间按右端点升序排序之后，对于每一个区间，如果当前没有摄像头开着，就把它右端点的摄像头开了。
虽然第二问基于第一问，但是我都是第一问起火，第二问稳过。

改 I

1, 2 样例都对了，一看 3，丸辣！顿时心灰意冷。
“然而我已经不是去年的我了！”
我从头分析一遍，原来是 $a_i>0$ 时的 upper_bound 写成 lower_bound 了。
改了，然而还是错。
一试，结果 C++ 的整除居然是向 0 舍入。好吧，改了，但是仍然错。
我慌了，试着过滤掉范围不合法的。结果更错了。

改 II

一看第 3 个样例，发现 $a_i$ 咋都是 0 呢？再一看，#4 $a_i>0$，#5 $a_i<0$. 好吧。
于是 #3 盯着 $a_i=0$ 改了。具体的忘了。
然后再分析，发现 $a_i>0$ 的时候，应该为 $[d_i, +\infty)\cap(p,+\infty)$，然而这个并集不好做。于是加了 $v_i>V$ 的特判代替。
改完居然稀里糊涂地 A 了所有大样例。
代码果然是玄学。

T3

以1为单位转移

写了个 $\mathrm{O}(n^3)$ 的暴力 dp 拿部分分。
$f(i, r, b)$ 表示第 $i$ 个字，上一个红，蓝色分别是 $r, b$.
本来想用 map 防止爆空间并且减少无用计算的，但是忘了 map 咋写了。
最后只能把 maxn 改小了。痛失更多部分分。

以段为单位转移

马后炮想出来的，可惜 T2 调了太久。

T4

太长没看。

后

对了大样例。实在没有时间和精力打拍子了。
最后 30 分钟，我一边憋着尿一边求神拜佛。
提前 2 分钟收卷，出考场发现我的可乐居然被人喝了。

分

$100+100+35+0=235$