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

includeCPP · 2024-12-25 14:44:20 · 题解

遇到这种与 2 的次幂有关的题目，一个显然的思路是将所有数转化为二进制表示，这样可以很直观地发现一些性质。

本题即为一个很好的例子。我们把输入的 n 转换为二进制表示，显然地，任意一个十进制数都可以用二进制表示。

对于一个二进制数，其十进制即为：对于每一个二进制上为 1 的数位，设其为从小到大第 i 位，令 m_i 为 2^{i+1}，则 \sum m 即为其十进制表示下的数。

由于 2^0 不能参与构造，那么二进制表示下 n 的最低位也不能为 1，显然地，对于所有奇数，无法构造。对于所有偶数，可以构造，且为唯一解。

那么我们模仿上述思考的方法，从小到大依次枚举 n 的二进制位，遇到 1 就加入数组中，最后倒序输出即可。

本题数据范围 1 \le n \le 10^7，因此枚举 30 位即可。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=36;
int a[N];
int res=0;
int main(){
    int n;
    cin>>n;
    if(n&1){
        cout<<"-1";
        return 0;
    }
    int p=0;
    while(n>=1){
        if(n&1){
            a[++res]=(1<<p);
        }
        n>>=1;
        ++p;
    }
    for(int i=res;i>=1;i--){
        cout<<a[i]<<" ";
    }
    return 0;
}