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

Amoribus · 2024-12-25 12:27:54 · 题解

• 我们这样考虑，一个十进制整数必然可以化为二进制，也就是写成若干个 2 的非负整数次幂之和，如果这个数是奇数，那么它二进制的末尾必然是 1，也就是它的拆分中必然有一项 2^0，故无解。
• 如果是偶数则它的二进制末位是 0，也就是必定能写成若干个 2 的正整数次幂之和，因此必然有解。我们可以先记录 10^7 以内的 2 的正整数次幂，然后从大到小，将 n 试着减去这些 2 的正整数次幂。（感性地理解一下，这样做是正确的。）然后输出答案即可。

我采用了递归的写法，相对比较直观。

#include<bits/stdc++.h>
using namespace std;
int n;
int p[40]={0,2,4,8,16,32,64,128,256,512,1024,2048,\
4096,8192,16384,32768,65536,131072,262144,524288,\
1048576,2097152,4194304,8388608,16777216,33554432,\
67108864,134217728,268435456,536870912,1073741824};
void f(int x){
    if(x==1||x==0) return;
    for(int i=30;i>=1;i--){
        if(x>=p[i]){
            cout<<p[i]<<" ";
            f(x-p[i]);
            break;
        }
    }
}
int main()
{
    cin>>n;
    if(n%2==1){
        cout<<-1<<endl;
        return 0;
    }
    else{
        f(n);
    }
}