【题解-信息学奥赛一本通】1363：小球(drop)

题目1363小球(drop)题目描述许多的小球一个一个的从一棵满二叉树上掉下来组成FBTFull Binary Tree满二叉树每一时间一个正在下降的球第一个访问的是非叶子节点。然后继续下降时或者走右子树或者走左子树直到访问到叶子节点。决定球运动方向的是每个节点的布尔值。最初所有的节点都是false当访问到一个节点时如果这个节点是false则这个球把它变成true然后从左子树走继续它的旅程。如果节点是true则球也会改变它为false而接下来从右子树走。满二叉树的标记方法如下图:因为所有的节点最初为false所以第一个球将会访问节点1节点2和节点4转变节点的布尔值后在在节点8停止。第二个球将会访问节点1、3、6,在节点12停止。明显地第三个球在它停止之前会访问节点1、2、5在节点10停止。现在你的任务是给定FBT的深度D和I表示第I个小球下落你可以假定I不超过给定的FBT的叶子数写一个程序求小球停止时的叶子序号。输入一行包含两个用空格隔开的整数D和I。其中2≤D≤201≤I≤524288。输出对应输出第I个小球下落停止时的叶子序号。时空限制1s / 64MB样例输入4 2样例输出12代码1模拟#includebits/stdc.husingnamespacestd;constintN203;intD,I,st[1N],k,path[N],idx;intmain(){cinDI;for(inti0;iI;i){k1;idx0;for(intj2;jD;j){intt2*kst[k];st[k]!st[k];kt;path[idx]k;}}coutpath[idx];return0;}代码2数学根节点上的第I个经过的如果I是奇数那么就是往左走如果I是偶数那么就是往右走。当I是奇数的时候它是往左走的第I1/2个小球。当I是偶数的时候它是往右走的第I/2个小球。#includebits/stdc.husingnamespacestd;constintN203;intD,I,k,path[N],idx;intmain(){cinDI;k1;idx0;for(intj2;jD;j){if(I%2){kk*2;I(I1)/2;}else{kk*21;II/2;}path[idx]k;}coutpath[idx];return0;}代码3DFS#includebits/stdc.husingnamespacestd;constintN203;intD,I,k,path[N],idx,st[1N];voiddfs(intk,intd){if(dD){if(idxI)coutk;return;}dfs(2*kst[k],d1);st[k]!st[k];}intmain(){cinDI;for(inti1;iI;i){idxi;dfs(1,1);}return0;}结果参考https://blog.csdn.net/weixin_44493173/article/details/109167633