题解 【[HNOI2006]鬼谷子的钱袋】

鬼谷子的钱袋】"/>

题解 【[HNOI2006]鬼谷子的钱袋】

题目传送门->在这里

首次读题没有什么思路，毕竟也是在 神奇的解法 \text{神奇的解法} 神奇的解法里的，多次读题之后，才发现这到题的正解。

简化题目：

给定整数 N N N，求至少需要 M M M个数，使其和可以分别为 1 … … N − 1 1……N-1 1……N−1,求 M M M和数列。

分析题目：

通过简化题目，我们不难发现这就是一个分治的题目，并且题目的范围貌似已经提示的很明确了。 1 ≤ m ≤ 1000000000 1≤m ≤1000000000 1≤m≤1000000000，用普通的枚举，搜索，甚至 d p dp dp，都一定会超时，唯独 O ( l o g N ) O(log N) O(logN)的二分不会超时。

深入分析：

我们拿样例来解释：

3 3 3可以被分解成 1 1 1和 2 2 2，这不是废话吗

我们在取一个数作为例子，例如，我们取 10 10 10这个数。

10 10 10 可以分解成 5 5 5和 5 5 5，在拆开 5 5 5后得到 3 3 3和 2 2 2，然后在把 2 2 2拆成 1 1 1和 1 1 1。

最后可以得到 10 10 10被拆解成了 1 , 1 , 3 , 5 1,1,3,5 1,1,3,5。

也就是说，我们对一个 N N N，可以每一次都对它进行 N / 2 N/2 N/2的操作，直到为 N N N被分解成 0 0 0为止。

程序实现：

对于每个值的存储，我们开一个数组，用来每次 N / 2 N/2 N/2的数字，然后倒序输出。

• 以下为本题核心代码

while(m){a[++k]=(m+1)/2;m/=2;}

数组因为是从大到小存储的，所以我们要倒序输出

代码如下

#include<cstdio>
int a[200001];
int main()
{int m,k=0;scanf("%d",&m);while(m){a[++k]=(m+1)/2;m/=2;}printf("%d\n",k);for(int i=k;i>=1;i--)printf("%d ",a[i]);putchar('\n');return 0;
}

总之，本题就是一个难想的题，只要有思路，代码的实现就不会很难。

另外打个广告 ： B l o g \color{cyan}{Blog} Blog