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

lailai0916 · 2021-09-29 16:41:53 · 题解

解题思路

显然 2 的正整数次幂都是偶数，多个偶数相加不可能得到奇数。因此 n 为奇数时无解，输出 -1。

若 n 为偶数，则它的二进制最低位为 0，而二进制第 i 位（i>0）刚好对应 2 的 i 次幂。

因此用 1<<31-__builtin_clz(n) 取出当前 n 的二进制最高位对应值，从大到小依次输出并减去即可。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    if(n&1)
    {
        cout<<-1<<'\n';
        return 0;
    }
    while(n)
    {
        int t=1<<31-__builtin_clz(n);
        cout<<t<<' ';
        n-=t;
    }
    return 0;
}