关键词:
链接:https://www.nowcoder.com/acm/contest/106/J
来源:牛客网
题目描述
It’s universally acknowledged that there’re innumerable trees in the campus of HUST.
And there are many different types of trees in HUST, each of which has a number represent its type. The doctors of biology in HUST find 4 different ways to change the tree’s type x into a new type y:
1.??? y=x+1
2.??? y=x-1
3.??? y=x+f(x)
4.??? y=x-f(x)
The function f(x) is defined as the number of 1 in x in binary representation. For example, f(1)=1, f(2)=1, f(3)=2, f(10)=2.
Now the doctors are given a tree of the type A. The doctors want to change its type into B. Because each step will cost a huge amount of money, you need to help them figure out the minimum steps to change the type of the tree into B.?
Remember the type number should always be a natural number (0 included).
输入描述:
One line with two integers A and B, the init type and the target type.
输出描述:
You need to print a integer representing the minimum steps.
示例1
输入
5 12
输出
3
说明
The minimum steps they should take: 5->7->10->12. Thus the answer is 3.
【题意】:通过4种操作n最少几步可以达到m。
【出处】:poj 3278
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int n,k;
const int MAXN=1000010;
int visited[MAXN];//判重标记,visited[i]=true表示i已经拓展过
struct step
int x;//位置
int steps;//到达x所需的步数
step(int xx,int s):x(xx),steps(s)
;
queue<step>q;//队列(Open表)
int f(int x)
int c=0;
while(x)
if(x&1) c++;
x>>=1;
return c;
int main()
cin>>n>>k;
memset(visited,0,sizeof(visited));
q.push(step(n,0));
visited[n]=1;
while(!q.empty())
step s=q.front();
if(s.x==k)//找到目标
cout<<s.steps<<endl;
return 0;
else
if(s.x-1>=0 && !visited[s.x-1])
q.push(step(s.x-1,s.steps+1));
visited[s.x-1]=1;
if(s.x+1<=MAXN && !visited[s.x+1])
q.push(step(s.x+1,s.steps+1));
visited[s.x+1]=1;
if(s.x+f(s.x)<=MAXN&&!visited[s.x+f(s.x)])
q.push(step(s.x+f(s.x),s.steps+1));
visited[s.x+f(s.x)]=1;
if(s.x-f(s.x)>=0&&!visited[s.x-f(s.x)])
q.push(step(s.x-f(s.x),s.steps+1));
visited[s.x-f(s.x)]=1;
q.pop();
return 0;
第十四届华中科技大学程序设计竞赛--jvarioustree(代码片段)
链接:https://www.nowcoder.com/acm/contest/106/J来源:牛客网时间限制:C/C++1秒,其他语言2秒空间限制:C/C++32768K,其他语言65536K64bitIOFormat:%lld题目描述It’suniversallyacknowledgedthatthere’reinnumerabletreesinthecampusofH 查看详情
第十四届华中科技大学程序设计竞赛cprofessionalmanager并查集删除/虚点(代码片段)
题目描述It’suniversallyacknowledgedthatthere’reinnumerabletreesinthecampusofHUST.Thusaprofessionaltreemanagerisneeded.Yourtaskistowriteaprogramtohelpmanagethetrees.Initially,therearenforestsandforthei-thf 查看详情
第十四届全国大学生智能车竞赛竞赛技术报告下载链接
第十四届智能车竞赛技术报告下载链接 01下载报告 今天上午,看到有同学询问关于十四届智能车竞赛技术报告下载的询问。 实际上,之前第十四届的技术报告在百度上有, 只是没有能够提供下载链接。 由... 查看详情
第十四届华中科技大学程序设计竞赛jvarioustree数值型一维bfs/最小步数(代码片段)
链接:https://www.nowcoder.com/acm/contest/106/J来源:牛客网题目描述It’suniversallyacknowledgedthatthere’reinnumerabletreesinthecampusofHUST.AndtherearemanydifferenttypesoftreesinHUST,eachofwhichhasanumberrepresen 查看详情
浙江财经大学第十四届程序设计竞赛题解
【题面pdf下载】链接:https://pan.baidu.com/s/1Eb16fHtNYMLrRk9QnXWa-g密码:dwn8【题目牛客网提交链接】【现场赛排名】链接:https://pan.baidu.com/s/1jfzH6-7BoPhEjnijGQK53w密码:y669 感谢各位大佬的参赛。 由于命题人水平不高,而且之前没... 查看详情
第十四届华中科技大学程序设计竞赛kwalkingintheforest二分答案/最小化最大值(代码片段)
链接:https://www.nowcoder.com/acm/contest/106/K来源:牛客网题目描述It’suniversallyacknowledgedthatthere’reinnumerabletreesinthecampusofHUST.Nowyou'regoingtowalkthroughalargeforest.ThereisapathconsistingofNsto 查看详情
长春理工大学第十四届程序设计竞赛(重现赛)m.orxzone
链接:https://ac.nowcoder.com/acm/contest/912/M题意:DaenerysStormborn,风暴中出生的丹尼莉丝,theUnburnt,烧不死的,QueenofMeereen,弥林女王,QueenoftheAndalsandtheRhoynarandtheFirstMen,安达尔人,罗伊那人,和先民的女王,LordoftheSevenKingdoms,七国之主 查看详情
长春理工大学第十四届程序设计竞赛(重现赛)h
H.ArithmeticSequence题目链接:https://ac.nowcoder.com/acm/contest/912/H题目数竞选手小r最喜欢做的题型是数列大题,并且每一道都能得到满分。你可能不相信,但其实他发现了一个结论:只要是数列,无论是给了通项还是给了递推式,无论... 查看详情
长春理工大学第十四届程序设计竞赛(重现赛)f(代码片段)
F.SuccessionediFixoracci题目链接:https://ac.nowcoder.com/acm/contest/912/F 题目:动态规划(Dynamicprogramming,简称dp)是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。例如,假设小x一步能爬1层或2层台阶,求小x爬n... 查看详情
长春理工大学第十四届程序设计竞赛(重现赛)b(代码片段)
BBowlingGame题目链接:https://ac.nowcoder.com/acm/contest/912/B题目CUST的队员打完省赛后,小r带着大家去打保龄球。保龄球是一项难度非常高的游戏,然而这根本难不住校队成员,他们个个都很厉害(炸和)一发10个瓶都倒。尤其是小r,每次... 查看详情
长春理工大学第十四届程序设计竞赛(重现赛)j.printout
链接:https://ac.nowcoder.com/acm/contest/912/J题意:小r为了打校赛,他打算去打字社打印一份包含世界上所有算法的模板。到了打字社,小r一看价格:总打印页数X0X0页以下(不含X0X0)x0x0元每页,X0∼X1X0∼X1页(不含X1X1)x1x1元每页,X1&si... 查看详情
hdu6467简单数学题递推公式&&o优化乘法(广东工业大学第十四届程序设计竞赛)(代码片段)
...rce“字节跳动-文远知行杯”广东工业大学第十四届程序设计竞赛 解题思路: 但是这道题只推出递推 查看详情
广东工业大学第十四届程序设计竞赛鸽子数(代码片段)
ProblemDescription通常来说,题面短的题目一般都比较难,所以我要把题面写得很长很长。通常来说,题面短的题目一般都比较难,所以我要把题面写得很长很长。通常来说,题面短的题目一般都比较难,所以我要把题面写得很长很... 查看详情
(未完成)[hduoj]“字节跳动-文远知行杯”广东工业大学第十四届程序设计竞赛(代码片段)
solved5 A(签到)题意:两个人随机得到0或1其中之一数字,每个人都可以猜对方的数字是什么,有一个人猜对就算成功,问最优策略下00,01,10,11四种情况两人的成功概率分别是多少。题意不明的签到题,题面说两人不能沟通... 查看详情
湖南大学第十四届acm程序设计新生杯e.easyproblem(代码片段)
E.EasyProblemDescription:Zghhlikesnumber,buthedoesn‘tlikewritingproblemdescription.Sohewilljustgiveyouaprobleminsteadoftellingalongstoryforit.Nowgivenapositiveintegerxandkdigitsa1,a2,...,ak,canyoufindapositiveintegerysuchthatyisthemultipleofxandindecimalrepresentationycontainsalldigitsofa1,a2,...,... 查看详情
第五届湖南省机器人大赛暨第十四届湖南省智能汽车大赛名单(代码片段)
简介:本文汇总了第五届湖南省智能车竞赛的基本信息。感谢中南大学王击老师发送过来的信息。关键词:湖南省智能车竞赛,智能车竞赛#mermaid-svg-Bl4gxd2xsRwJqsTIfont-family:"trebuchetms",verdana,arial,sans-serif;font-size:16px;fill:#3... 查看详情
第十四届蓝桥杯(web应用开发)模拟赛1期-大学组(代码片段)
数据类型检测请看这篇数据类型检测渐变色背景生成器html<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"/><metahttp-equiv="X-UA-Compatible"content="IE 查看详情
第十四届蓝桥杯c/c++_大学b组省赛真题
...或其它方式提交的答案无效。试题包含“结果填空”和“程序设计”两种题型。结果填空题:要求选手根据题目描述直接填写结果。求解方式不限。不要求源代码。把结果填空的答案直接通过网页提交即可,不要书写多... 查看详情