2 条题解

  • 1
    @ 2024-04-05 13:27:19
    #include <bits/stdc++.h>
    using namespace std;
    int n,k;
    int dfs(int k)
    {
        if(k<=n)
        {
            return n-k;
        }
        if(k%2)
        {
            return min(dfs(k+1)+1,dfs(k-1)+1);
        }
        else
        {
            return min(dfs(k/2)+1,k-n);
        }
    }
    int main()
    {
        ios::sync_with_stdio(false);
        cin>>n>>k;
        int ans=0;
        if(n==0)
        {
            n=1;
            ans=1;
        }
        ans+=dfs(k);
        cout<<ans;
        return 0;
    }
    
    

    //深搜可过,但不是最优解

    • @ 2024-08-26 21:43:00
      #include<iostream>
      using namespace std;
      int n, k, ans = 0;
      int dfs(int k){
          if(k <= n)return n-k;
          if(k & 1)return min(dfs(k+1), dfs(k-1)) + 1;
          else return min(dfs(k/2)+1, k-n);
      }
      int main(){
          ios::sync_with_stdio(false);
          cin >> n >> k;
          if(n == 0){
              n = 1;
              ans = 1;
          }
          cout << dfs(k) + ans;
          return 0;
      }
      
  • 0
    #include<algorithm> 
    #include<bitset> 
    #include<cstdio> 
    #include<cstring> 
    #include<ctime> 
    #include<cmath> 
    #include<cstdlib> 
    #include<iostream> 
    #include<iomanip> 
    #include<map> 
    #include<queue> 
    #include<stack> 
    #include<set> 
    #include<vector> 
    #include<bits/stdc++.h>
    using namespace std;
    const int MAXN=100000+10;
    int n,k;
    bool vis[MAXN];
    struct Node
    {
       int x,steps;
       Node(int _x,int _steps):x(_x),steps(_steps){};
    };
    queue<Node> q;
    void bfs()
    {
        q.push(Node(n,0));
        vis[n]=true;
        while(!q.empty())
        {
            Node cur=q.front();
            q.pop();
            int x=cur.x;
            if(x==k)
            {
                cout<<cur.steps<<endl;
                break;
            }
            else for(int i=1;i<=3;++i)
            {
                int nx;
                if(i==1)nx=x-1;
                if(i==2)nx=x+1;
                if(i==3)nx=x*2;
                if(nx>=0&&nx<=100000&&!vis[nx])
                {
                    vis[nx]=true;
                    q.push(Node(nx,cur.steps+1));
                }
            }
        }
    }
    int main()
    {
        memset(vis,false,sizeof(vis));
        cin>>n>>k;
        if(n==k)
        {
            cout<<0<<endl;
            return 0;
        }
        bfs();
        return 0;
    }
    
    
    
    
  • 1

信息

ID
1018
难度
6
分类
(无)
标签
递交数
105
已通过
26
通过率
25%
被复制
6
上传者