uva 679 Dropping Ball

BabbleDay posted @ 2013年4月14日 02:37 in 等养肥了再分 , 1487 阅读

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

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

#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;
}

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

Avatar_small
Lock your Facebook P 说:
2022年12月21日 03:32

Facebook has introduced a new safety feature called profile lock. Users can use this feature to restrict access to their profile to those who are not on their friend list. Other persons who are not on the user’s friends list will be unable to view the profile once it has been locked. Lock your Facebook Profile This simple guide helps you to lock your FB Profile easily with simple methods on any device such as a PC, Android, or iPhone.

Avatar_small
Tj Maxx Credit Card 说:
2023年1月20日 00:10

TJ Maxx also well known as TJMaxx or TJX, is a superstore chain in the United State of America that is famous for selling products at lower prices compared to other superstore chains in the market. Tj Maxx Credit Card Payment In order to increase their customer intent they have launched a special credit card called TJMaxx credit card. This may be used in any of their stores. Upon using these cards customers will earn loyalty and bonus points. These loyalty and bonus points are used in order to redeem through special offers.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter