[蓝桥杯]机器人塔
题目描述
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的肩上
解决思路
算法特点
-
确定塔的层数：根据总人数M+N，求解满足k(k+1)/2 = M+N的整数k
-
枚举基座层：基座层有k个机器人，每个机器人可以是A或B，共2^k种可能
-
模拟建塔过程：
-
从基座层开始向上构建
-
每层机器人由下一层的两个相邻机器人决定：若两个机器人相同，则上层为A；若不同，则上层为B
-
-
统计A的数量：在构建过程中统计整个塔中A的数量
-
匹配条件：若塔中A的数量等于M，则计数加1
-
输出结果：符合条件的基座层配置数量
#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; }代码解释
-
输入处理：读取A和B的数量M和N
-
计算总人数：total = M + N
-
时间复杂度：O(2^k * k)，其中k是塔的层数
-
空间复杂度：O(1)，仅使用常数空间
-
优化：使用位运算高效模拟建塔过程
-
适用性：在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
-
输出结果：输出满足条件的配置数量
-