BabbleDay's Blog

很多年前就在某处见过它了，可是当时还不知道它的名字，没想到这么多年后又重逢～

这是它的网址http://prezi.com/index/，mark一下～～开心ing～～

然后至于操作就超级简单了～直接用模板就可以做的超级炫啦～～～啦啦啦～～～

有人推荐了 刘海洋的《LaTeX入门》，可以入手一本看看～

另外巧遇一个pdf，简单明了很喜欢，mark一下：点击链接可以直接下载哦～

顺便再吐槽一下Arch的texlive从2012更到2013的时候崩了，这里有个.pacnew的bug，不过最简单的办法就是先卸了2012再装2013就没事啦哈哈～～

两句话：不要轻易使用模拟编程，算下时间复杂度。“一左一右”之类的联想二进制，学会利用二进制的移位操作。。。

这是模拟过程的代码，可惜超时了

#include <iostream>
#include <cmath>

using namespace std;

void the_case()
{
    int depth, num;
    cin >> depth;
    num = pow(2, depth);
    bool node[num];
    for (int i=0; i<num; i++) node[i] = false;

    int n, r;
    cin >> n;
   for(int k=1; k<=n; k++) 
    {
        int j=1;
        for (int i=1; i<depth; i++)
        {
            if (node[j]==false)
            {
                node[j]=true;
                j = j * 2;
            }
            else 
            {
                node[j]=false;
                j = j*2 +1;
            }
        }
        r = j;
    }
    cout << r << endl;
}

int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        the_case();
    }
    cin.clear();
    return 0;
}

后来很郁闷的从前辈那边学到了算法：观察第i个球与最后位置p的数学关系发现“p的二进制做镜像后和2×i+1的二进制一样”

补充下思考细节，因为对于叶子节点的二进制来说，最高位每两次一循环（01），次高位每4次一循环（0011），次次高位每8位一循环（00001111），就会发现和二进制计数递增数列成镜像

#include <iostream>

using namespace std;

void the_case()
{
    int depth, no;
    unsigned int m; //注意使用unsigned在这种移位操作中
    cin >> depth >> no;
    unsigned int t=0; //同上
    m = no*2-1; //第no个变成2×no+1
    while(depth--) //数的深度等于二进制位数
    {
        t <<= 1; //将t已有位数左移保留
        t += m&1; //这里是提取出m的最低位
        m >>= 1; //将m已经镜像的位数移去
    }
    cout << t << endl;
}

int main()
{
    int c;
    cin >> c;
    while(c--)
        the_case();
    return 0;
}

向前辈表示敬意和感谢，对自己继续勉励！！