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

__Aha__ · 2024-12-25 16:13:49 · 题解

思路

看到 2 的正整数次幂和，想到二进制。

显然，奇数的二进制最后一位是 1，所以其没有“优秀的拆分”，也可以这样理解：若干偶数之和，怎么可能等于奇数呢。

同理，偶数一定有“优秀的拆分”。

结果就是求出这个数中所有二进制上为 1 的部分，并把它们转化成十进制。

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long n,i=1;
    cin>>n;
    if(n%2){
        cout<<-1;
        return 0;
    }
    while(i<=n) i*=2;
    i/=2;
    while(n){
        n-=i;
        cout<<i<<" ";
        while(i>n) i/=2;
    }
    return 0;
}