洛谷P2320 鬼谷子的钱袋

P2320 06湖南 鬼谷子的钱袋

• • 171通过
  • 480提交
• 题目提供者xmyzwls
• 标签各省省选
• 难度普及+/提高

提交该题 讨论 题解 记录

最新讨论

• 题目有误
• 数据需要特判
• 评测系统太神了

题目描述

输入输出格式

输入格式：

输出格式：

输入输出样例

输入样例#1：

3

输出样例#1：

2

1  2
分析：首先要把题目读懂，即可以用n个1,1个2~m的数，通过加法组合成1~m的所有整数，当然，这所有的数字加起来要等于m,似乎有点复杂，该怎么处理呢？
      显然，不好直接处理本题，那么先假设一下m=10,如果想要组成1~m的所有整数，那么1是必须要的，因为如果不要1就不能组成1了，然后想，如果有一部分数通过加上一个数等于另外一部分数该多好！
      那么可以想到把10个数分成1~5和6~10,那么显然，1~5的数字加上5就能够组成6~10,所以取5，然后可以发现这就是不断地求子问题，那么递归，但是5是奇数怎么办？因为c++中的除法向下取整，所以分成1~2,3~5,1~2必须加上3才能组成3~5，那么把3取上，3又分成1和2,3显然1必须加上2才能取2,3，那么取2，因为1是必须取的，所以取1.
      透过现象看本质，可以发现求解的过程很像倍增，每一次可以取的数目都*2,那么如果2^n > m,那么n即为所求的袋子数，如何求每个袋子装的金币呢？根据之前模拟的过程记录答案即可.
      通过这道题要明白，一些用字母表示的数不好直接处理，可以设特殊值，从现象看本质，最后想到求解的方法!
代码可以缩成1个循环!

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

int m,tot,cnt,ans[];

int main()

{

    scanf("%d", &m);

    for (int i = ; ; i = i * )

    {

        tot++;

        if (i > m)

        {

            printf("%d\n", tot - );

            break;

        }

    }

    printf("1 ");   //1是肯定要选的

    while (m /  != )

    {

        ++cnt;

        if (m %  == )

            ans[cnt] = m / ;

        if (m %  == )

            ans[cnt] = m /  + ;

        m /= ;

    }

    for (int i = cnt; i >= ; i--)   //因为要从小到大输出，所以逆序输出

        printf("%d ", ans[i]);

    return ;

}