機(jī)器人塔

X星球的機(jī)器人表演拉拉隊(duì)有兩種服裝，A和B。
他們這次表演的是搭機(jī)器人塔。

類(lèi)似：

A B B

A B A
A A B B
B B B A B
A B A B B A

隊(duì)內(nèi)的組塔規(guī)則是：

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

你的任務(wù)是幫助拉拉隊(duì)計(jì)算一下，在給定A與B的人數(shù)時(shí)，可以組成多少種花樣的塔。

輸入一行兩個(gè)整數(shù) M 和 N，空格分開(kāi)（0<M,N<500）,分別表示A、B的人數(shù)，保證人數(shù)合理性。

要求輸出一個(gè)整數(shù)，表示可以產(chǎn)生的花樣種數(shù)。

例如：
用戶(hù)輸入：
1 2

程序應(yīng)該輸出：
3

再例如：
用戶(hù)輸入：
3 3

程序應(yīng)該輸出：
4

資源約定：
峰值內(nèi)存消耗 < 256M
CPU消耗 < 1000ms

請(qǐng)嚴(yán)格按要求輸出，不要畫(huà)蛇添足地打印類(lèi)似：“請(qǐng)您輸入…” 的多余內(nèi)容。

所有代碼放在同一個(gè)源文件中，調(diào)試通過(guò)后，拷貝提交該源碼。

注意: main函數(shù)需要返回0
注意: 只使用ANSI C/ANSI C++ 標(biāo)準(zhǔn)，不要調(diào)用依賴(lài)于編譯環(huán)境或操作系統(tǒng)的特殊函數(shù)。
注意: 所有依賴(lài)的函數(shù)必須明確地在源文件中 #include ， 不能通過(guò)工程設(shè)置而省略常用頭文件。

提交時(shí)，注意選擇所期望的編譯器類(lèi)型。

Ideas

按照組塔規(guī)則，只要最底下一層的排列確定了，那么從下往上的機(jī)器人排列就確定了。

所以我們只需要搜索最底下一層的所有排列情況，然后判斷這種情況是否可以利用所有的機(jī)器人組成相應(yīng)的塔結(jié)構(gòu)。

機(jī)器人塔每一層的數(shù)量是公差為1的等差數(shù)列，由求和公式：a1*n+[n*(n-1)*d]/2，得機(jī)器人總數(shù) num = 1 * n + [n * (n - 1)] / 2，其中n表示層數(shù)。

設(shè)A的人數(shù)為num_a，B的人數(shù)為num_b，那么 num_a + num_b = 1 * n + [n * (n - 1)] / 2，然后我們可以通過(guò)解方程得到機(jī)器人塔的層數(shù)。

接下來(lái)就是正常的DFS的套路了，搜索最下面一層所有排列情況，然后再定義一個(gè)check函數(shù)用來(lái)判斷當(dāng)前排列情況是否滿(mǎn)足要求。

Code

C++

#include <cmath> #include <cstring> #include <iostream>using namespace std;int num_a, num_b, line; char map[45][45]; long long ans;bool check() {int a = 0, b = 0;for (int i = 1; i < line + 1; i++)for (int j = 1; j < i + 1; j++)if (map[i][j] == 'A') a++;else b++;if ((a != num_a) || (b != num_b)) return false;return true; }void init() {for (int i = line; i > 1; i--)for (int j = 1; j < i; j++)if (map[i][j] == map[i][j + 1])map[i - 1][j] = 'A';else map[i - 1][j] = 'B'; }void dfs(int y) {if (y == line + 1) {init();if (check()) {ans++;}return;}map[line][y] = 'A';dfs(y + 1);map[line][y] = 'B';dfs(y + 1); }int main() {cin >> num_a >> num_b;int temp = sqrt(1 + 8 * (num_a + num_b));line = (temp - 1) / 2;dfs(1);cout << ans << endl;return 0; }

Python

from math import sqrtmaps = [[None] * 50 for _ in range(50)]def dfs(y):if y == level:a, b = 0, 0for i in range(level - 2, -1, -1):for j in range(i + 1):maps[i][j] = 'A' if maps[i + 1][j] == maps[i + 1][j + 1] else 'B'for i in range(level):for j in range(i + 1):if maps[i][j] == 'A':a += 1elif maps[i][j] == 'B':b += 1if a == num_a and b == num_b:global ansans += 1returnmaps[level - 1][y] = 'A'dfs(y + 1)maps[level - 1][y] = 'B'dfs(y + 1)if __name__ == '__main__':ans = 0num_a, num_b = map(int, input().split())level = int((sqrt(1 + 8 * (num_a + num_b)) - 1) / 2)dfs(0)print(ans)

總結(jié)

以上是生活随笔為你收集整理的2016年第七届蓝桥杯 - 国赛 - C/C++大学B组 - D. 机器人塔的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。