华东交通大学2016年ACM“双基”程序设计竞赛 1003

2023-07-26 23:51:28

Problem Description

风雨漂泊异乡路，

浮萍凄清落叶飞。

游子寻根满愁绪，
一朝故土热泪归。
Hey ecjtuer！刚刚学习了二叉树的知识，现在来考察一下..
给你一个深度为h的满二叉树，根节点为1（根的深度为0）,根据先序遍历对节点进行编号，如下图是对一个深度为2的满二叉树的节点进行编号。
现在希望你告诉我以第n个叶子节点（从左往右数）为起点，终点为根节点，形成的一条链经过的节点的序号之和。
1
/ \
2 5
/ \ / \
3 4 6 7

Input

输入两个数 h 代表二叉树的深度 n代表查询的叶子节点
1<=h<=50
1<=n<=2^h
注意多组数据

Output

输出所求链的序号之和模1e9+7的余数

Sample Input

2 3

Sample Output

Author

zhengjinke2123

解法：找规律，嗯，找规律，能知道的是左边是加1，右边是加左边的，然后加1

#include<stdio.h>

//#include<bits/stdc++.h>

#include<string.h>

#include<iostream>

#include<math.h>

#include<sstream>

#include<set>

#include<queue>

#include<map>

#include<vector>

#include<algorithm>

#include<limits.h>

#define inf 0x3fffffff

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

using namespace std;

int mod=1e9+7;

LL n,m;

LL ans=1;

LL num=1;

int main()

{

    while(cin>>n>>m)

    {

        LL e=1;

        ans=1;

        num=1;

        while(n--)

        {

            LL pos=(e<<n);

            if(m<=pos)

            {

                num++;

             //   cout<<"A"<<endl;

            }

            else

            {

                num+=2*pos;

                m-=pos;

                //cout<<"B"<<endl;

            }

           // cout<<x<<endl;

            ans+=num;

            ans%=mod;

        }

        cout<<ans%mod<<endl;

    }

    return 0;

}

码农公寓