【补题记录】ARC180

· · 个人记录

记录

赛时在车上还很困，A 都没做出来直接跑了。CD 老师讲了，写一下记录。

题解

A - ABA and BAB

发现对于每个长度为奇数且相邻两个字母不相同的子串，都可以删除其中任意多个 AB（或者说是 BA），也就是长为 k 的子串可以有 \frac{k+1}2 种结果。所以对于每个这样的极长子串记录方案数，乘法原理乘起来即可。

这样不会算重是因为两段之间一定是互不影响的，而且相邻两个极长段之间要么字符相同，要么是极长段长为偶数多出来的，都会有字符分隔，所以乘法原理正确。

C - Subsequence and Prefix Sum

发现会影响接下来操作的只有目前的前缀和，而不关心这个前缀和是怎么来的。又因为值域小，总和的绝对值不超过 1000，可以设入状态，设 f_{i,j} 表示前 i 位中目前前缀和为 j 的方案数。

所以不选 i 时有 f_{i,j}=f_{i,j}+f_{i-1,j}，否则有 f_{i,j+a_i}=f_{i,j+a_i}+f_{i-1,j}(j\ne0)。这里 j 不等于 0 是因为如果用 0 来转移，那么 a_i 不会有变化，会导致计重。

所以设 g_i 表示上一次为 0 又加上了 i 的方案数，每次令 g_{a_i}=g_0,g_0=f_{i,0} 即可。前面的转移也会变成 f_{i,j+a_i}=f_{i,j+a_i}+f_{i-1,j}+g_j(j\ne0)，这样就没问题了。

D - Division into 3

先考虑朴素做法，发现区间内的最大值一定会贡献到答案里。那么分这个最大值 p 在哪一段讨论。若在第二段，那么左右各取最边上的一个一定最优。若在两边，那么中间的第二段只取一个一定不劣，这里假设取左边的第一段，那么就要求 i\in[p+1,r-1] 使得 a_i+\max_{k=i+1}^r a_k 最小。

考虑把所有这样的询问 [p,r] 离线下来，然后对整个长度为 n 的区间操作。发现 a_i 只会影响到 [k,i-1] 这段区间，其中 a_k 是 i 前面最近的大于 i 的数。那么所有最终有影响的 a_i 一定单调递减，可以用个单调栈维护。

所以设 f_i 表示处理到目前的 r 时的 a_i+\max_{k=i+1}^r a_k，如果能在依次处理每一个元素的同时维护这个数组，那只要在处理完了询问的 r 后求 [p+1,r-1] 区间的 f_i 最小值即可。那么每处理到 i 就给 f_{i-1} 赋值 a_{i-1}+a_i，然后维护单调栈，弹出元素 x 时意味着 x 的上一个元素直到 x-1 这一段区间 f_i 中的最大值不能取 a_x 而是要取 a_i 了，所以这段要加上 a_i-a_x。

综上，要支持的操作有：

所以线段树就行了。