Python算法
蓝桥杯 2025 省赛真题：特殊红黑树颜色判断算法 Python 实现
针对蓝桥杯 2025 省赛中的特殊红黑树问题，通过观察树的构造规律发现颜色与二进制位中 1 的个数奇偶性相关。利用 Thue-Morse 序列变体原理，提供三种 Python 实现方案：直接计算、内置函数优化及位运算最优解。核心在于将 k-1 转换为二进制并统计 1 的个数，偶数对应红色，奇数对应黑色。该算法时间复杂度为 O(log k)，适用于大规模数据查询，解决了传统递归方法效率低下的问题。
针对蓝桥杯 2025 省赛中的特殊红黑树问题，通过观察树的构造规律发现颜色与二进制位中 1 的个数奇偶性相关。利用 Thue-Morse 序列变体原理，提供三种 Python 实现方案：直接计算、内置函数优化及位运算最优解。核心在于将 k-1 转换为二进制并统计 1 的个数，偶数对应红色，奇数对应黑色。该算法时间复杂度为 O(log k)，适用于大规模数据查询，解决了传统递归方法效率低下的问题。
小蓝构造了一棵特殊的红黑树，构造规则如下：
树的前几层形态示意图如下：
R(1,1) / \ R(2,1) B(2,2)
/ \ / \
R(3,1) B(3,2) B(3,3) R(3,4)
我们需要判断第 n 行（从上往下数）第 k 个（从左往右数）结点的颜色是红色 (RED) 还是黑色 (BLACK)。
观察这棵树的规律：
第 n 行第 k 个结点的颜色可以通过以下方式判断：
证明：
import sys
def count_ones(num):
"""计算二进制中 1 的个数"""
count = 0
while num > 0:
count += num & 1 # 检查最低位是否为 1
num >>= 1 # 右移一位
return count
def get_color(n, k):
"""
获取第 n 行第 k 个结点的颜色
n: 行号（从 1 开始）
k: 列号（从 1 开始）
返回："RED" 或 "BLACK"
"""
# 将 k 转换为 0-based 索引
index = k - 1
# 计算二进制中 1 的个数
ones_count = count_ones(index)
# 根据 1 的个数的奇偶性判断颜色
if ones_count % 2 == 0:
return "RED"
else:
return "BLACK"
def main():
# 读取输入
data = sys.stdin.read().strip().split()
if not data:
return
m = int(data[0]) # 查询次数
results = []
idx = 1
for _ in range(m):
n = int(data[idx]) # 行号
k = int(data[idx + 1]) # 列号
idx += 2
# 获取颜色并保存结果
color = get_color(n, k)
results.append(color)
result results:
(result)
__name__ == :
main()
import sys
def get_color_optimized(n, k):
"""
优化版本：使用 Python 内置函数计算二进制中 1 的个数
"""
# 将 k-1 转换为二进制，计算 1 的个数
ones_count = bin(k - 1).count('1')
# 根据 1 的个数的奇偶性判断颜色
return "RED" if ones_count % 2 == 0 else "BLACK"
def main():
# 读取输入
data = sys.stdin.read().strip().split()
if not data:
return
m = int(data[0])
results = []
idx = 1
for _ in range(m):
n = int(data[idx])
k = int(data[idx + 1])
idx += 2
# 注意：行号 n 其实不需要用于计算，因为规律与 n 无关
# 但题目要求输入 n，所以保留
color = get_color_optimized(n, k)
results.append(color)
# 输出结果
print("\n".join(results))
if __name__ == "__main__":
main()
import sys
def main():
data = sys.stdin.read().strip().split()
if not data:
return
m = int(data[0])
outputs = []
idx = 1
for _ in range(m):
# 读取 n 和 k（虽然 n 在公式中不需要，但题目要求输入）
n = int(data[idx])
k = int(data[idx + 1])
idx += 2
# 核心公式：计算 k-1 的二进制表示中 1 的个数的奇偶性
# 使用位运算快速计算
x = k - 1
parity = 0 # 奇偶性：0 表示偶数个 1，1 表示奇数个 1
while x:
parity ^= 1 # 每遇到一个 1，奇偶性翻转
x &= x - 1 # 清除最低位的 1（Brian Kernighan 算法）
# 根据奇偶性输出颜色
outputs.append("RED" if parity == 0 else "BLACK")
print("\n".join(outputs))
if __name__ == "__main__":
main()
为什么可以通过二进制中 1 的个数判断颜色？
让我们分析一下树的构建规律：
从根到某个结点的路径可以用二进制表示：
每次添加 1 时，颜色会翻转（红↔黑）。因此，最终颜色取决于路径中 1 的个数的奇偶性。
对于最大数据范围（n≤30，k≤2^29），所有方法都足够快。
2 1 1 2 2
RED BLACK
4 3 1 # R
3 2 # B
3 3 # B
3 4 # R
输出：
RED BLACK BLACK RED
3 4 1 # R
4 3 # B
4 6 # R
输出：
RED BLACK RED
这道题的关键是发现颜色与二进制表示中 1 的个数的奇偶性有关的规律。通过这个发现，我们可以用简单高效的算法解决问题。
主要解法对比：
| 方法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 二进制计数法 | O(log k) | O(1) | 高效、简洁 | 需要发现规律 |
| 递归法 | O(n) | O(n) | 直观、易理解 | 效率较低 |
| 位运算法 | O(二进制中 1 的个数) | O(1) | 最快 | 需要位运算知识 |
推荐使用版本 2（优化版本），因为它：
通过这道题，我们学习到：
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
解析常见 curl 参数并生成 fetch、axios、PHP curl 或 Python requests 示例代码。 在线工具，curl 转代码在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online