【VP 记录】EDU097

KSCD_ · 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] 区间内的必须改，剩下的元素中最长不下降子序列可以不修改，其他的必须修改，统计答案和即可。

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