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}\)
- \(\max_{j<i-1,a_i=a_j} (dp_{i-1,j}+a_i)\)。
观察到第二个式子和第三个式子都包含区间最大值，考虑使用线段树优化 dp。
具体来说，对满足 \(a_i=k\) 的项单独开线段树，并对全局单独开一棵。
那么二操作就是全局树的区间 \(\max\)，三操作就是第 \(a_i\) 棵树的区间 \(\max\)。
做完了。
T4
没来得及写，T3 debug 时间太长了。
模拟应该能拿 30 pts。
感受
-
fsanitize开了之后耗时几乎 \(\times 2\)，T2 在打开时极限数据下耗时为 1300 ms，关闭后即降低至 600 ms。 -
T3 式子转线段树的时候弄错了，浪费的时间有点长。