2016國賽
題目描述
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,N（0<M,N≤50）,分别表示 A、B 的人數，保證人數合理性。輸出描述
要求輸出一個整數，表示可以産生的花樣種數。輸入輸出樣例
輸入輸出1 23
題目大意
給出A,B兩類機器人，讓它們按—定規則堆成三角形塔，問可堆成的方案數
規則:
A隻能放在AA，BB上B隻能放在AB，BA上
思考：如何确定每一個方案
- 問題轉換成：确定第一層（最下一層）的A，B分布情況即可
因為第一行确定了，第二次也随之确定（根據組塔規則），以此類推，所有的機器人的位置都是确定的。
機器人的層數由機器人數量決定，
，n最大可取到13，是以最多13層。一個位置可以放A和B兩種，是以第一層最多能放
種，這個計算量不高。
A，B兩個狀态的表示
二進制法:
用0表示A，用1表示B
從最後一層向上遞推的過程:
遞推的結果符合異或運算的性質
解題思路:二進制枚舉+異或運算遞推
1、根據輸入的A，B機器人數推算層數n：
2、二進制法求底層AB的所有情況
3、對于每個底層，利用異或運算（^）不斷向上遞推，遞推過程中根據二進制數0，1統計A,B機器人剩餘未使用的個數
4、如果A,B剩餘未使用的個數出現負數，或者到達最頂層時A、B機器人個數不全為0，那麼這個方案無效
5、統計所有有效的方案數，即為結果
代碼：
d = {} # 存機器人數和層數
base = 0
for i in range(1, 20):
base += i # 機器人數
d[base] = i
M, N = map(int, input().split())
level = d[M + N] # 根據機器人數算出有多少層
def dfs(cur, clv, m, n): # cur:目前情況，clv：目前層數（最底層的機器人個數），m：剩餘A的人數，n：剩餘B的人數
if m < 0 or n < 0: # 排除出現負數的情況
return False
if clv == 0: # 層數為0
return m == n == 0
cb = bin(cur)[2:].count('1') # 轉為二進制：0bxxxx（字元串），統計1的個數count('1')
ca = clv - cb # 不直接統計0的個數，因為例如001010最前面的兩個0沒辦法計入
m -= ca; n -= cb
up = (cur ^ (cur >> 1)) & ((1 << (clv - 1)) - 1) # 計算出上一層的情況
return dfs(up, clv - 1, m, n) # 搜尋上一層（層數-1）
res = 0
for case in range(1 << level): # 周遊2^n種情況
if dfs(case, level, M, N):
res += 1
print(res)
注：下面對代碼up = (cur ^ (cur >> 1)) & ((1 << (clv - 1)) - 1) 進行解釋
例如：cur為22（二進制位10110），clv為6
1、cur >> 1：将cur右移一位，右移一位為1011；
1 << (clv - 1）：1向左移動clv-1位，為01111
2、 (cur ^ (cur >> 1))：求上一層的情況，但最左邊多出來一位
3、& ((1 << (clv - 1)) - 1)：和一個二進制位為01111相與（&）就能去掉最左邊的一位。注意“-”的優先級大于“>>”，是以需要加一個括号讓<<先算。