Dropping Balls（UVA 679）

本文主要是介绍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是多余的

这篇关于Dropping Balls（UVA 679）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---