首页 > 代码库 > 洛谷P2320 鬼谷子的钱袋
洛谷P2320 鬼谷子的钱袋
P2320 06湖南 鬼谷子的钱袋
- 171通过
- 480提交
- 题目提供者xmyzwls
- 标签各省省选
- 难度普及+/提高
提交该题 讨论 题解 记录
最新讨论
- 题目有误
- 数据需要特判
- 评测系统太神了
题目描述
输入输出格式
输入格式：
输出格式：
输入输出样例
输入样例#1：
3
输出样例#1：
21 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[100010];int main(){ scanf("%d", &m); for (int i = 1; ; i = i * 2) { tot++; if (i > m) { printf("%d\n", tot - 1); break; } } printf("1 "); //1是肯定要选的 while (m / 2 != 0) { ++cnt; if (m % 2 == 0) ans[cnt] = m / 2; if (m % 2 == 1) ans[cnt] = m / 2 + 1; m /= 2; } for (int i = cnt; i >= 1; i--) //因为要从小到大输出，所以逆序输出 printf("%d ", ans[i]); return 0;}
洛谷P2320 鬼谷子的钱袋
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。