题解：CF2084H Turtle and Nediam 2

· · 题解

感觉比较套路啊，但是为啥又不会做了/ll

将 01 串缩成极长连续段，记每段长度为 a_i，共有 m 段。操作分为对 a_i>1 的 a_i\to a_i-1，或者 1<i<m 且 a_i=a_{i-1}=1，将 a_{i-1} 删除并且将 a_i 合并到 a_{i-2} 上。发现 a_m 压根删不掉，并且与前面无关，因此可以只考虑 [1,m-1]，将 II 的判定换为并非开头，最终答案乘上 a_m。

判定一个序列 b 能否被操作得到，特判最终全相等的情况。由于最终每个元素都可以看成由一个全集划分的区间操作缩成一个元素，每个区间长度为奇数。对于 b，要求由最短的前缀生成它。不妨设 b 对应的 0/1 颜色与 s 开头相同，否则 b 开头颜色与 s 不同：可以弹出首位，移位后 a_1'=1，归约到 b 开头颜色与 s 开头的情况。

容易得到这样的 dp：f_i 表示 [1,i] 可以生成的 b 使得恰好以 i 为结尾，然后枚举 i\bmod2 \ne j\bmod 2,i<j，新拼上的区间是 [i+1,j]，尝试转移到 f_j。此时需要考虑 \text{back}(b)=v 的取值范围，在 j 时有 l_j=\max_{j\bmod 2=k\bmod 2,k\leq j}a_k+\frac{j-k}{2}。那么转移到 j 时，应该有 \text{back}(b)\in(l_{j-2},l_j]。固定 i，从小到大枚举 j 并维护 l_j 容易做到 \mathcal O(n^2) 的复杂度。

注意到在暴力过程中 l_i=\max(l_{i-2}+1,a_i)，因此尝试将 \max 拆了，找到第一次 l_{i-2}+1 比 a_i 小的位置 j，这样就会被取 \max，f_i 对后续的转移贡献就与 f_{j-2} 的转移贡献没有区别，可以延后贡献到 j 合并贡献。令 j=nxt_i，那么在 [i+2,nxt_j-2] 的贡献可以对奇偶分开，动态维护一个差分数组即可。时间复杂度 \mathcal O(n)。

提交记录