Latest: https://www.cnblogs.com/caijianhong/p/18508783/traval-in-csp2024
初赛太难了。
广附黄华路考点不能带“无存储功能的手表”以及“非透明的水杯”进入考场。
花了 10 分钟调教了机器。
T2、T4 的题面好长。
T1 直接贪心就行。
T2 先二分得到超速区间，然后单调队列优化 dp。期间被无车被抓的样例卡了一次。
T3 的 dp 设计之前见过，然后优化很显然。一开始还在想是先打暴力还是先打正解。
T4 先写了性质 A，然后搞了个复杂的 O(Tn\log n) 的做法，具体过程太长了就不写了。
线性做法应该要推倒重来，没什么时间了。稍微删除了一些无用的循环，但还是稳定 0.6s。
下班！！！
---
思路不一定是对的。甚至很可能是错的，，，考场代码细节太多，不想默了。
# 题解 P11231【[CSP-S 2024] 决斗】
## solution
可以优先将 $r_i$ 小的怪物淘汰出局，也可以优先使用 $r_i$ 小的怪物的攻击。对 $r_i$ 排序后从小到大维护两个指针 $i, j$，表示当前将要用 $r_j$ 淘汰 $r_i$，始终保持 $r_j>r_i, j\leq n$，每次发动一次攻击后 $i, j$ 都右移。我写的复杂度是 $O(n\log n)$。
# 题解 P11232【[CSP-S 2024] 超速检测】
## solution
速度是单调的，可以对每个车二分得到它在什么路程区间上是超速的。使用以下公式：
- 当一辆车的初速度为 $v_0$、加速度 $a \neq 0$，做匀加速运动，则当它的位移（即行驶路程）为 $s$ 时，这辆车的瞬时速度为 $\sqrt{v_0^2+2\times a\times s}$。
为避免根号的误差，可以对两边平方。注意这个路程区间的两端只需要取到整数。
后面的部分我写了单调队列优化 dp。$f_i$ 表示最后一个选上的灯是第 $i$ 盏，转移首先计算 $maxl=\max_{[l, r], r< pos_i}l$，注意不被任何灯抓到的车不能计算贡献，然后 $f_i=1+\min_{maxl\leq pos_j}f_j$。有一些神经病的边界问题都可用 $minl$ 判断。然后这个东西可以单调队列优化。我写的复杂度是 $O(n(\log n+\log L))$。
# 题解 P11233【[CSP-S 2024] 染色】
## solution
两种颜色是没有区别的。$f_{i, j}$ 表示一种颜色最后一个选的是 $i$，另一种颜色最后一个选的是 $j$，要求 $j<i$。转移枚举 $i+1$ 与 $i, j$ 中的哪一个同色。转移到 $f_{i+1, j}$ 和 $f_{i+1, i}$ 中的一个。仔细考虑也就是
$$
f_{i, j}+[a_i=a_{i+1}]a_{i+1}\to f_{i+1, j}
$$
$$
f_{i, j}+[a_j=a_{i+1}]a_{i+1}\to f_{i+1, i}
$$
将 $i$ 这一维去掉，第一种转移是全局加（直接维护标记），第二种转移是单点修改（事实上甚至是 `push_back`，不会影响其它已计算的值），需要支持查询全局最大值和 $a_j=a_{i+1}$ 的 $f_j$ 的最大值，前者用一个变量维护，后者开一个桶维护。我写的复杂度是 $O(T(n+V))$。
# 题解 P11234【[CSP-S 2024] 擂台游戏】
## solution 84
枚举最后补全到 $2^k$ 个人，显然不会影响复杂度。
这个游戏就是一个二叉树结构，直接建类似 zkw 线段树的结构方便考虑。考虑第 $i$ 个人怎么赢，它到根的路径上，是擂主的时候必须赢（也就是其能力值要不小于某个可以用 $d$ 预处理的数），不是擂主是时候要求擂主能输。由于有伪人的存在（由于有人的能力值不确定），我们不一定能知道擂主能不能输。先写一个带 $\log$ 的东西，记 $sum_p$ 表示结点 $p$ 的子树中可能赢的人的编号，$up_p$ （一个集合）表示结点 $p$ 的赢家的可能的能力值（显然可以对 $17$ chkmin）。当一个伪人的能力值塌陷时（当一个人的能力值确定时），他到根的路径的 $sum, up$ 都被更改。如果我们提前将某些不可能赢的人（指其做某一层擂主的时候会输）的人提前枪毙，使其不计入 $sum$，并记 $R$ 为 $p$ 所在的轮数，$lc$ 是擂主方的儿子，$rc$ 是 $lc$ 的兄弟，那么：
- $up_p=\{x\in up_{lc}|x\geq R\}$ 表示擂主方赢的部分。如果 $\exists x\in up_{lc_p}$ 那么擂主可以输掉，$up_p$ 额外 $\cup$ 上 $up_{rc}$。
- $sum_p=sum_{lc}$ 表示赢的擂主的编号和（可能输的擂主已经枪毙）。如果 $\exists x\in up_{lc_p}$ 那么擂主可以输掉，$sum_p$ 额外 $+$ 上 $sum_{rc}$。
维护之，复杂度 $O(Tn\log n)$。实现要好一点。关键在于我们用一个 $up$ 去除了伪人带来的不确定性，充要地刻画了每个人赢的条件，并在每次修改时维护。