子文略略略题解

为了响应学院领导“提高编程能力的号召”，最近大一新生程序设计课上多了一个刷题平台（于是它们有四项课后任务：课后习题、游戏项目、安全项目和编程训练，可真够累的）。本来这个刷题平台放的题目都是比较基础的语言类题目，可是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

随便代一个样例可得

将一个数转换成二进制需要，因此时间复杂度是，总时间复杂度为

part1

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

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

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不具备无后效性的条件，怎么办呢？多试几次就可以了。

只不过此时的总复杂度是，妥妥地TLE.

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

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级别，因此总复杂度为。

ps

part0

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

part1

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

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

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