题目链接：https://www.nowcoder.com/acm/contest/106/J

题意就是给你两个数a,b，然后a每次可以加1减1或者加f(x)减f(x)，f(x)的值就是x的二进制的1的个数，问a最少需要变换多少次才能变成b。直接用bfs就能做了，二进制的话用bitset会方便一点，剩下就看代码吧。


AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <bitset>
using namespace std;
struct Node
{
  int x,step;
}S,E,Now,Next;
int vis[1000005];

int fun(int x)
{
  int ans = 0;
  bitset<20> b(x);
  string str = b.to_string();
  int len = str.length();
  for(int i=0;i<len;i++)
  {
    if(str[i]=='1')ans++;
  }
  return ans;
}

int bfs(){
  memset(vis,0,sizeof(vis));
  S.step = 0;
  queue<Node> q;
  q.push(S);
  while(!q.empty())
  {
    Now = q.front();
    q.pop();
    if(Now.x == E.x)
    {
      return Now.step;
    }
    for(int i=0;i<4;i++)
    {
      if(i==0)Next.x=Now.x+1;
      if(i==1)Next.x=Now.x-1;
      if(i==2)Next.x=fun(Now.x) + Now.x;
      if(i==3)Next.x=Now.x - fun(Now.x);
      if(Next.x>=0 && Next.x <= 1000000 && vis[Next.x]==0){
        vis[Next.x] = 1;
        Next.step = Now.step + 1;
        q.push(Next);
      }
    }
  }
    return 0;
}

int main()
{
  scanf("%d%d",&S.x,&E.x);
  int temp = bfs();
  printf("%d\n",temp);
  return 0;
}