Binary Colouring

题面翻译

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

• $1 \le n \le 32$,
• $a_i$ 是 $1,0$ 或 $-1$，
• $x =\sum\limits_{i=0}^{n-1}a_i2^i$,
• 不存在一个 $i$ 使得 $a_i\neq0$ 且 $a_{i+1}\neq 0$。

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

题目描述

You are given a positive integer $ x $ . Find any array of integers $ a_0, a_1, \ldots, a_{n-1} $ for which the following holds:

• $ 1 \le n \le 32 $ ,
• $ a_i $ is $ 1 $ , $ 0 $ , or $ -1 $ for all $ 0 \le i \le n - 1 $ ,
• $ x = \displaystyle{\sum_{i=0}^{n - 1}{a_i \cdot 2^i}} $ ,
• There does not exist an index $ 0 \le i \le n - 2 $ such that both $ a_{i} \neq 0 $ and $ a_{i + 1} \neq 0 $ .

It can be proven that under the constraints of the problem, a valid array always exists.

输入格式

Each test contains multiple test cases. The first line of input contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The description of the test cases follows.

The only line of each test case contains a single positive integer $ x $ ( $ 1 \le x < 2^{30} $ ).

输出格式

For each test case, output two lines.

On the first line, output an integer $ n $ ( $ 1 \le n \le 32 $ ) — the length of the array $ a_0, a_1, \ldots, a_{n-1} $ .

On the second line, output the array $ a_0, a_1, \ldots, a_{n-1} $ .

If there are multiple valid arrays, you can output any of them.

样例 #1

样例输入 #1

7
1
14
24
15
27
11
19

样例输出 #1

1
1
5
0 -1 0 0 1
6
0 0 0 -1 0 1
5
-1 0 0 0 1
6
-1 0 -1 0 0 1
5
-1 0 -1 0 1
5
-1 0 1 0 1

提示

In the first test case, one valid array is $ [1] $ , since $ (1) \cdot 2^0 = 1 $ .

In the second test case, one possible valid array is $ [0,-1,0,0,1] $ , since $ (0) \cdot 2^0 + (-1) \cdot 2^1 + (0) \cdot 2^2 + (0) \cdot 2^3 + (1) \cdot 2^4 = -2 + 16 = 14 $ .

可以把这个要求的数转化为二进制在翻转过来，位数是1，代表要加2的位数次方，可是题目要求不能两个相邻的1在一起，观察此位数i和i+1都是1，就是2^i+2^(i+1),这个式子可以转化成2^(i+2)-2^i,就是在i初填-1，i+2处填2，i+1处填0，但是不能有2，而2*2^i又可以转化成2^(i+1)，所以在a[i]等于2处让a[i+1]+1即可，这样保证不会有两个非零数相邻

#include <iostream>
using namespace std;
using namespace std;
const int N = 32 + 10;
int t, n, a[N];
void solve(int x) {
    int cnt = 0, ans = 0;
    //如果将其反转，那么a数组就是x的二进制。所以不反转刚好起到了转成二进制并反转的作用
    while (x) {
        a[++cnt] = (x & 1);
        x >>= 1;
    }
    a[cnt + 1] = 0;
    for (int i = 1; i <= cnt; ++i) {
        if (a[i] == 2)//进位
            a[i] = 0, ++a[i + 1];
        if (a[i] == 1 && a[i + 1] == 1)//判断当有连续两个1的情况
            a[i] = -1, a[i + 1] = 0, ++a[i + 2];
    }
    for (int i = 1; i <= cnt + 1; ++i)
        if (a[i]) ans = i;//找到最终的位数
    printf("%d\n", ans);
    for (int i = 1; i <= ans; ++i)
        printf("%d ", a[i]);
    printf("\n");
    return;
}
int main() {
    cin >> t;
    while (t--) {
        cin >> n;
        solve(n);
    }
    return 0;
}