首页 > ACM题库 > HDU-杭电 > hdu 2568 前进-递归和分治-[解题报告]C++
2014
02-10

hdu 2568 前进-递归和分治-[解题报告]C++

前进

问题描述 :

轻松通过墓碑,进入古墓后,才发现里面别有洞天。
突然,Yifenfei发现自己周围是黑压压的一群蝙蝠,个个扇动翅膀正准备一起向他发起进攻!
形势十分危急!
好在此时的yifenfei已经不是以前那个经常被lemon抢走MM的菜鸟了!面对众多蝙蝠的嗜血狂攻,只见yifenfei使出轻灵的剑法,刷,刷,刷,瞬间搞定……
现已知yifenfei使用了2招(剑招A和剑招B):剑招A,一招能杀死一半的蝙蝠。但是如果当前的蝙蝠数为奇数,那么就必须先出一招剑招B杀死其中任意一个,使蝙蝠数为偶数,再出剑招A。
现在请问:杀死n只蝙蝠需要使出多少招剑招B?

输入:

输入数据首先给出一个整数C,表示测试组数。
然后是C组数据,每组包含一个正整数n (n<2^31)。

输出:

输入数据首先给出一个整数C,表示测试组数。
然后是C组数据,每组包含一个正整数n (n<2^31)。

样例输入:

2
1
5

样例输出:

1
2

#include <iostream>
long degui(long m);
using namespace std;

int main()
{
    int n,i;
    long sum,a;
    cin>>n;
    for(i=1;i<n+1;i++)
    {
        cin>>a;
        sum=degui(a);
        cout<<sum<<endl;

    }


    return 0;
}

long degui(long m)  //简单的递归
{
    if(m==1 || m==2)
    {
        return 1;
    }
    else
    {
        if(m%2==0)
        {
            return degui(m/2);
        }
        else
        {
            return (degui(m/2)+1);
        }
    }
}

解题转自:http://blog.csdn.net/breakback/article/details/7360068


  1. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测

  2. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!

  3. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }