硬币塔
时间限制：1秒
空间限制：65535 KB
题目描述
看不懂题目的可以直接点这里
一个k级的硬币塔从下到上，由1个银币，一个k-1级硬币塔，k个金币，一个k-1级硬币塔，1个银币堆成。0级硬币塔只有一个金币。问n级硬币塔从下向上数i个有几个金币。
输入描述
一行用空格隔开的两个整数n,i
输出描述
一个整数表示答案
样例一
输入
5 13
输出
6
题目分析
不得不吐槽一句 ，这题题目描述得挺难看懂的。
下面是鄙人通俗的解释：
题目描述
硬币塔： 由包含金币和银币的一摞硬币组成。
如下图所示，金色方块表示金币，灰色方块表示银币。
0阶硬币塔的组成方式为：只有一个金币
高阶硬币塔： 由低阶硬币塔和数个硬币组成。
k阶硬币塔的组成方式为：从下到上，1个银币，1个k-1阶硬币塔，k个金币，1个k-1阶硬币塔，1个银币堆成。（ k ≥ 1 k\geq1 k≥1）
输入描述
输入为一行空格隔开的两个正整数 k k k 和 n n n
其中 k k k 代表这组样例是一个 k k k 阶硬币塔
数据范围：
-
0 ≤ k ≤ 40 0\leq k\leq 40 0≤k≤40
-
0 ≤ n ≤ 2147483647 0\leq n\leq 2147483647 0≤n≤2147483647 （ 2147483647 = 2 31 ? 1 2147483647 = 2^{31-1} 2147483647=231?1）
输出描述
输出一行一个正整数，代表这个 k k k 阶硬币塔从下往上数 n n n 个硬币，其中金币有多少个。
样例一
样例输入
2 4
样例输出
2
样例解释
如图所示是一个2阶硬币塔，其最下面的4个硬币中共有2个是金币，因此输出答案2。
题目分析
这题硬币塔高度的增长速度是指数级的
如果用 h e i g h t [ i ] height[i] height[i] 代表 i i i 阶硬币塔的高度，那么很容易有：
h e i g h t [ i ] = 1 + h e i g h t [ i ? 1 ] + i + h e i g h t [ i ? 1 ] + 1 height[i] = 1 + height[i - 1] + i + height[i - 1] + 1 height[i]=1+height[i?1]+i+height[i?1]+1
也就是说 h e i g h t [ i ] > 2 ? h e i g h t [ i ? 1 ] height[i] > 2 * height[i - 1] height[i]>2?height[i?1]
因此我们可以用递归来求解，同时记忆化一下。
定义函数getAB(long long a, long long b)代表a阶硬币塔的下面b个硬币中有多少个金币。
所谓记忆化就是用C++的map等方式把计算过的结果记录下来，避免重复求解。
map<pair<ll, ll>, ll> ma;
ll getAB(ll a, ll b) { // a层塔的下b层有多少个金币
if (ma.count({a, b})) // 如果已经计算过就直接返回
return ma[{a, b}];
... // 没计算过就开始计算，计算结果为ans
return ma[{a, originalB}] = ans; // 返回之前记录下来
}
getAB的设计思路是：在
b
b
b大于0时，不断从下往上递归求解。（一个银币中有0个金币，一个a-1阶硬币塔中有多少个金币，a个金币中有a个金币，…）
ll getAB(ll a, ll b) {
... // 如果出现过就直接返回
b--; // 最下面的银币
if (b > 0) { // 如果还要往上数，那么接下来就是一个a-1阶硬币塔
ll removeHeight = min(height[a - 1], b); // 这次数的个数为：{a-1阶硬币塔的高度, 剩余要数的硬币的个数}的最小值
b -= removeHeight;
ans += getAB(a - 1, removeHeight);
}
if (b > 0) {
ll removeHeight = min(a, b); // 中间有a个金币
b -= removeHeight;
ans += removeHeight;
}
if (b > 0) { // 又是一个a-1阶硬币塔
ll removeHeight = min(height[a - 1], b);
b -= removeHeight;
ans += getAB(a - 1, removeHeight);
}
b--; // 最上面一个银币
... // 返回结果ans并记录下来
}
终止条件为 a = 0 a=0 a=0，也就是计算到了0阶硬币塔。
AC代码
#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;
typedef pair<ll, ll> pii;
#define SIZE 40
map<pii, ll> ma;
ll height[SIZE + 1] = {1};
ll getAB(ll a, ll b) { // a层塔的下b层有多少个金币
ll originalB = b;
if (ma.count({a, b}))
return ma[{a, b}];
if (a == 0) {
return ma[{a, b}] = 1;
}
ll ans = 0;
b--; // 最下面的银币
if (b > 0) {
ll removeHeight = min(height[a - 1], b);
b -= removeHeight;
ans += getAB(a - 1, removeHeight);
}
if (b > 0) {
ll removeHeight = min(a, b); // 中间有a个金币
b -= removeHeight;
ans += removeHeight;
}
if (b > 0) {
ll removeHeight = min(height[a - 1], b);
b -= removeHeight;
ans += getAB(a - 1, removeHeight);
}
b--;
return ma[{a, originalB}] = ans;
}
int main(int argc, char** argv) {
for (ll i = 1; i <= SIZE; i++) {
height[i] = 1 + height[i - 1] + i + height[i - 1] + 1;
}
ll a, b;
cin >> a >> b;
if (!b) {
puts("0");
return 0;
}
ll ans = getAB(a, b);
printf("%lld\n", ans);
return 0;
}
原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/124420882
