蓝桥杯 2025 省赛真题：特殊红黑树颜色判断算法 Python 实现

• 根结点：(k=1, k-1=0, 二进制 0, 1 的个数 0(偶数), 红色✓)
• 第 2 行第 2 个：(k=2, k-1=1, 二进制 1, 1 的个数 1(奇数), 黑色✓)
• 第 3 行第 3 个：(k=3, k-1=2, 二进制 10, 1 的个数 1(奇数), 黑色✓)

Python 实现代码

版本 1：直接计算法

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)
    # 输出结果
    for result in results:
        print(result)

if __name__ == "__main__":
    main()

版本 2：使用内置函数优化

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()

版本 3：最优解（数学公式）

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 的个数=0，偶数）
2. 红色结点的子结点：
   • 左子结点：红色（二进制最后添加 0，1 的个数不变）
   • 右子结点：黑色（二进制最后添加 1，1 的个数+1）
3. 黑色结点的子结点：
   • 左子结点：黑色（二进制最后添加 0，1 的个数不变）
   • 右子结点：红色（二进制最后添加 1，1 的个数+1）

从根到某个结点的路径可以用二进制表示：

• 左子结点：在二进制末尾加 0
• 右子结点：在二进制末尾加 1

每次添加 1 时，颜色会翻转（红↔黑）。因此，最终颜色取决于路径中 1 的个数的奇偶性。

时间复杂度分析

1. 直接计算法：O(log k)，因为需要遍历 k-1 的二进制位
2. 优化版本：O(log k)，但使用内置函数更快
3. 递归解法：O(n)，需要递归 n 层
4. 位运算法：O(二进制中 1 的个数)，使用 Brian Kernighan 算法

对于最大数据范围（n≤30，k≤2^29），所有方法都足够快。

测试样例

样例输入

2 1 1 2 2 

计算过程

1. 查询 1：n=1, k=1
   • k-1 = 0，二进制：0
   • 1 的个数：0（偶数）
   • 结果：RED
2. 查询 2：n=2, k=2
   • k-1 = 1，二进制：1
   • 1 的个数：1（奇数）
   • 结果：BLACK

样例输出

RED BLACK 

更多测试用例

测试 1：第 3 行各个位置

4 3 1 # R
3 2 # B
3 3 # B
3 4 # R 

输出：

RED BLACK BLACK RED 

测试 2：第 4 行部分位置

3 4 1 # R
4 3 # B
4 6 # R 

输出：

RED BLACK RED 

边界情况处理

1. 最大范围测试：
   • n=30, k=2^29（约 5.4 亿）
   • 算法仍能快速计算
2. 最小范围测试：
   • n=1, k=1
   • 正确返回 RED
3. 奇偶性检查：
   • 确保正确处理偶数个 1 和奇数个 1 的情况

常见错误

1. 忘记 k-1：直接使用 k 而不是 k-1 进行二进制转换
2. 索引错误：将 1-based 索引当作 0-based 使用
3. 忽略 n 的作用：虽然 n 在公式中不需要，但题目要求输入，不能忽略

总结

这道题的关键是发现颜色与二进制表示中 1 的个数的奇偶性有关的规律。通过这个发现，我们可以用简单高效的算法解决问题。

主要解法对比：

推荐使用版本 2（优化版本），因为它：

1. 代码简洁易懂
2. 使用 Python 内置函数，效率高
3. 容易理解和调试

通过这道题，我们学习到：

1. 寻找数学规律的重要性
2. 如何将树结构问题转化为数学问题
3. 二进制运算在实际问题中的应用