首页 > 代码库 > HDU 5573 题解
HDU 5573 题解
题意:关于一只要续命的青蛙(雾),一颗完全二叉树,它的标号正如我们所期望的根为1,左儿子为父节点*2,右儿子为父节点*2+1,然后老青蛙从根往下走,一共走K步,它需要n个灵魂,每走过一个点,可以减去或加上这个点的标号,输出一种可能方案,输入数据保证至少有一组解
1=<n<=1e9,N<=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 题解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。