Christmas

蔚落 2023-07-13 03:20 22阅读 0赞

> 题目描述  
> In some other world, today is Christmas.  
> Mr. Takaha decides to make a multi-dimensional burger in his party. A level-L burger (L is an integer greater than or equal to 0) is the following thing:  
> ·A level-0 burger is a patty.  
> ·A level-L burger (L≥1) is a bun, a level-(L−1) burger, a patty, another level-(L−1) burger and another bun, stacked vertically in this order from the bottom.  
> For example, a level-1 burger and a level-2 burger look like BPPPB and BBPPPBPBPPPBB (rotated 90 degrees), where B and P stands for a bun and a patty.  
> The burger Mr. Takaha will make is a level-N burger. Lunlun the Dachshund will eat X layers from the bottom of this burger (a layer is a patty or a bun). How many patties will she eat?
> 
> Constraints 1≤N≤50 1≤X≤( the total number of layers in a level-N  
> burger ) N and X are integers. 输入 Input is given from Standard Input  
> in the following format:
> 
> N X
> 
> 输出 Print the number of patties in the bottom-most X layers from the  
> bottom of a level-N burger.
> 
> 样例输入 Copy 2 7 样例输出 Copy 4

很明显是一道典型的递归题：

可以发现burger是对称的。那么就可以分段递归。  
len是每个burger的长度（高度），p记录的是每个burger含有的p的个数。  
两个公式稍微推一下就可以得到，是一个等比数列的问题。（事实上直接迭代也可以得到）  
上代码：

#include <cstdio>
    #include <cmath>
    #include <iostream>
    
    using namespace std;
    
    typedef unsigned long long ll;
    
    ll p[55], len[55];
    
    ll solve(ll n, ll x)
    {
        
        if(x <= n)
            return 0;
        if(x >= len[n]-1)
            return p[n];
        if(x == len[n]/2+1)
            return (p[n]/2+1);
        else if(x < len[n]/2+1)
            return solve(n-1,x-1);
        else
            return p[n]/2+1 + solve(n-1, x-len[n]/2-1);
    }
    
    int main()
    {
        
        for(int i = 0; i <= 50; ++i)
        {
        
            p[i] = pow(2, i+1)-1;
            len[i] = pow(2, i-1)*8-3;
        }
        ll n,x;
        cin>>n>>x;
        cout<<solve(n,x)<<endl;
        return 0;
    }

![这里参考大佬写的递归][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDk3NDIz_size_16_color_FFFFFF_t_70]  
谢谢！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDk3NDIz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200309211441688.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDk3NDIz,size_16,color_FFFFFF,t_70