UVa679 完全二叉树编号

这题我也是用了两种方法，第一种比较常规，但超时，第二种比较讨巧

暴力求解（超时）

运用完全二叉树的性质，对于结点k，左子结点编号2k，右子结点编号2k+1，用一个数组表示当前每个结点状态，然后模拟每个小球的下落过程

代码实现

#include <iostream>

using namespace std;
const int maxDeep = 20;

int main()
{
    int n,D,I;
    while (cin >> n)
    {
        if (n == -1)
            break;
        for (int i = 0; i < n; i++)
        {
            int *tree = new int[1 << 20](); //1左移二十位，即2的20次方
            int pos;
            cin >> D >> I;
            for (int j = 1; j <= I; j++) //模拟每个小球下落过程
            {
                //二叉树左子节点的编号为2K，右子节点编号为2K+1
                pos = 1;//小球初始位置
                for (int k = 1; k < D; k++) //分层
                {
                    if (tree[pos] == 0)
                    {
                        tree[pos] = 1;
                        pos = 2 * pos;//下一层的左节点
                        //cout << pos << " ";
                    }
                    else
                    {
                        tree[pos] = 0;
                        pos = 2 * pos+1;
                        //cout << pos << " ";
                    }
                }
                //cout << endl;
            }
            cout << pos << endl;
        }
    }
    system("pause");
    return 0;
}

只模拟最后一次小球下落求解

因为一个结点的状态只有两种，所以可以由根节点开始计算最后一次小球I所走的路径，如果I%2=0，则最后一个球是第I/2个走到右子树的小球，令I=I/2；如果I为奇数，则最后一个球是第（I+1）/2$（I+1）/2$个走到左子树的小球，令I=(I+1)/2$I=(I+1)/2$

代码实现

#include<iostream>

using namespace std;

int main()
{
    int n, D, I;
    while (cin >> n)
    {
        if (n == -1)
            break;
        for (int i = 0; i < n; i++)
        {
            int pos=1;
            cin >> D >> I;
            for (int j = 1; j < D; j++) //模拟最后一个小球下落过程
            {
                if (I % 2 != 0)
                {
                    pos = 2 * pos;
                    I = (I + 1) / 2;
                }
                else
                {
                    pos = 2*pos + 1;
                    I = I / 2;
                }
            }
            cout << pos << endl;
        }
    }
    system("pause");
    return 0;
}