蓝桥杯刷题冲刺 | 倒计时19天

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

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

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;elsenext.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”,也是可以的