\textbf{CSP-S 2024} 游记
没报 \textbf J 组，上午在学校上数学课，某同学带了 \textbf{NOI} 辞典过去听课。。。中午回家吃饭，下午不到两点就到了考场，发现不让进。在外面溜达了一会，碰到一堆大神，但周围也很多小学生，感觉要被单调队列了。
终于让进了，坐下后先把背景换成了“暴力出奇迹”，小企鹅还挺可爱的。默写了一下快读快写板子，结果输入输出负数写错了，第二题调试时候改了快读，快写错到最后不过不影响。。。
接下来看第二题，为什么用简单物理背景出题，还给了三条公式。。。一眼看出是两道黄题（二分查找、最小点覆盖）拼接起来的，开始写，边界调了半天，$16:10$ 左右搞定。
第三题题面写的乱七八糟，还定义了个 $C$ 数组，瞪出了一个 $n^2$ DP，结果打着打着发现了后效性，立刻全删。突然发现贪心：最优情况下每个点只可能与左侧最近相同数产生得分。简单举了个例子证了一下，转化成类似选区间问题，就是 $O(n)$ DP。开始写代码，$10$ 分钟过去大样例一个没过。此时已是 $17:20$。出去上了个厕所，发现外面好冷。回来再一分析发现空区间可以直接选。调整了一下代码，样例 $1$ 过掉，样例 $2$ 差两个点。突然发现边界写的乱七八糟，改了一下过了，感谢样例强度。$18$ 点整。
只剩半个小时了，第四题题面又很古怪，来来回回读了三遍读懂了，手模了样例，$40$ 分（可能是 $60$）暴力思路想了出来，但是代码可能比较长写不完，果断放弃想特殊性质。$8/16$ 分（不确定）代码用 $15$ 分钟写完。一遍过，交了上去。最后 $5$ 分钟，开始收拾东西，心想今年又考砸了，前面做题太慢，最后一题暴力没拿满，悲伤。预估分数 $100+100+100+[8,16]=[308,316]$。
周六找了个时间重写了遍前三题代码，交到洛谷上都满分，心里踏实了一些。周日有人把压缩包密码破开了（怎么这么快），把考场代码交了上去，$100+100+100+28=328$，心想最后一题数据什么情况。看了数据范围发现 $T=1$ 时这种做法确实不是很好卡。
周中计蒜客又出了估分系统，$100+100+100+40=340$，数据水到家了吧。
最终分数 $100+100+100+8=308$，数据强度还是可以的。
## $\textbf{P1}\sim\textbf{P3}$ 题解
### 决斗（$\texttt{duel}$）
#### 题目描述
[洛谷题目链接](https://www.luogu.com.cn/problem/P11231)。
今天是小 Q 的生日，他得到了 $n$ 张卡牌作为礼物。这些卡牌属于火爆的“决斗怪兽”，其中，第 $i$ 张卡代表一只攻击力为 $r_i$，防御力也为 $r_i$ 的怪兽。
一场游戏分为若干回合。每回合，小 Q 会选择某只怪兽 $i$ 以及**另一只**怪兽 $j(i \neq j)$，并让怪兽 $i$ 向怪兽 $j$ 发起攻击。此时，若怪兽 $i$ 的攻击力小于等于怪兽 $j$ 的防御力，则无事发生；否则，怪兽 $j$ 的防御被打破，怪兽 $j$ 退出游戏不再参与到剩下的游戏中。一只怪兽在整场游戏中**至多**只能发起一次攻击。当未退出游戏的怪兽都已发起过攻击时，游戏结束。
小 Q 希望决定一组攻击顺序，使得在游戏结束时，未退出游戏的怪兽数量尽可能少。
#### 我的考场做法
贪心：先让能力较低的怪兽打最小的，再让其他怪兽把他打死。
先算出每种能力值的怪兽出现次数 $cnt_i$。设 $a_i$ 表示 $i$ 能力值且还可以攻击的怪兽个数，$b_i$ 表示 $i$ 能力值且还未被攻击的怪兽的个数。一开始 $a_i=b_i=cnt_i$。
从小到大遍历 $i$，每一次让 $a_i$ 个怪兽尝试消灭更小的怪兽。用双指针解决。时间复杂度 $O(n+r)$。
#### 其他人的做法
题目等价于将排序后的 $r$ 划分成严格上升子序列数目最小值，也就等于 $r$ 中出现个数最多的数出现的次数。时间复杂度 $O(n+r)$ 或 $O(n\log_2 n)$（取决于排序算法）。
### 超速检测（$\texttt{detect}$）
#### 题目描述
[洛谷题目链接](https://www.luogu.com.cn/problem/P11232)。
这个周末，主干道上预计出现 $n$ 辆车，其中第 $i$ 辆车从主干道上距离最南端 $d_i$ 的位置驶入，以 $v_i$ 的初速度和 $a_i$ 的加速度做匀加速运动向北行驶。我们只考虑从南向北的车辆，故 $v_i > 0$，但 $a_i$ 可正可负，也可以为零。当车辆行驶到主干道最北端（即距离最南端为 $L$ 的位置）或速度降为 $0$（这只可能在 $a_i < 0$ 时发生）时，我们认为该车驶离主干道。
主干道上设置了 $m$ 个测速仪，其中第 $j$ 个测速仪位于主干道上距离最南端 $p_j$ 的位置，每个测速仪可以设置开启或关闭。当某辆车经过某个开启的测速仪时，若这辆车的
瞬时速度**超过**了道路限速 $V$，那么这辆车就会被判定为超速。注意当车辆驶入与驶出主干道时，如果在对应位置有一个开启的测速仪，这个测速仪也会对这辆车进行测速。
上司首先想知道，如果所有测速仪都是开启的，那么这 $n$ 辆车中会有多少辆车被判定为超速。
其次，为了节能，部门想关闭一部分测速仪。然而，他们不希望漏掉超速的车，也就是说，当 $n$ 辆车里的某辆车在所有测速仪都开启时被判定为超速，他们希望在关闭一部分测速仪以后它依然被判定为超速。上司还想知道在这样的条件下最多可以关闭多少测速仪。
#### 我的考场做法
先算出这些车辆通过哪些测速仪时会被判定为超速，分类讨论。
- $a_i=0$，汽车进行匀速直线运动：
- $v_i\le V$，则汽车在整段道路上都没有超速。
- $v_i>V$，则汽车从进入道路开始都是超速的，二分算出进入道路后第一个测速仪，则从这个测速仪到最后一个测速仪都是超速的。
- $a_i<0$，汽车进行减速直线运动：
- $v_i\le V$，则汽车在整段道路上都没有超速。
- $v_i>V$，则从行驶到 $\dfrac{V^2-v_i^2}{2a_i}+d_i$ 前（不含）都超速了，仍用二分计算。
- $a_i>0$，汽车进行加速直线运动：
- $v_i>V$，则汽车进入道路后一直超速。
- $v_i\le V$，则汽车行驶到 $\dfrac{V^2-v_i^2}{2a_i}+d_i$ 后（不含）就一直超速。
善用 `lower_bound` 和 `upper_bound`（注意区别：前者是第一个 $\ge$ 给定值的最小元素，后者是 $>$）。
这样第一问答案被计算完了。考虑第二问：每个被判定为超速的汽车被某个区间内的测速仪记录，为了保证仍然被抓到，这个区间内需要有测速仪开启。
问题转化为给定若干区间，选出尽可能少的点使得每个区间都有选出的点。
很典型的贪心：按右端点排序，依次遍历区间，如果没有被覆盖，选右端点。（也可左端点排序进行贪心，但略复杂，容易写错。）
时间复杂度 $O(n\log_2(nm))$。
### 染色（$\texttt{color}$）
#### 题目描述
[洛谷题目链接](https://www.luogu.com.cn/problem/P11233)。
给定一个长度为 $n$ 的正整数数组 $A$，你要将 $A$ 中的每个数染成红色或蓝色之一，然后按如下方式计算最终得分：
设 $C$ 为长度为 $n$ 的整数数组，对于 $A$ 中的每个数 $A_i$（$1 \leq i \leq n$）：
- 如果 $A_i$ 左侧没有与其同色的数，则令 $C_i = 0$。
- 否则，记其左侧**与其最靠近的同色数**为 $A_j$，若 $A_i = A_j$，则令 $C_i = A_i$，否则令 $C_i = 0$。
你的最终得分为 $C$ 中所有整数的和，即 $\sum \limits_{i=1}^n C_i$。你需要最大化最终得分，请求出最终得分的最大值。
#### 我的考场做法
先预处理出每个数 $A_i$ 左侧最近的相同的数 $A_{p_i}$。则这一对数对答案做出贡献当且仅当 $A_{p_i+1}\sim A_{i-1}$ 同色，且与 $A_{p_i}$ 和 $A_i$ 不同色。
转化成一个区间 $[p_i,i]$，其权值为 $A_i$。现在要从这 $(\le)\;n-1$ 个区间中选出若干个，使得和最大。选出的任意两个区间 $[p_i,i],[p_j,j]\;(i<j)$ 需满足以下两条中的一条：
- $p_j<p_i=i-1<i<j$，即第一个区间长为 $2$，且包含于第二个（不含端点）；
- $i\le p_j$，即要么不交，要么交集恰好为 $\{i\}$。
动态规划：$dp[i]$ 表示上一个区间结尾为 $i$ 的答案。转移方程 $dp[i]=\max(dp[i-1],dp[p[i + 1]]+A_{i+1}+\sum_{i=p[i+1]+2}^{i}A_i\times[p[i]=i-1])$，可以前缀和优化。最终答案 $dp[n-1]$。时间复杂度 $O(n+A)$。
#### 其他人的做法
- $O(n\log_2n)$ 做法：[这篇文章](https://www.luogu.com.cn/article/4spomrpc) 。
- $O(n)$ 做法：[这篇文章](https://www.luogu.com.cn/article/rzyvi1w6)。