题解 P7071 【优秀的拆分（暂无数据）】

Colead · 2020-11-07 17:51:35 · 题解

P7071

大家好，我是一个刚受CSP2020折磨摧残完的蒟蒻，来讲讲CSP2020的T1。

首先我们必须知道的是：

任何数都可以表示为2的非负次幂相加的形式。

因为x=x*1

而1=2^0

每两个2^0可组成一个2^1,每两个2^1可组成一个2^2，以此类推……

而本题中是什么？正整数次幂！

也就是没有了2^0这一项！

这代表了什么？

所有的奇数都无法表示！

那偶数的时候呢？

先看看2的最大次方是几，然后倒序枚举能减就减即可。

时间复杂度：O(log n)

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    if(n%2)//无法整除。
    {
        cout<<"-1"<<endl;
        return 0;
    }
    else
    {
        int cnt;
        for(int i=1;;i++)
        {
            if((int)pow(2,i)>=n)//枚举最大次方。
            {
                cnt=i;
                break;
            }
        }
        for(int i=cnt;i>=1;i--)
        {
            if(n>=(int)pow(2,i))
            {
                cout<<(int)pow(2,i)<<" ";//能减就减。
                n-=(int)pow(2,i);
            }
        }
        return 0;
    }
}