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是多余的