2020 优秀的拆分 · 方案二直接看二进制位

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 2/5 · 共 783 字

奇数无解，偶数按位输出 2 的幂

2020
位运算

正文

// CSP-J 2020 复赛 T1 · 优秀的拆分（方案二）
// 原题：https://oj.yecheng.tv/p/CSPJ2020A
//
// 方案二 · 直接看二进制位
// 想明白一件事就够了：把一个数写成若干个互不相同的 2 的幂之和，
// 就是它的二进制表示 —— 第 i 位是 1，就表示这个和里有 2^i。
// 于是「优秀的拆分」唯一不合法的情形只有一个：第 0 位是 1，
// 也就是 n 是奇数（因为 2^0 = 1 不算正整数次幂）。
// 所以：奇数直接 -1；偶数就从高位到低位，把每个为 1 的位输出成 2^i。

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

int main() {
    freopen("power.in", "r", stdin);
    freopen("power.out", "w", stdout);

    int n;
    cin >> n;
    if (n % 2 == 1) {
        cout << -1 << "\n";
        return 0;
    }

    bool first = true;
    for (int i = 30; i >= 1; i--) {
        if (n & (1 << i)) {                // 第 i 位为 1，即含有 2^i
            if (!first) cout << " ";
            cout << (1 << i);
            first = false;
        }
    }
    cout << "\n";
    return 0;
}

2020 优秀的拆分 · 方案二 直接看二进制位

正文

CSP-J 标程 · 复赛真题的其它内容

2020 优秀的拆分 · 方案二直接看二进制位