CF2178 Goodbye 2025 补题笔记

D

Statement

有 $n \leq 2 \times 10^5$ 个精灵，他们有生命值 $h_i$ 和攻击力 $a_i$ ，初始有 $h_i=a_i$ 且不同精灵的攻击力不相同。

重复以下过程：

• 任选两个活着（ $h_i>0$ ）的精灵 $x,y$ ，让没有发起过攻击的精灵 $x$ 发起一次攻击，使双方的生命值扣除对方的攻击力。如果无法执行操作，过程结束。

给定整数 $m$ ，构造一组攻击序列使得结束时恰好有 $m$ 个精灵存活。

Solution

首先当 $m > \lfloor\frac{n}{2}\rfloor$ 时一定无解（一定还有可以互相杀的），考虑按照攻击力排序，既然要让 $m$ 个最终存活，不妨钦定攻击力最高的 $m$ 个最终存活，让他们分别攻击另外 $m$ 个精灵（目的是消耗掉他们的攻击机会），再让剩下的 $k = n - 2 \times m$ 个精灵按照攻击力排序呈“链状”主动攻击送死即可。

如果 $m=0$ 即所有精灵全部死亡怎么办？最后一次攻击必须是两个精灵同归于尽，那么其中较强的一个一定已经被消耗，依然钦定攻击力最高的两个活下来，按照攻击力从小到大排序找到若干个精灵用于削弱最强的精灵，剩下的依旧“链状”主动攻击次弱的即可。

submission

E

Statement

交互题。数组 $a$ 由如下方式生成：

• 初始 $a=b=[2^k]$ 。
• 以任意顺序执行至少零次以下两种操作：
• 选择 $a$ 与 $b$ 中的一个，若其最大的一个元素是偶数 $x$ ，用两个 $\frac{x}{2}$ 替换它。
• $a,b := a+b$ （ $+$ 代表拼接操作）。
• 最后 $b$ 将会被丢弃。

你可以进行至多 $300$ 次查询：询问 $l,r$ ，返回 $a$ 在 $[l,r]$ 的区间和 。你要找到 $a$ 中最大元素的值。 $n \le 10^5$ 。

Solution

由于每次总是分裂大的那个数，对于任意一个区间，按照区间和将其均等分割为两个区间，最大值一定在较短的那个区间里。二分查询，可以在 $300$ 次查询以内找到答案。
submission

F

还没做