解题思路，别抄

学生版： 老师版：

题目描述中： 等级为 L 的汉堡（L≥0）按如下方式定义： 等级 0 汉堡：只有 一层肉饼（记作 P）。 等级 L 汉堡（L≥1）：自下而上依次为：面包 B、等级 L−1 汉堡、肉饼 P、等级 L−1 汉堡、面包 B。 据此描述： 等级0汉堡：P 等级1汉堡：BPPPB，前1层0个肉饼（测试样例2） 等级2汉堡：BBPPPBPBPPPB，前7层4个肉饼（测试样例1） 这样就理顺了。 样例解释中提示：等级 50 汉堡的层数已经大到无法用 32 位整数表示。 显然依靠存储等级N的汉堡样式再进行输出是一定会超出存储范围的。因此不能存储实际样式，只能使用数据关系推断。 等级 n （n≥1）汉堡：面包 B、等级 n−1 汉堡、肉饼 P、等级 n−1 汉堡、面包 B。 查找前x层的肉饼(字符P)数量。 如果x的数值小于等于等级n汉堡层数的一半，则可将问题转化为：等级 n−1 汉堡的前x-1层中肉饼的数量；否则，问题可转化为：等级 n−1 汉堡中肉饼的数量+等级n-1汉堡中前 x-2-(等级 n−1 汉堡的层数)。 显然需要先计算每个等级汉堡的层数。 代码如下： 通过率：70%，没通过的原因是因为超时。分析：递归调用中存在重复计算，会导致超时，但X最大超过int范围，显然也无法用二维数组存储某个等级汉堡下前X层中肉饼数量。突然悟了，虽然无法存储所有情况，但存储某个等级汉堡中总肉饼数量还是可以实现的，应该也可以有效降低重复计算次数。 更新迭代代码如下：

#include<bits/stdc++.h> using namespace std; typedef long long ll; ll sizeB[60], patty[60]; ll f(int N, ll x){ if(x0) return 0; if(N0) return 1; // 等级0只有P if(x==1) return 0; // 最底层B if(x <= 1 + sizeB[N-1]) return f(N-1, x-1); if(x == 2 + sizeB[N-1]) return patty[N-1] + 1; return patty[N-1] + 1 + f(N-1, x - sizeB[N-1] - 2); } int main(){ int N; ll x; cin >> N >> x; sizeB[0]=1; patty[0]=1; for(int i=1;i<=N;i++){ sizeB[i] = 2sizeB[i-1] + 3; patty[i] = 2patty[i-1] + 1; } cout << f(N, x) << "\n"; return 0; }