CSP-S 2024 游寄

cupWolf · 2024-11-02 19:35:54 · 生活·游记

Day -\infty

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

前

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

T1

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

T2

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

ver.1 （错解）

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

注：

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

• a_i=0
  • 对应到摄像头上，即为 $\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>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

写了个 \mathrm{O}(n^3) 的暴力 dp 拿部分分。