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

soywcy · 2020-11-07 20:59:15 · 题解

• if 语句出了大问题，现已修正

• 关于 数组 a 长度的问题亦已修正

上机时题目标题差点吓死我。

步入正题

题目传送门

分析：

样例输入

6

样例输出

4 2

(1) 可以证明：一切奇数都不存在优秀的拆分，因为2的正整数次幂为偶数。

所以一遇到奇数就输出-1。

但是也有一个细节要注意：0也不存在优秀的拆分。

所以一开始的判断可以这么写：

if (n%2==1 || n==0){
    printf("-1");
    return 0;
}

(2)观察样例：

咦？怎么和样例输出一模一样？

再试一个：

可以证明：16\ \ 8\ \ 4 是 28的优秀的拆分。

所以我们思路来了：

把 n 转换为2进制，每取到一位"1"就变成十进制，再从大到小输出即为 n 优秀的拆分。

具体看核心代码：

void change(int b){
    int res=0; //统计a数组里有多少个元素并且作为指数
    while(b){
        if (b&1){  // 从右至左取每一位并判断是否为0
            a[res]=pow(2,res);  // 变成十进制
        } 
        res++;
        b>>=1;// 右移一位
    }
    idx=res;   // 记录个数，便于主程序输出
}

最后贴上代码：

#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
int n,a[30],idx;
void change(int b){
    int res=0;
    while(b){
        if (b&1) a[res]=pow(2,res);
        res++;
        b>>=1;
    }
    idx=res;
}

int main(){
    scanf("%d",&n);
    if (n%2==1 || n==0){
        printf("-1");
        return 0;
    }
    change(n);
    for(int i=idx;i>=1;i--)
        if (a[i]!=0) printf("%d ",a[i]);
    return 0;
}