题解：CF1977B Binary Colouring

· · 题解

思路分析

题面一出来，就很容易想到先把这个数拆成二进制再处理。

我们注意到，拆出来后的不合法情况只有两个 1 相邻的情况。然而，我们同时也知道，2^i+2^{i+1}=2^{i+2}-2^i，因此，\texttt{0 1 1} 可以被替换成 \texttt{1 0 -1}。

此时就可以有两种思路：

  1. 可以选择将连续的若干个 1 替换成零，将最后一个 1 替换成 -1，再将第一个 1 前面的 0 替换为 1。当然了，需要特判形如：11\dots1011\dots 的情况。

  2. 可以仅将两个连续的 1 替换成 \texttt{1 0 -1}。这样子的话就不需要特判了，但是需要进行进位。

我采取的是第二种思路。代码如下：

#include <bits/stdc++.h>
using namespace std;
int t, n, ans[32];
signed main() {
    ios::sync_with_stdio(0);
    cin >> t;
    while (t--) {
        memset(ans, 0, sizeof ans);
        cin >> n;
        for (int i = 0; i < 30; ++i)
            ans[i] = n & 1, n >>= 1;
        for (int i = 0; i < 30; ++i) {
            if (ans[i] == 2) ans[i + 1]++, ans[i] = 0;
            if (ans[i] == 1 && ans[i + 1] == 1)
                ans[i + 2]++, ans[i] = -1, ans[i + 1] = 0;
        }
        cout << "32\n";
        for (int i = 0; i <= 31; ++i)
            cout << ans[i] << " ";
        cout << endl;
    }
    return 0;
}