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比较（是否可行），不断二分求出最小高度