UVa 679 Dropping Balls

题目描述给定一棵完全二叉树FBT\texttt{FBT}FBT深度为DDD2≤D≤202 \le D \le 202≤D≤20节点按层序编号从111开始。每个非叶子节点有一个标志位初始为false。第III个小球从根节点落下经过每个节点时若标志为false则将其改为true并走向左子树若为true则将其改为false并走向右子树。求第III个小球最终停在哪一个叶子节点。输入格式第一行为测试用例数lll。接下来lll行每行两个整数DDD和III。输入以单独一行-1结束。输出格式对于每个测试用例输出一行即小球最终所在的叶子节点编号。样例输入5 4 2 3 4 10 1 2 2 8 128 -1输出12 7 512 3 255题目分析本题可以直接模拟每个小球的掉落过程但由于III最大可达524288524288524288深度D≤20D \le 20D≤20直接模拟每个小球O(D)O(D)O(D)步总复杂度O(I⋅D)O(I \cdot D)O(I⋅D)约为10710^7107尚可接受。但更高效的方法是观察规律对于第III个小球在每个节点处根据III的奇偶性决定走向。具体地当小球到达某个节点时它是该节点处第kkk个经过的小球按全局顺序。若kkk为奇数则走向左子树且下一个走向该节点左子树的小球序号为⌈k/2⌉\lceil k/2 \rceil⌈k/2⌉若kkk为偶数则走向右子树且下一个走向右子树的小球序号为k/2k/2k/2。因此我们可以从根节点开始不断更新III直到到达叶子深度。解题思路对每个测试用例令pos 1depth 1。当depth D时若I为奇数则走向左子树pos pos * 2I (I 1) / 2。若I为偶数则走向右子树pos pos * 2 1I I / 2。depth。输出pos。该解法无需模拟每个小球直接根据奇偶性计算最终位置时间复杂度O(D)O(D)O(D)。复杂度分析每个测试用例O(D)≤20O(D) \le 20O(D)≤20lll未知但通常较小非常快。代码实现// Dropping Balls// UVa ID: 679// Verdict: Accepted// Submission Date: 2016-08-25// UVa Run Time: 0.090s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases,D,I;cincases;for(intc1;ccases;c){cinDI;intpos1;for(intdepth1;depthD;depth){if(I%21){pospos*2;I(I1)/2;}else{pospos*21;II/2;}}coutpos\n;}return0;}总结本题通过分析小球在二叉树中的行为规律利用奇偶性直接计算最终位置避免了模拟的大量开销。关键点在于理解每个节点处的小球序号与其走向的关系。该解法是典型的数学规律题适合作为递归和规律发现的练习。