本博客为作者原创，要转载请写明出处！

尊敬的读者们，如果你认为这篇题解有问题/错误，或有其他解法，请评论/私信告诉作者本人，将被列在“特别鸣谢”名单内！

特别鸣谢（按提供意见/建议的时间先后顺序排序）

昵称	时间	建议/意见具体内容
@牛客964762634号	2022-10-23 20:35	创建本题解

总任务

阅读题面
理解题意
完成代码

1. 阅读题面

CSP-J 2020 优秀的拆分（ $p o w e r$ ）

题目描述

一般来说，一个正整数可以拆分成若干个正整数的和。

例如， $1 = 1$ ， $10 = 1 + 2 + 3 + 4$ 等。对于正整数 $n$ 的一种特定拆分，我们称它为“优秀的”，当且仅当在这种拆分下， $n$ 被分解为了若干个不同的 $2$ 的正整数次幂。注意，一个数 $x$ 能被表示成 $2$ 的正整数次幂，当且仅当 $x$ 能通过正整数个 $2$ 相乘在一起得到。

例如， $10 = 8 + 2 = 2^{3} + 2^{1}$ 是一个优秀的拆分。但是， $7 = 4 + 2 + 1 = 2^{2} + 2^{1} + 2^{0}$ 就不是一个优秀的拆分，因为 $1$ 不是 $2$ 的正整数次幂。

现在，给定正整数 $n$ ，你需要判断这个数的所有拆分中，是否存在优秀的拆分。若存在，请你给出具体的拆分方案。

输入格式

输入只有一行，一个整数 $n$ ，代表需要判断的数。

输出格式

如果这个数的所有拆分中，存在优秀的拆分。那么，你需要从大到小输出这个拆分中的每一个数，相邻两个数之间用一个空格隔开。可以证明，在规定了拆分数字的顺序后，该拆分方案是唯一的。

若不存在优秀的拆分，输出 -1。

样例 #1

样例输入 #1

样例输出 #1

4 2

样例 #2

样例输入 #2

样例输出 #2

-1

提示

样例 1 解释

$6 = 4 + 2 = 2^{2} + 2^{1}$ 是一个优秀的拆分。注意， $6 = 2 + 2 + 2$ 不是一个优秀的拆分，因为拆分成的 $3$ 个数不满足每个数互不相同。

数据规模与约定

对于 $20 %$ 的数据， $n \le 10$ 。
对于另外 $20 %$ 的数据，保证 $n$ 为奇数。
对于另外 $20 %$ 的数据，保证 $n$ 为 $2$ 的正整数次幂。
对于 $80 %$ 的数据， $n \le 1024$ 。
对于 $100\%$ 的数据， $1 \le n \le {10}^7$ 。

理解题意

1. 我们需要干什么？

我们需要干什么？

我们需要“优秀的拆分”一个正整数。

如何实现？

枚举2的正整数次幂。

有特殊情况吗？有什么特殊情况？

有的。当拆分 $n$ 后有 $2^{0}$ ，即 $n \mod 2 == 1$ 时，该数就无法实现“优秀的拆分”，所以输出 -1 。

2. 我们需要怎么做？

我们需要怎么做？

拆分 $n$ （枚举 $2$ 的正整数次幂，注意 $n \mod 2 == 1$ 的情况）。

代码实现为：

#include<bits/stdc++.h>
using namespace std;
int n,now=1,i,j,ans;
bool a[5010];
int main(){
    //freopen("power.in","r",stdin);
    //freopen("power.out","w",stdout);
    cin>>n;
    if(n%2!=0){
        cout<<-1<<endl;
        return 0;
    }
    while(now*2<=n){
        now*=2;
        i++;
    }
    j=i;
    while(now>=2){
        if(n-now>=0){
            a[j]=true;
            n-=now;
        }
        j--;
        now/=2;
    }
    for(int j=i;j>=1;j--){
        if(!a[j]){
            continue;
        }
        ans=pow(2,j);
        cout<<ans<<" ";
    }
    cout<<endl;
    return 0;
}

3. 我们能优化代码吗？

我们能优化代码吗？

显然，答案当然是可以的。

怎么优化？

不知道有没有人想到了这个东西——二进制。没错，本题可以理解为十进制数转二进制数！

十进制数转二进制数的基本方法这里不讲了，直接上代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[5010],x,t,p;
int main(){
    //freopen("power.in","r",stdin);
    //freopen("power.out","w",stdout);
    cin>>n;
    if(n%2!=0){
        cout<<"-1"<<endl;
        return 0;
    }
    t=n;
    p=1;
    while(t){
        if(t%2!=0){
            a[++x]=p;
        }
        p*=2;
        t/=2;
    }
    for(int i=x;i>=1;i--){
        cout<<a[i]<<" ";
    }
    cout<<endl;
    return 0;
}

代码展示

请勿抄袭！

解法1（AC）

#include<bits/stdc++.h>
using namespace std;
int n,now=1,i,j,ans;
bool a[5010];
int main(){
    //freopen("power.in","r",stdin);
    //freopen("power.out","w",stdout);
    cin>>n;
    if(n%2!=0){
        cout<<-1<<endl;
        return 0;
    }
    while(now*2<=n){
        now*=2;
        i++;
    }
    j=i;
    while(now>=2){
        if(n-now>=0){
            a[j]=true;
            n-=now;
        }
        j--;
        now/=2;
    }
    for(int j=i;j>=1;j--){
        if(!a[j]){
            continue;
        }
        ans=pow(2,j);
        cout<<ans<<" ";
    }
    cout<<endl;
    return 0;
}

解法2（AC）

#include<bits/stdc++.h>
using namespace std;
int n,a[5010],x,t,p;
int main(){
    //freopen("power.in","r",stdin);
    //freopen("power.out","w",stdout);
    cin>>n;
    if(n%2!=0){
        cout<<"-1"<<endl;
        return 0;
    }
    t=n;
    p=1;
    while(t){
        if(t%2!=0){
            a[++x]=p;
        }
        p*=2;
        t/=2;
    }
    for(int i=x;i>=1;i--){
        cout<<a[i]<<" ";
    }
    cout<<endl;
    return 0;
}

首先发布：CSDN程序员社区

随后发布：洛谷博客

作者：牛客964762634号

CSP-J 2020 第二轮 第一题 优秀的拆分（power）题解

总任务