CSP-S 2024

· · 生活·游记

考前大量消耗 rp，CSP 大量消耗 rp，我在 NOIP 怕不是没有 rp 了。

省流：100+100+100+48=348。

duel 和 color 是 CF 原题，Copy CodeForces 真有你的。

duel

有个很显然的结论是 \max\{cnt_{a_i}\}，但是我没观察到。

有个很显然的性质是：小的打小的，然后被大的打。

因此你拿个小根堆维护没有 out，每次看堆顶和当前元素的大小关系就行了。

detect

容易发现能发现超速的一定是连续的区间，二分求出来，然后就是很典的贪心了。 忘了怎么做？赛时做法千奇百怪，我的做法是先把区间去重，容易想到一个区间包含另一个区间的时候，这个区间是没用的，去掉这种区间后按照左端点排序。如果当前区间没被覆盖就取右端点，易证这个做法是最优的。 其实实现比较精细的话不需要去重。 ### color 直接大力线性 dp，经典模型是直接定义 $f_i$ 表示 $i$ 的答案，然后枚举前面的 $j$ 进行转移。 放到本题中，$j$ 就是 $i$ 前面第一个和 $i$ 同色/异色的位置，如果是异色的话，$j$ 的贡献不是很好算，直接在状态上做手脚，把 $f_i$ 的定义改成钦定 $i$ 和 $i+1$ 颜色不同时的答案。 转移就看 $i$ 和 $i-1$ 的颜色关系，不妨令 $i$ 和 $i-1$ 同色，异色同理。 枚举 $j$ 表示 $[1,i-2]$ 中最后一个和 $i$ 异色的位置，那么 $j$ 和 $i+1$ 颜色相同，有转移 $f_i\gets\max\{f_i,f_j+\sum\limits_{k=j+1}^{i-1}[a_k=a_{k+1}]a_k+[a_j=a_{i+1}]a_j\}$。 令 $s_i=\sum\limits_{j=1}^{i-1}[a_j=a_{j+1}]a_j$，有转移 $f_i\gets\max\{f_i,f_j+s_{i-1}-s_j+[a_j=a_{i+1}]a_j\}$。 这时已经容易想到讨论 $a_j$ 和 $a_{i+1}$ 的关系了。 若 $a_j=a_{i+1}$，那么容易想到令 $j$ 为 $[1,i-2]$ 最后一次出现 $a_j$ 的位置一定不劣，这种情况单独算即可。 若 $a_j\ne a_{i+1}$，其实可以把 $a_j=a_{i+1}$ 的情况放一起算，因为少加上了 $a_j$ 一定不优，就是 $f_i\gets\max\{f_i,f_j+s_{i-1}-s_j\}$，用前缀 $\max$ 维护一下即可。 ### arena 讲一个大家都会做的平方带对 dp：定义 $f_{i,j}$ 表示 $i$ 是否能存活到第 $j$ 轮。事实上因为 $c$ 不同每次的人机不一样所以每次都要 dp。 A 性质每次都没有人机，所以先用一个 dp 初始化出来就行了。