查看源代码：
CSP-S-2024.md

---
title: CSP-S 2024 日记
createTime: 2024/10/26
categories:
    - IT
tags:
    - OI
    - OI-travel-notes
---

## 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}$，手工向上下舍入。  
接下来分类讨论：  

:::tip 注：
- 后文所有区间均指该区间与 $\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$