题解：P7071 [CSP-J2020] 优秀的拆分

liyingchao · 2024-12-25 13:39:45 · 题解

题目链接(P7071)

以下是思路 :

• 首先呢，我们先处理无解的情况。因为2的正整数次方无论如何都是偶数。所以n只要是奇数，就输出-1。
• 其次，我们去处理可行的情况，我们可以举几个例子：
  例一:12
  12以下的2的正整数次幂有 : 2 , 4 , 8
  那么，12=4+8，输出:8 4
  例二:18
  12以下的2的正整数次幂有 : 2 , 4 , 8 , 16
  那么，18=16+2（不是8+8是因为题目要求不同）
  综上所述：输出的时候，就从大往小计算和输出，可以满足题目要求。
• 现在呢，我们的两种情况都处理完了。
• 剩下的一些要点就随注释在代码里了。

  AC code :

#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;
}