• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

题目描述

nxjln2a424e5253.png

输入格式

hjhpbrltq0z5254.png

输出格式

lyenbt3cei55255.png

题意翻译

许多小球从一棵满二叉树中一个接一个地落下,形成一棵新的满二叉树。每次都是落球第一个访问非叶节点。然后继续往下走,要么去右边的子树,要么去左边的子树,直到到达叶子节点。

决定球运动方向的是每个节点的布尔值。最初,所有节点都是假的。当一个节点被访问时,如果它是假的,球就把它变成真的,然后从左边的子树继续它的旅程。如果节点是真的,球也会把它改成假的,然后从右边的子树走。全二叉树的标记方法如下。

因为所有节点最初都是假的,所以第一个球将访问节点1、节点2和节点4,并在改变节点的布尔值后停在节点8。第二个球将访问节点1、3和6,并停在节点12。显然,在它停止之前,第三个球将访问节点1、2和5,并在节点10停止。

现在你的任务是,给定新的满二叉树的深度D和落球的个数I,你可以假设I不超过给定的新的满二叉树的叶子个数,写一个程序求球停时的叶子个数P。

e5q3dq3dmks5256.png

输入输出样例

输入#1输出#2

5 12

4 2 7

3 4 512

10 1 3

2 2 255

8 128

-1

分析

从图中可以看出,除了1,其余奇数都是右子树节点,偶数都是左子树节点。

也就是说,如果这是一个奇数点,那么这个节点是假的。接下来转到左子树,编号为A的球会变成a*2。

如果这是一个偶点,那么这个节点为真。接下来转到右边的子树,编号为A的球会变成A * 2 ^ 1。

代码

#包括iostream

使用命名空间std

int main()

{

int n,d,I,j,a,b;

cinn//输入总共有多少组数据。

for(j=0;jn;J )//每组数据

{

辛蒂;//输入深度D和球号I。

a=1;b=1;//每次球落下的时候,记得初始化。a记录球的数量,B记录球的深度。

而(bd)//球的深度没有达到深度D,也就是没有走到最后。

{

如果(i%2!=0)a *=2;//i是奇数点,false,去左子树,球A变成a*2。

else a=a * 2 ^ 1;//i是一个偶点,真,去右边的子树,球A变成了A * 2 ^ 1。

b;//每次行走,深度为1

I=(I 1)/2;

}

coutaendl//当A最终停止时输出叶数

}

int m;cinm//在末尾输入-1表示结束

返回0;

}

(参考洛古的解决方案)

Link to comment
Share on other sites