[蓝桥杯]机器人塔

题目描述

X 星球的机器人表演拉拉队有两种服装，A 和 B。

他们这次表演的是搭机器人塔。

类似：

A

B B

A B A

A A B B

B B B A B

A B A B B A

队内的组塔规则是：

A 只能站在 AA 或 BB 的肩上。

B 只能站在 AB 或 BA 的肩上。

你的任务是帮助拉拉队计算一下，在给定 A 与 B 的人数时，可以组成多少种花样的塔。

输入描述

输入一行两个整数 M,NM,N（0<M,N<5000<M,N<500）,分别表示 A、B 的人数，保证人数合理性。

输出描述

要求输出一个整数，表示可以产生的花样种数。

输入输出样例

示例

输入

1 2

输出

3

运行限制

• 最大运行时间：10s
• 最大运行内存: 512M

总通过次数: 2263  |  总提交次数: 2708  |  通过率: 83.6%

方法思路

为了解决机器人塔问题，我们需要计算在给定A和B机器人数量时，能组成的塔的种类数。塔的构建规则是：

• A只能站在AA或BB的肩上

• B只能站在AB或BA的肩上

解决思路

算法特点

1. 确定塔的层数：根据总人数M+N，求解满足k(k+1)/2 = M+N的整数k

2. 枚举基座层：基座层有k个机器人，每个机器人可以是A或B，共2^k种可能

3. 模拟建塔过程：

   • 从基座层开始向上构建

   • 每层机器人由下一层的两个相邻机器人决定：若两个机器人相同，则上层为A；若不同，则上层为B

4. 统计A的数量：在构建过程中统计整个塔中A的数量

5. 匹配条件：若塔中A的数量等于M，则计数加1

6. 输出结果：符合条件的基座层配置数量

   #include <iostream>
   #include <vector>
   #include <cmath>
   #include <unordered_map>
   using namespace std;int main() {int M, N;cin >> M >> N;int total = M + N;int k = 0;while (k * (k + 1) / 2 < total) k++;if (k * (k + 1) / 2 != total) {cout << 0 << endl;return 0;}int ans = 0;for (int mask = 0; mask < (1 << k); mask++) {int countA = 0;int current_mask = mask;int current_len = k;while (current_len > 0) {countA += current_len - __builtin_popcount(current_mask);if (current_len > 1) {current_mask = (current_mask ^ (current_mask >> 1)) & ((1 << (current_len - 1)) - 1);}current_len--;}if (countA == M) {ans++;}}cout << ans << endl;return 0;
   }

   代码解释

7. 输入处理：读取A和B的数量M和N

8. 计算总人数：total = M + N

9. 时间复杂度：O(2^k * k)，其中k是塔的层数

10. 空间复杂度：O(1)，仅使用常数空间

11. 优化：使用位运算高效模拟建塔过程

12. 适用性：在k较小（k ≤ 30）时高效，k较大时需优化

    • 确定塔的层数k：求解满足k(k+1)/2 = total的最小整数k

    • 枚举基座层配置：

      • 使用位掩码mask表示基座层，1表示B，0表示A

      • 遍历所有可能的基座层配置（0到2^k-1）

    • 模拟建塔过程：

      • 对于每个基座层配置，从下向上构建塔

      • 计算每层A的数量：层长 - 1的数量

      • 更新上层掩码：(current_mask ^ (current_mask >> 1)) & ( (1 << (len-1)) - 1)

    • 统计符合条件的配置：若整个塔中A的数量等于M，则有效配置计数加1

    • 输出结果：输出满足条件的配置数量