题解 P1028 【数的计算】

fangd · 2019-03-02 22:53:55 · 题解

零、关于题解

这篇题解是我在洛谷的处女答，编辑于2019年3月2日。就像玩洛谷要从A + B Problem玩起一样，蒟蒻的我挑了一道较为简单的一道题写一写。请大家多多指教！

一、读题

起初，这道题将我卡住了一些时间，并不是因为这道题太难，而仅仅只是因为我没有把题目读懂（好吧，我承认我太弱了）。

1. 题目给出了一个小于等于1000的数n，要求在这个数的左边加上一个数或者不做任何处理，使之不能超过原数的一半。
2. 紧接着再在操作完的数左边，加上一个数，新加上的数不能超过之前加上的数的一半 。当然，如果是第一次操作，就是不能超过n的一半。
3. 如此循环往复，直到不操作或者不能操作为止。大家可以参考着样例的解释看一看。
   以下给出伪代码：

   void count(int x)
   {
   for(每一个不超过(x / 2)的元素)   //遍历
   {
       每遍历一个，当然也可以不遍历
       计数器加一;
       count(每一个加上的元素);
   }
   }
   //计数器的结果即为所求

很多大佬都给出了这样的各种语言的递归代码，我就不在这里献丑了。

二、递推的解法

1. 对于每一个给出的或者我们自己加上的n，都有唯一的能推出的结果数与之对应（废话）。
2. 对于每一个n，n所能推出的结果数（即题目的答案）都可以拆解成所有不大于n/2的所有的n的所能推出地结果数的和。

综合以上两点，我们可以遍历从0到题目给出的n / 2的每一个n，然后求出它们的和就可以解决这个问题了。但，第二个命题的原理是什么呢？
以题目给的样例6为例，对于数字6，我们根据题意，可以有如下操作：

1. 不做任何操作：6
2. 在6的左边，加上1或2或3。

这也就是上面的第一层递推。但是，题目并没有这么简单，因为对于加上后的数，我们还能再进行一些操作。对于36，我们还可以推出136；对于26，我们还可以推出126。值得注意的是，不管是36，"3" + "7"，又或者是"3" + ...... + "1234567"，它们所能推出的结果的数量，和n = 3所能推出的结果的数量是一样的。因此，对于n = 6，它的结果数就是1所能推出的结果数 + 2所能推出的结果数 + 3所能推出的结果数。推而广之，我们就得到了第二个结论：对于每一个合法的n，n所能推出的结果数（即题目的答案）都可以拆解成所有不大于n/2的所有的n的所能推出地结果数的和。理解了这个，将从0到n / 2的所有的n所能推出的结果数用arr数组存起来，题目代码就能很容易地得到了：

#include <cstdio>
int main()
{
    int n, arr[1001] = {1, 1}; //将数组第0个和第1个的值赋为1。arr[0]表示什么也不操作，这也算是一种情况。
    scanf("%d", &n);
    for (int i = 2; i <= n; ++i)
        for (int j = 0; j <= (i >> 1); ++j)
            arr[i] += arr[j];
    printf("%d\n", arr[n]);
    return 0;
}

但仔细观察，我们发现，对于每一个arr[i]，我们都要将前面所有小于i的arr遍历求和，算法的时间复杂度为O(n ^ 2)级别的。我们能否将其再优化呢？

三、再优化

我们不妨打一下表，观察一下：

在给出的数据中，我们很容易就能发现两个规律。注意，这里的等号均表示等量关系，而不是赋值：
1. 对于任意合法的正整数n，都有：arr[2n] = arr[2n + 1]
2. 对于每一个arr[n]，都有arr[n] = arr[n - 1] + arr[n / 2]

证明如下：

1. 我们已经知道，对于每一个n，n所能推出的结果数（即题目的答案）都可以拆解成所有不大于n / 2的所有的n的所能推出地结果数的和。我们不妨用sum[0, x / 2]，来表示整数x从0到n / 2，所能推出的所有结果数的和。那么很显然：sum[0, x / 2]即为数当n = x时，题目的答案。因此，有：
   arr[n] = sum[0, n / 2] = sum[0, (n - 1) / 2] + arr[n / 2] = arr[n - 1] + arr[n / 2]。第二个命题得证。
2. 根据第二个命题，由于n / 2与(n。因此对于对于任意合法的正整数n，都有arr[2n] = arr[2n + 1]。第一个命题得证。

这样我们就可以给出如下的代码：

#include <cstdio>
int main()
{
    int n, arr[1002] = {1, 1};
    scanf("%d", &n);
    for (int i = 2; i <= n; i += 2)
        arr[i] = arr[i + 1] = arr[i - 1] + arr[i >> 1];
    printf("%d\n", arr[n]);
    return 0;
}

如此，解法的时间复杂度达到了O(n)。而且，这似乎是所有已经提交的题解中，在不压行的情况下，最短的代码了（然而这并没有什么卵用）。

四、后记

由于时间有限，再加上本人才疏学浅，如有谬误，请大家不吝赐教。在写题解的过程中，我也参考了他人的题解。为此，我向各位表示衷心的感谢！祝愿大家早日成为神犇，与君共勉！