自动搬运

查看原文

来自洛谷，原作者为

	ControlVector **

搬运于2025-08-24 23:13:04，当前版本为作者最后更新于2025-04-12 19:03:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

容易证明以下两个性质：

1. 每行的前半部分和后半部分对应位颜色相反。
2. 每行的前半部分就是上一行，故答案只与 $k$ 有关，与 $n$ 无关。

每行从 $0$ 开始编号，编号 $x=k-1$

由 性质 2，答案与 $n$ 无关，不妨设节点在可能的最浅行，那么节点一定在该行的后半部分，不然可以更浅。

考虑 $x$ 的 二进制表示，例如 $x=(101001)_{2}$，则由 性质 1，该节点颜色与 $x_1=(001001)_{2}=(1001)_{2}$ 对应的节点颜色相反，$x_1$ 节点又与 $x_2=(0001)_{}=(1)_{2}$ 对应的节点颜色相反，$x_2$ 节点又与 $x_3=(0)_{2}=0$ 对应的节点颜色相反，而 $0$ 是根节点，颜色为 红色，那么 $x$ 的颜色为 黑色。

所以，颜色只和 $x$ 二进制表示中 $1$ 的数量的奇偶性相关，可使用内置函数 __builtin_parity 计算。

#include <iostream>
using namespace std;

int main() {
    int m, k;
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> k >> k;
        cout << (__builtin_parity(k-1) ? "BLACK\n" : "RED\n");
    }
}