作者：指针不指南吗
专栏：蓝桥杯倒计时冲刺

🐾马上就要蓝桥杯了，最后的这几天尤为重要，不可懈怠哦🐾

文章目录

• 1.抓住那头牛
• 2.排列序数

1.抓住那头牛

• 题目

  链接： 抓住那头牛 - C语言网 (dotcpp.com)

  题目描述

  农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0≤N≤100000)，牛位于点K(0≤K≤100000)。农夫有两种移动方式：

  输入格式

  两个整数，N和K。

  输出格式

  一个整数，农夫抓到牛所要花费的最小分钟数。

  样例输入

  5 17
  

  样例输出

  4
  

• 第一次 AC 50%

  #include<bits/stdc++.h>
  using namespace std;
  
  int main()
  {
  	int n,k;
  	scanf("%d%d",&n,&k);
  	
  	if(n==k)
  	{
  		printf("0");
  		return 0;
  	}
  	
  	if(n>k)
  	{
  		printf("%d",n-k);
  		return 0;
  	}
  	
  	if(n<k)
  	{
  		printf("%d",max(1+n-k,k-n));
  		return 0; 
  	}
  	
  	return 0;
   } 
  

• 第二次 AC 50%

  #include<bits/stdc++.h>
  using namespace std;
  
  int main()
  {
  	int n,k;
  	scanf("%d%d",&n,&k);
  	
  	if(n==k)
  	{
  		printf("0");
  		return 0;
  	}
  	
  	if(n>k)
  	{
  		printf("%d",n-k);
  		return 0;
  	}
  	
  	if(n<k)
  	{
  		int x=n,cnt=0;
  		while(x<k)
  		{
  			x*=2;
  			cnt++;
  		}
  		
  		if(cnt+k-x<0)
  		{
  			printf("%d",min(k-n,cnt+x-k));
  			return 0;
  		}
  		else
  		{
  			int c=min(k-n,cnt+x-k);
  			printf("%d",min(c,cnt+k-x));
  			return 0;
  		}
  		
  	}
  	
  	return 0;
   } 
  

• DFS 题解

  #include<bits/stdc++.h>
  using namespace std;
  
  int n,k;
  
  //深度搜索
  int dfs(int t) //n到t的时间 
  {
  	//不能乘车 
  	if(t<=n) 
  		return n-t;
  	
      //目标地分情况：奇数和偶数
      //为什么这么分呢？
      //偶数可以直接到，直接一步一步走那里
      //奇数：分成，到t前面往后退一步，到t后面，往前走一步
  	if(t%2==1)
  	{
  		return min(dfs(t-1)+1,dfs(t+1)+1);
  	}
  	else
  	{
  		return min(dfs(t/2)+1,t-n);
  	}
  	
  }
  
  
  int main()
  {
  	
  	cin>>n>>k;
  	
  	int s=0;
  	
  	if(n==0)  //特判一下，如果n==0,2x没有用，抓牛过程中无论如何至少会往前走一步
  	{
  		n++;
  		s++;
  	}
  	
  	s+=dfs(k);
  	
  	cout<<s<<endl;
  	
  	return 0;
   } 
  

• 我的 low BFS

  #include<bits/stdc++.h>
  using namespace std;
  
  int n,k;
  
  //bfs 可以走的点放进队列里面，走没走过的点，然后走到想要的结果
   
   int d[100010];
   
   bool st[100010]; 
   
  int bfs()
  {
  	queue<int> q;
  	q.push(n);
  	
  	memset(d,-1,sizeof d);
  	
  	while(q.size())
  	{
  		int t=q.front();
  		q.pop();
  		
  		//分情况 
  		if(t==k) return 0;
  		//扩展  三种情况
  		q.push(t+1);
  		q.push(t-1);
  		q.push(2*t);
  		d[t];
  	}
  	return d[k];
  	
  }
  
  int main()
  {
  	cin>>n>>k;
  	
  	cout<<bfs(); 
  	
  	return 0;
  }
  

别笑emmm，我也不知道我写的是个什么

• 正确 BFS

  #include<iostream>
  #include<cstdio>
  #include<cstring>
  #include<queue>
  using namespace std;
  const int MAXN=100001;
  struct status{
      int n,t;
      status(int n,int t)
      {
          n=n;
          t=t;
      }
  };
  bool visit[MAXN];
   
  int BFS(int n,int k){
      queue<status> myqueue;
      myqueue.push(status(n,0));//压入初始状态
      visit[n]=true; //起始点已被访问
      while(!myqueue.empty())
      {
          status current=myqueue.front();
          myqueue.pop();
          if(current.n==k)//查找成功
              return current.t;
          for(int i=0;i<3;i++)//转入不同状态 
          {
              status next(current.n,current.t+1);
              if(i==0)
                  next.n+=1;
              else if(i==1)
                  next.n-=1;
              else
                  next.n*=2;
              if(next.n<0||next.n>=MAXN||visit[next.n])
                  continue;//新状态不合法
              myqueue.push(next);//压入新的状态
              visit[next.n]=true;//该点已被访问
          } 
      }
  }
  int main()
  {
      int n,k;
      cin>>n>>k;
      memset(visit,false,sizeof(visit));//初始化；
      cout<<BFS(n,k)<<endl;
      return 0;
  }
  

  正在进一步的理解 这个BFS算法，还没有完全掌握

• 反思

  一开始把这道题想成简单的模拟了，可以 AC 50%，还ok

  • 模拟过程中，第一次没有考虑全面

  后面又改了一次，还是不行，看题解

  真没想到，这个使用的是 dfs 和bfs ，果然做的题还是太少了

  • dfs 递归回溯
  • bfs 不断扩展 直到找到结果

2.排列序数

今天新学的知识点，跟大家分享一下，特别帅

先输入字符串 s ，然后使用 next_permutation() 输出全排列，当全排列与初始字符串相等时结束

#include<bits/stdc++.h>
using namespace std;


int main()
{
	string s="bac";
	
	sort(s.begin(),s.end());
	
	do{
		cout<<s<<endl;
	}while(next_permutation(s.begin(),s.end()));
	
	
	return 0;
}

s=“12345”,也是可以的