本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-06 08:23:54

记录

A 切掉了，B 卡了很长时间，后来跳过看 CD 切了，B最终也没做出来，寄。

题解

A. Marketing Scheme

可以发现 $a=2l$ 时对于 $l$ 满足条件且范围最大，因此判断 $r < 2l$ 是否成立即可。

B. Reverse Binary Strings

发现每次反转可以减短连续段长度，具体地，每次可以同时减小一段黑和一段白或两种中一种，所以答案为两种颜色分别需要减短的长度和，也即每个连续段长度 $-1$ 的和。

C. Chef Monocarp

发现一定有一种最优方案使得按照 $t_i$ 不增排序时，$T_i$ 递增。因此按照 $t_i$ 排序，之后可以使用 dp，设 $f_{i,j}$ 为前 $i$ 个物品处理完且最后一个物品在时间 $j$ 的最小代价，则可以从 $f_{i-1,k},i-1<k<j$ 转移过来，取最小值即可。

D. Minimal Height Tree

发现在 bfs 序上每个节点的所有子节点都是一段连续递增的子串，又因为高度最小就要让每个节点的子节点尽可能多，所以选极大上升子串一定最优，同时每开到下一层就记录一下答案即可。

E. Make It Increasing

发现所有无法修改的位置会把整个序列分成若干段，每一段是独立的。可以加入边界 $a_0=-\infty,a_{n+1}=+\infty$

考虑对每个区间 $[l,r]$，因为要求严格上升，所以需要 $a_r-a_l\ge r-l$，也就是 $a_l-l\le a_r-r$，进一步地可以把 $a_i$ 转化为 $a_i-i$，原序列的上升子序列就变为新序列的不下降子序列。

所以在这个区间内，不在 $[a_l,a_r]$ 区间内的必须改，剩下的元素中最长不下降子序列可以不修改，其他的必须修改，统计答案和即可。

由于区间端点必然属于最长不下降子序列，所以不用特殊处理。