題目描述
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
-
輸出結果：輸出滿足條件的配置數量
-
