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

cjy2008 · 2020-11-07 22:59:51 · 题解

先分析题目： 看到“2 的正整数次幂”就可以知道这是一道进制转换题:

只需要把输入的数转换成二进制串就可以了！

首先我们知道奇数是一定不行的，因为奇数拆分后一定含有1。这也不难理解：2的正整数次幂一定是偶数。

所以有如下代码：

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

咱们继续分析：

易知偶数是一定存在拆分的 不然要二进制干什么

接下来就是如何找到这个拆分了。这里介绍一种数学方法：每次除以2直到n=0，把余数倒过来念。如:

所以有如下代码

void iofind(int p,int u){
    if(p==0) return;
    if(p%2==1) k[u]=1;//k[i]=1表示拆分中有2的i次方
    iodfs(p/2,u+1);
}

iofind(n,0);

最后乘方输出即可

for(int i=800;i>=1;i--){//奇怪的码风
    if(k[i]==1){
        printf("%d ",iopow(2,i-1)); 
    } 
}

放代码

#include<bits/stdc++.h>//考场代码，如有不足，请多谅解
using namespace std;
int n;
int k[1000]; 
void iofind(int p,int u){
    if(p==0) return;
    if(p%2==1) k[u]=1;
    iodfs(p/2,u+1);
}
int iopow(int n,int s){  //这是求n的s次幂的函数，懒得写快速幂
    int o=n;
    for(int i=1;i<=s;i++){
        n*=o;
    }
    return n;
}
int main(){
//  freopen("power.in","r",stdin);
//  freopen("power.out","w",stdout);
    scanf("%d",&n);
    if(n%2==1){
        printf("-1");
        return 0;
    }
    iofind(n,0);
    for(int i=800;i>=1;i--){
        if(k[i]==1){
            printf("%d ",iopow(2,i-1)); 
        } 
    }
//  fclose(stdin);
//  fclose(stdout);
    return 0;
}

第一次写题解，如有不足，请多谅解！