2023的第一杯茶
01.02 CF 379D
01.03 ABC 249F
初始你有一个数字$x = 0$
总计$N$个操作,
操作1: x替换为y
操作2: x等于 x加上y
你总共可以跳过至多$K$个操作, 问你可以得到的最大x是多少?
- 操作1会覆盖之前的所有操作记录, 从后往前考虑是一个合理的选择
- 从后往前, 首先记录操作1的数量
op1, 与K进行比较; $op1 \leq K$都至少可以跳(不被覆盖掉) - 遇到操作2, 贪心地选最好的进行, 否则就跳掉(用一个堆来维护?), 所以肯定是保留正数, 负数尽可能挑大的.
01.04
01.05 CF 1718A2
输入t组数据, 每一组数据包括一个数字n和长度为n的数组
每次操作可以把a的下标从L到R的元素同时异或一个数, 花费为$ceil(R - L + 1) / 2$
输出把a的元素全部变成0的最小代价
尽可能地连续
尽可能覆盖更多位?
感觉可以和今天的每日一题放在一起, 都是处理数值异或类型的问题.
01.06 CF 1739D
你可以做如下操作至多 k 次：
断开 p[i] 和 i 之间的边，然后在 1 和 i 之间连边。
输出操作后，这颗树的最小高度。
高度的定义为 1 到最远叶子节点的路径的边数。
- 最小高度 => 可以二分这个高度值
- 什么时候我们需要做操作：自底向上写一个树形dp，当高度值+1达到限制时，需要进行切割操作；
- 记录这个次数与k比较（是否可行），不断二分求出最小高度