深度剖析2016蓝桥杯（洛谷P8644）机器人塔问题及C++实现

1周前 (08-14)比赛题解72

一、问题背景

机器人塔是2016年蓝桥杯国赛B组的一道经典题目。题目描述给定A、B两种机器人，A机器人站在两个相同机器人上方会生成一个A机器人，站在两个不同机器人上方会生成一个B机器人。我们需要计算用M个A和N个B机器人能搭建多少种不同的k层机器人塔。

二、解题思路

数学基础验证：首先验证M+N是否能构成k层三角形数（k*(k+1)/2）
位运算枚举：使用位运算枚举最底层的所有可能排列组合
自底向上验证：从底层开始逐层推导上层机器人类型，并统计剩余机器人数量

三、代码解析（完整代码+注释）

#include <iostream>
#include <vector>
using namespace std;

// 计算整数x的二进制表示中1的个数
int count_bits(int x) {
    int cnt = 0;
    while (x) {
        cnt += x & 1;  // 检查最低位是否为1
        x >>= 1;       // 右移一位
    }
    return cnt;
}

int main() {
    int M, N;  // A和B机器人的数量
    cin >> M >> N;
    
    // 计算总层数k（三角形数）
    int total = M + N;
    int k = 1;
    while (k*(k+1)/2 < total) k++;
    
    // 如果不能正好构成k层三角形塔
    if (k*(k+1)/2 != total) {
        cout << 0 << endl;
        return 0;
    }

    int ans = 0;
    // 枚举最底层所有可能的排列（使用位掩码）
    for (int mask = 0; mask < (1 << k); mask++) {
        int b = count_bits(mask);  // B机器人数
        int a = k - b;             // A机器人数
        
        // 初步筛选：底层A/B数量不超过总供给
        if (b > N || a > M) continue;
        
        int valid = 1;  // 标记当前方案是否有效
        int current = mask;  // 当前层掩码
        int remain_a = M - a;  // 剩余A机器人
        int remain_b = N - b;  // 剩余B机器人
        
        // 自底向上构建各层
        for (int layer = k-1; layer >= 1 && valid; layer--) {
            int next_layer = 0;  // 下一层的掩码
            
            for (int i = 0; i < layer; i++) {
                bool left = current & (1 << i);    // 左机器人类型
                bool right = current & (1 << (i+1)); // 右机器人类型
                
                if (left == right) { // 生成A机器人
                    if (remain_a <= 0) { valid = 0; break; }
                    remain_a--;
                    next_layer |= (0 << i);  // 设置对应位为0(A)
                } else { // 生成B机器人
                    if (remain_b <= 0) { valid = 0; break; }
                    remain_b--;
                    next_layer |= (1 << i);  // 设置对应位为1(B)
                }
            }
            current = next_layer;  // 移动到上一层
        }
        
        // 验证机器人是否正好用完
        if (valid && remain_a == 0 && remain_b == 0) {
            ans++;  // 合法方案计数
        }
    }
    
    cout << ans << endl;
    return 0;
}