Dropping Balls（UVA 679）

网址如下：

Dropping Balls - UVA 679 - Virtual Judge (vjudge.net)

（第三方网站）

二叉树

别说了，我只会模拟，最后用时530ms

结果算法书给出了一个优化的解法：

因为小球要么往左，要么往右，根据到这个点有几个小球可以推断出当前点的状态，根据要求的第几个小球可以推断在这个点有多少个球往左走了，多少个球往右走了

这样可以根据 I 直接推断出第 I 个的动向，配合D直接算出答案

用时20ms

代码如下：

#include<cstdio>

int main(void)
{
    int l; scanf("%d", &l);
    for(int i = 0; i < l; i++)
    {
        int D, I; scanf("%d%d", &D, &I);
        int k = 1, d = 1;
        while(d++ < D)
        {
            if(I % 2) k = k * 2;
            else k = k * 2 + 1;
            I = (I + 1) / 2;
        }
        printf("%d\n", k);
    }
    
    return 0;
}

模拟的代码如下：

#include<cstdio>
struct Ball{
    int D, I;
}b[100000];
const int maxn = 1048576;
bool tree[maxn];
int ans[21][524289], maxD, maxI, l;

int main(void)
{
    scanf("%d", &l);
    for(int i = 0; i < l; i++)
    {
        scanf("%d%d", &b[i].D, &b[i].I);
        maxD = (maxD > b[i].D) ? maxD : b[i].D; maxI = (maxI > b[i].I) ? maxI : b[i].I;
    }
    for(int i = 1; i <= maxI; i++)
    {
        //更新树
        int D = 1, j = 1;
        while(D <= maxD)
        {
            tree[j] = !tree[j];
            ans[D++][i] = j;
            if(tree[j]) j = j * 2;
            else j = j * 2 + 1;
        }
    }
    for(int i = 0; i < l; i++)
        printf("%d\n", ans[b[i].D][b[i].I]);
    getchar();
    
    return 0;
}

后面的getchar是多余的