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

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

12

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;
}

  

上一篇:iOS开发-捕获程序崩溃日志


下一篇:WebForm 页面传值