题解：P12141 [蓝桥杯 2025 省 A] 红黑树

overdoze · 2025-04-13 07:23:54 · 题解

这道题我不会用进制和位运算，但是我会递归。

首先，暴力枚举红黑树，得到下表：

R
RB
RBBR
RBBRBRRB
RBBRBRRBBRRBRBBR

其中，R 表示红色，B 表示黑色。

我们可以给它们对半分（除了第一层），得到下表：

R
R B
RB BR
RBBR BRRB
RBBRBRRB BRRBRBBR

发现了没有？

第 k 层下标 \le 2^{k-2} 的元素是 k-1 层当前下标对应元素的颜色。

而第 k 层下标 > 2^{k-2} 的元素是第 k-1 层当前节点 -2^{k-2} 下标对应元素的颜色取反（即红变成黑，黑变成红）。

我们就可以使用递归解答。

AC 记录

代码就别抄我了。