游客 注册 | 登录
中文 | En

2022 - 公交路线

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

喵星人的世界是我们这些低智商生物无法理解的，比如他们的公交车站点连接起来刚好构成一棵完全二叉树（如图，它的高度h为2,它的第i层有2^i个节点），我们知道，公交路线是不走回头路的，也就是说不会经过同一个站点两次，（起点和终点在同一地点也算一条路线），现在，他们想让每个站点都有公交车经过，问最少需要安排多少辆公交车？

     

<span style="font-family:宋体;font-size:16pt;">h=2</span> 


<span style="font-size:16.0000pt;font-family:'宋体';"></span> 


<span style="font-size:12.0000pt;font-family:'宋体';"></span>

题目输入

输入一个T，表示测试样例数

  对于每组测试数据，输入一个h，表示树的高度(0=<h<=60)

题目输出

对于每组测试数据输出一行，需要多少辆车？

输入/输出样例

输入格式

5
0
1
2
3
4

输出格式

1
1
3
5
11

C++解答

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>

using namespace std;
long long a[100];
void dabiao()
{
    a[0]=1;
    a[1]=1;
    for(int i=2;i<=60;i++)
    {
        a[i]=a[i-1]+a[i-2]*2;
    }


}
int main()
{
    int t;
    cin>>t;
    int n;
    dabiao();
    while(t--)
    {
        cin>>n;
        cout<<a[n]<<endl;
    }


    return 0;
}

Java解答

import java.math.BigInteger;
import java.util.*;

import static java.util.Arrays.sort;

public class Main{
    public static boolean ok(int n){
        while(n!=0){
            if(n%10==4 || n%10==7)
                n/=10;
            else
                return false;
        }
        return true;
    }
    public static void main(String args[]){
        Scanner cin=new Scanner(System.in);
        BigInteger f[]=new BigInteger[61];
        f[0]=BigInteger.valueOf(1);
        f[1]=BigInteger.ONE;
        int t=cin.nextInt();
        while(t-->0){
        for(int i=2;i<61;i++){
            f[i]=f[i-1].add(f[i-2].add(f[i-2]));
        }
        while(cin.hasNext()){
            System.out.println(f[cin.nextInt()]);
        }
        }
    }
}
请先登陆