B. Binary Colouring

给你一个正整数 $x$ 。请找出下列条件成立的任意整数数组 $a_{0}, a_{1}, \dots, a_{n - 1}$ ：

$1 \leq n \leq 32$ ,
$a_{i}$ 是 $1$ ， $0$ 或 $- 1$
$x = \sum_{i = 0}^{n - 1} a_{i} \cdot 2^{i}$ ,
不存在同时满足 $a_{i} \neq 0$ 和 $a_{i + 1} \neq 0$ 的索引 $0 \leq i \leq n - 2$ 。

可以证明，在问题的限制条件下，总是存在一个有效的数组。

Solution

位运算

本题的难点主要是注意到一个变形：

a^{i} + a^{i + 1} = a^{i + 2} - a^{i}

若某位数的第 $i$ 位满足： $(a_{i}, a_{i + 1}) = (1, 1)$ ，则不满足要求，需要变为 $(a_{i}, a_{i + 1}, a_{i + 2}) = (- 1, 0, 1)$

void solve() {
    int x;cin >> x;
    vector<int> ans;
    for (int i = 0;i <= __lg(x);i++) {
        if (((x >> i) & 1) && ((x >> (i + 1)) & 1)) {
            ans.push_back(-1);
            x += (1 << (i + 1));
        } else {
            ans.push_back((x >> i) & 1);
        }
    }
    cout << ans.size() << '\n';
    for (auto x : ans)cout << x << " ";cout << '\n';
}