题解：CF1977B Binary Colouring

· · 题解

构造。

Solution

考虑先将 x 转成二进制的形式；

举个例子，14 就转成 0,1,1,1（要倒着写）。

如果有两个 1 相邻，就将其下一位加 1，将两个 1 赋值为 -1,0；

即：

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

若该位上的值被累加到 2，则将其赋值为 0 并将下一位加 1，若下一位没有，则往末尾添加一个 1 即可；

即：

2^{i} \times 2=2^{i+1}

举个例子，14 可以被划分成：

(0,1,1,1) \Rightarrow (0,-1,0,2) \Rightarrow (0, -1,0,0,1)

code.