题解 P7071 【优秀的拆分】

CZ_7 · 2020-11-07 14:28:16 · 题解

这题才不用转二进制呢！二进制太麻烦了！

这道题还是比较简单的。

首先我们明确一下题目要求：

对于正整数 n 的一种特定拆分，我们称它为“优秀的”，当且仅当在这种拆分下，n 被分解为了若干个不同的 2 的正整数次幂

也就是说所有带1的数都不是“优秀的拆分”。

那么直接判定退出就行了：

cin>>n;
    if(n%2==1){
        cout<<"-1";
        return 0;
    }

那么偶数怎么办呢？

我们首先定义一个a数组存储2的幂：

    a[1]=1;//初定义a[1]=2^1 
    for(int i=2;i<=26;i++){
        a[i]=a[i-1]*2;//每次乘2 
    }

其实25就够了，但是为了保险，还是定义一个26比较好。

那么如何输出呢？从大到小输出就行了：

for(int i=26;i>=2;i--){//从大往小输出 
        if(n>=a[i]){//能输出就输出 
            n-=a[i];
            cout<<a[i]<<' ';
        }
        if(n==0)return 0;//一个小优化 
    }

下面贴上完整代码：

#include<bits/stdc++.h>//万能头文件 
using namespace std;
int n;
long long a[30];//以防万一开ll 
int main(){
    cin>>n;
    if(n%2==1){
        cout<<"-1";
        return 0;
    }
    a[1]=1;//初定义a[1]=2^1 
    for(int i=2;i<=26;i++){
        a[i]=a[i-1]*2;//每次乘2 
    }
    for(int i=26;i>=2;i--){//从大往小输出 
        if(n>=a[i]){//能输出就输出 
            n-=a[i];
            cout<<a[i]<<' ';
        }
        if(n==0)return 0;//一个小优化 
    }
    return 0;
} 

我们下次再见！