Codeforces Round 907 (Div. 2) Editorial

__vector__ · 2023-11-02 13:34:47 · 个人记录

对我来说的难度: A<B<F<D<<C<E

A

从前向后贪心就好了.

B

每个数 a_i 最多被操作 \lfloor \log_2 a_i \rfloor 次.

每次操作,a_i 会变成 2^{x_i - 1} 的倍数.

暴力维护就好了.

C

最优方案是技能 1 干掉一半,剩下使用技能 2 解决.
应最小化使用技能 2 的次数.

考虑最少要用多少次,这里可以显然得出一个结论,设将 a 排序从大到小后,第一个前缀和大于等于 \frac{\sum\limits_{i=1}^{n}a_i}{2} 的元素编号为 pos,那么这 pos 个元素都是需要使用技能 2 的.

不难的得出,总答案是 \lceil \frac{\sum\limits_{i=1}^{n}a_i}{2} \rceil + pos.

D

显而易见 f 的变化次数是 log 级别,而在 f 相等的情况下, g 的变化次数是 log 级别.

二分就行.

E

贪心题。

可以先拆分成一些由前后互质的数组成的数列。

由于 1 是一个特殊的存在，直接操作非 1 的数，若旁边有相邻的 1，那么不会改变与 1 的 gcd，所以将所有 1 找出来，记录所有连续 1 的段落，另外如果连续 1 子段的某一端在 1 或 n，则按照贪心策略应放到最后操作。

特别地，如果整个数组全是 1，答案是 n-k。

具体的，将所有不包含 1 互质子段扔进队列 1，所有不包含位置 1,n 的连续 1 子段扔进队列 3，另外设一个队列 2，后面解释。

然后，很明显，有以下贪心过程。

• 首先遍历队列 1，对于非 1 互质段落，可以发现每段从第 2 个开始，到第 len-1，隔一个数操作一个数，可以做到每次操作，答案 -2。对于操作剩下的数，如果一个数两边都是 0，那么可以扔掉不管，如果仍然剩下两个前后互质的数，将这两个数组成的子段扔进队列 2。

• 然后按照长度从小到大遍历队列 3 ，对于连续 1 子段，对于每个子段，若能解决掉 x \le len-1 个数，则答案减去 x，否则答案减去 len+1。

• 然后遍历队列 2，每个区间都有 1 的贡献。

• 最后寻找剩下的 1，每个数字 1 有 1 的贡献。

Submission

F

为了方便,将询问离线,提前建立最终的树.

• 操作一,建立新点,应当先消除当前点及其子树原有受到的来自祖先影响.

• 操作二,修改子树,直接改最终形态就行.

对于修改子树,可以提前 dfn 标号,这样整个子树的 dfn 是连续的一段区间,随后使用树状数组.