【HNOI2006】【Luogu2320】鬼谷子的钱袋(进制,玄学)

            

problem

把一个数n进行拆分
拆分出来大于一的数两两不等,使得拆出来的数可以组成[1, n]间的所有数
求最少拆成多少个数及拆分方案。n <= 1000000000。

solution

记得之前bz上好像水过这题,看了题解,答案就是二进制的位数,,,当时觉得好有道理,,然后就交了,,也没看。。。不过好像,不会证明还是,,,,

然后这次,,我还是全网都没找到证明,,所以继续占坑待填。。。。
讲个找规律的例子,比较好理解。

举个例子:
我们可以假象一下 若m=12 则需要求得组合方案有(1 2 3 4 ……12)
我们可以把他们分成两份 (1 2 …… 6) (7 8 ……12)称左边的为L 右边的为R
很容易得知R中的每种方案都可以由(12/2)+左边的组合得出
再次分成两份(1 2 3)(4 5 6)
同理 当m为奇数时 显而易见地 只需把 (m/2)改为(m/2+1) 即可

所以结论是:
表示n以内的任何数字可以用1到n/2内的数字
那么表示n/2以内的任何数字可以用1到n/4以内的数字……
答案就是不断n/2的结果。。(数值上等于二进制位数)

codes

#include
using namespace std;
int t, a[100005];
int main(){
    int m;  cin>>m;
    while(m/2 != 0){
        t++;
        if(m%2 == 0)a[t] = m/2;
        if(m%2 == 1)a[t] = m/2+1;
        m /= 2;
    }
    cout<1<<'\n'<<1<<' ';
    for(int i = t; i >= 1; i--)
        cout<' ';
    return 0;
}
点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像