「HCOI-R1」哀之变化

Wf_yjqd · 2023-09-23 11:29:49 · 题解

官方题解。

自评难度介于黄和绿之间。

暂时没考虑到其他做法。

\text{Subtask 0}

对于每次询问暴搜。

\text{Subtask 1}

考虑离线处理，将所有询问按 k 从小到大排序，然后一次 dp 出所有答案。

或者直接记忆化搜索。

复杂度为 \operatorname{O}(n^2)。

注：以上复杂度中的 n 仅表示题面中 n,k 的数量级。

\text{Subtask 2}

考虑求出达到 n 的最小次数，然后尝试在过程中浪费一些操作以达到 k 次。

首先特判 n=0,1 的情况。

当 n\ge 1 时，我们可以通过 1\times2-1=1 这样的操作浪费掉任意偶数次。

当 n\ge 2 时，我们还可以通过 2\times 2-1-1=2 这样的操作浪费掉 3 次。

显然可以凑出大于 1 的任意整数。

考虑能否浪费 1 次，显然只有 a\times2-1-1=(a-1)\times2。

如果 n 的最短操作中不包括 (a-1)\times2，以上方案就无法实现。

此时 n 一定为 2 的幂次或 2 的幂次 -1（最多只允许最后有一次 -1 操作）。

根据以上条件即可判断是否可行，复杂度 \operatorname{O}(T\times\log{n})。

或许您会不知道如何求达到 n 的最小次数，有一种较简单的思考方法。

转换此题为一个本质完全相同的问题（也是出题人最开始想到的问题）。

给定一个整数 n，进行 k 次操作，问最终能否为 1。

每次操作从以下两种中选一个：

• a\gets a+1

他们的最小次数也是一样的。

考虑尽可能多的 a\gets\frac{a}{2} 即可。

放一下代码吧。