题解 UVA679 【小球下落 Dropping Balls】

james1BadCreeper · 2019-09-28 11:47:59 · 题解

这道题可以用来二叉树入门。

这是一棵满二叉树。不难发现对于任意编号节点k,它的左子节点编号为k\times2,右子节点编号为k\times2+1，父亲节点编号为\lfloor k\div2 \rfloor。

例如上图的节点5，左子节点编号为5\times2=10，右子节点编号为5\times2+1=11,父亲节点编号为\lfloor 5 \div 2 \rfloor=2。

这样，不难写出如下模拟程序。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAX=(1<<20)+10;
int pr[MAX],tot;
bool s[MAX];
inline int read(void)
{
    register int x=0;
    char ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x;
}
inline void print(int x)//非递归能快一些
{
    tot=0;
    while(x)
    {
        pr[++tot]=x%10;
        x/=10;
    }
    while(tot)
        putchar(pr[tot--]+'0');
    puts("");
}
int main(void)
{
    register int now,i,T=read();
    int d;
    while(T--)对于每组数据
    {
        d=read();
        i=read();
        memset(s,0,sizeof(s));//清空数组
        int n=(1<<d)-1;//n是最大节点编号
        while(i--)
        {
            now=1;
            while(now<=n)
            {
                s[now]=!s[now];//模拟变化状态
                now=(s[now]?(now<<1):(now<<1|1));//进行移动
            }
        }
        print(now>>1);
    }
    read();//小心-1碍事
    return 0;
}

由于I可以高达2^{D}-1,下落总次数可以高达2^{19}\times19=9961472，加上最多有10000组测试数据，时间复杂度高达O(Tid),必定超时。

由于每个小球必定会落在根节点（最初节点），因此前两个小球必然一个在左子树，一个右子树。所以，一般地，我们可以递归地执行此操作，只需要看小球的奇偶性，就能判断小球落在哪棵子树上。
所以，当I是奇数，它是往左走的(I+1)\div2个小球，反之是I\div2个小球（向下取整），这样，模拟最后一个小球的路线：

（这里不懂的话可以自行手玩样例，基本上就懂了）

register int now=1;
for(register int k=0;k<d-1;k++)//层数进行循环
    if(i%2==1) //奇数
        now*=2,i=(i+1)/2; //左移
    else //偶数
        now=now*2+1,i/=2; //右移
print(now);

这是部分代码，完整代码在这里~：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int MAX=(1<<20)+10;
inline int read(void)
{
    register int x=0;
    char ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x;
}
void pr(int x)
{
    if(x>9) pr(x/10);
    putchar(x%10+'0');
}
inline void print(int x)
{
    pr(x);
    puts("");
}
int main(void)
{
    register int T=read(),i;
    int d;
    while(T--)
    {
        d=read();
        i=read();
        register int now=1;
        d--;
        for(register int k=0;k<d;k++)
            i&2-1?(now<<=1,i=(i+1)>>1):(now=(now<<1)|1,i>>=1);//卡常技巧
        print(now);
    }
    read();
    return 0;
}