子文略略略题解

为了响应学院领导“提高编程能力的号召”,最近大一新生程序设计课上多了一个刷题平台(于是它们有四项课后任务:课后习题、游戏项目、安全项目和编程训练,可真够累的)。本来这个刷题平台放的题目都是比较基础的语言类题目,可是yyx在其中加入了ds题和大模拟,让作业的难度陡然提升。我决定加一些思维题来平衡少年生在码力上的先天优势。

idea

与yjp在某日中午恰饭时得出,yjp很快想到了part 0的正解,但对part 1的解答存在一些问题。我通过了某种方式(下文会说)得到了一种复杂度较低的做法。

question

part0

给一个数x,它初始为0,你有加1、乘2两种操作。问从0变成自然数a最少需要几种操作。

part1

给一个数x,它初始为1,你有加1、减1、乘2三种操作。问从1变成自然数a最少需要几种操作。

solution

part0

从二进制角度思考:对这个数乘2相当于左移一位,而对这个数加一相当于在末尾加1,而这个1什么时候加都可以。因此最优的解法就是在左移的途中,那一位如果最后是1,就马上加上(不然要加更多个1才能补回去)。我们可以导出一个公式:

最少的次数 = 二进制的位数 + 二进制中1的个数 + C

随便代一个样例可得$C=-1$

将一个数转换成二进制需要$O(\log x)$,因此时间复杂度是$O(\log x)$,总时间复杂度为$O(T \log x)$

part1

yjp开始是想对末尾为一连串1的情况进行处理,可是具体的细节没有想得太清楚,只好作罢。

首先做一下dp,设dp[i]为从1变为i所需的最少次数,显然dp[1]=0,可列出以下转移方程:

1
2
3
4
if (i % 2 == 0)
dp[i] = min(dp[i/2] + 1, dp[i]);
dp[i] = min(dp[i-1] + 1, dp[i]);
dp[i] = min(dp[i+1] + 1, dp[i]);

显然这个dp不具备无后效性的条件,怎么办呢?多试几次就可以了。

只不过此时的总复杂度是$O(Tkx)$,妥妥地TLE.

此时我灵光一闪,把得到的最优解放在oeis上,然后得到了更优的转移方程。

1
2
3
4
if (i % 2 == 0)
dp[i] = min(dp[i/2] + 1, dp[i]);
else
dp[i] = min(dp[i/2] + 2, dp[i/2+1] + 2, dp[i]);

这样可能的状态数就是log级别了,拿个map维护一下,记忆化搜索即可。

由于map是用红黑树维护的,读写一个数也是log级别,因此总复杂度为$O(T \log^2 x)$。

ps

part0

第一题的解题人数在我预料之内。24h之内就有10人左右AC了。

part1

第二题在前24h无人AC,这稍微出乎了预期。

在第二天有非少年生AC了,这符合我出题的意图。

只不过之后又有少年生写出了$O(T \log x)$的做法。看了一些AC的代码,的确是模拟+分类讨论做的——看来yjp的愿望的确实现了,可喜可贺。