首页 > 代码库 > HDU 5573 题解

HDU 5573 题解

题意:关于一只要续命的青蛙(),一颗完全二叉树,它的标号正如我们所期望的根为1,左儿子为父节点*2,右儿子为父节点*2+1,然后老青蛙从根往下走,一共走K步,它需要n个灵魂,每走过一个点,可以减去或加上这个点的标号,输出一种可能方案,输入数据保证至少有一组解

 

1=<n<=1e9N<=2k<=260

1~100组数据,1000MS

题解/思路:其实这道题找一下规律就好了,你会发现最左边两条路径分别可以表示±1,±3,……,±(2k-1)和±2,±4,……,±2k,所以只需判断这两条边哪条满足就好了(事实上分奇偶就好),至于输出方案,就从第k深度开始往上走,令now=n,每次走过一个点,若now>0,则加上这个点,若now<=0,则减去这个点(因为每个点标号比他的父辈的和还大,唯有这样才可能满足条件)

也可以用二进制方法进行构造(仍从k深度往上走),注意到0001=1000-0100-0010-0001,能发现最左边两条边就能构造出符合题意的解:把N转化成二进制,最后一位为0则从最左边节点出发,最后一位为1则从最左边节点的右边一个节点出发。若一个 1前面有零,则这个点选择-,前面的点也都选择-,直到下一个1再进行判断;若1前面为1,则选择+;重复该操作即可。

 

 

#include<iostream>
#include<cstring>
using namespace std;
int t,n,k,sb,tot;
int v[100][2];

bool ok(int dx,int now){
    if (now==1) if (dx==1 || dx==-1) {v[++tot][1]=dx==1?1:2;v[tot][0]=now;return true;}else return false;
    if (dx>0) {v[++tot][1]=1;v[tot][0]=now;return ok(dx-now,now/2);}else {v[++tot][1]=2;v[tot][0]=now;return ok(dx+now,now/2);}
}

int main()
{
    cin>>t;
    for (int q=1;q<=t;++q){
        cin>>n>>k;
        //memset(v,0,sizeof(v));
        sb=1<<(k-1);
        tot=0;
        if (!ok(n,sb)){
            tot=0;
            ok(n,sb+1);
        }
        cout<<"Case #"<<q<<":"<<endl;
        for (int i=tot;i>=1;--i)
            if (v[i][1]==1) cout<<v[i][0]<<" +"<<endl;
                else if (v[i][1]==2) cout<<v[i][0]<<" -"<<endl;
    }    
}

 

HDU 5573 题解