CSP-S 2024 游记
JimmyLee
·
·
生活·游记
Day 0
回顾了一下各类字符串算法，切了几道 ACAM 的题。（果然没考）
然后就摆了。
Day 1
上午狠狠的摆。
下午去考场。
考试过程中被小孩哥干扰，左边砸鼠标，右边砸键盘。
有点缺德。
T1
签。
记 cnt_i 为战力为 i 的怪兽的个数，答案即为 \max(cnt_i)。
T2
转换成每个车能被下标为 [l, r] 的摄像头看到。
最小点覆盖即可。
T3
令 dp_{i,j,k} 为枚举到第 i 位，上一位蓝为第 j 位，上一位红为第 k 位。
显然有 i=j 或 i=k。
所以我们简化为 dp_{i,0/1,j}，表示为枚举到第 i 位，第 i 位取红/蓝，上一位蓝/红为第 j 位。
于是有：
\begin{aligned}
dp_{i,0,j}&=dp_{i-1,0,j}+[a_i=a_{i-1}]\times a_i\\
dp_{i,0,i-1}&=\max^{i-2}_{j=0}(dp_{i,0,i-1},dp_{i-1,1,j}+[a_i=a_j]\times a_i)\\
\end{aligned}
发现 0/1 互不影响。
于是又有：
\begin{aligned}
dp_{i,j}&=dp_{i-1,j}+[a_i=a_{i-1}]\times a_i\\
dp_{i,i-1}&=\max^{i-2}_{j=0}(dp_{i,i-1},dp_{i-1,j}+[a_i=a_j]\times a_i)\\
\end{aligned}
鉴于 [a_i=a_{i-1}]\times a_i 为定值，上排的式子可以转化成全局加。
考虑优化下排的式子。
\begin{aligned}
dp_{i,i-1}&=\max^{i-2}_{j=0}(dp_{i,i-1},dp_{i-1,j}+[a_i=a_j]\times a_i)\\
\end{aligned}
将其拆成三个式子的 \max：
-
dp_{i,i-1}
-
\max^{i-2}_{j=0} dp_{i-1,j}
-
观察到第二个式子和第三个式子都包含区间最大值，考虑使用线段树优化 dp。
具体来说，对满足 a_i=k 的项单独开线段树，并对全局单独开一棵。
那么二操作就是全局树的区间 \max，三操作就是第 a_i 棵树的区间 \max。
做完了。
T4
没来得及写，T3 debug 时间太长了。
模拟应该能拿 30 pts。
感受
-
fsanitize 开了之后耗时几乎 \times 2，T2 在打开时极限数据下耗时为 1300 ms，关闭后即降低至 600 ms。
-
T3 式子转线段树的时候弄错了，浪费的时间有点长。