鬼谷子的钱袋】"/>
题解 【[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
更多推荐
题解 【[HNOI2006]鬼谷子的钱袋】
发布评论