题目
https://atcoder.jp/contests/abc115/tasks/abc115_d
思路
本题是一题精妙的递归题. level-0, level-1, level-2 的汉堡分别如下图左, 中, 右所示:
burger.PNG
对于 level-1 汉堡而言, 其中的绿色部分即为 level-0 汉堡.
对于 level-2 汉堡而言, 其中的绿色部分即为 level-1 汉堡.
做题时, 可先把 level-n 的总层数和对应的 P 层数都列出来.
然后利用递归来解题.
比如 n = 2, x = 7. 先把最底部的 B 层去掉, 再计算下半部分的绿色部分, 共 5 层; 再计算中间层. 此时累计的层数已经达到 7 层, 所以不用计算上半部分的绿色部分和顶部的 B 层.
具体可参考下面的代码, 如果一时无法理解, 可以将 n = 2, x =1; n = 2, x = 2; n = 2, x = 3; ...; n = 2, x = 13 逐一代入代码中去分析.
AC 代码
- #include<bits/stdc++.h>
- using namespace std;
- long long burger[52], patty[52];
- long long n, x;
- long long ans = 0;
- void f(int n)
- {
- if(x == burger[n]) // 递归终止条件
- {
- // 测试数据 n=2,x=3 会进入本分支
- ans += patty[n];
- return;
- }
- else if(x <burger[n])
- {
- if(x) // x>0
- {
- x--; // 最底下那一层是 bun 不是 patty, 减掉
- if(x> burger[n-1])
- {
- ans += patty[n-1];
- x -= burger[n-1];
- // 加上中间那一层的 patty
- ans++;
- x--;
- // x> burger[n-1] 分为两种情况:
- // 一是 x>burger[n-1]+1, 这里 1 指的是中间的 patty 层, 这种情况进下面的 if
- // 二是 x==burger[n-1]+1, 这种情况进下面的 else
- if(x)
- {
- f(n-1);
- }
- else // x==0 是递归终止条件, 可以省略不写
- {
- // 测试数据 n=2,x=4 会进入本分支
- return;
- }
- }
- else // x<=burger[n-1]
- {
- f(n-1);
- }
- }
- else // x==0 是递归终止条件, 可以省略不写
- {
- // 测试数据 n=2,x=1 或 n=2,x=2 会进入本分支
- return;
- }
- }
- }
- int main()
- {
- scanf("%lld%lld",&n, &x);
- burger[0] = 1, patty[0] = 1; // 初始化 n = 0 时
- for(int i = 1; i <= 50; i++)
- {
- // 计算 1 层~ 50 层的汉堡总层数和对应的 patty 层数
- burger[i] = burger[i-1] * 2 + 3; // 汉堡的总层数
- patty[i] = patty[i-1] * 2 + 1; // patty 层数
- //cout << "n=" << i << ", 汉堡总层数和 patty 层数:" << burger[i] << ',' << patty[i] << '\n';
- }
- f(n);
- printf("%lld\n", ans);
- return 0;
- }
来源: http://www.jianshu.com/p/6d858cb29ac1