蓝桥杯刷题冲刺 | 倒计时19天
作者：指针不指南吗
专栏：蓝桥杯倒计时冲刺🐾马上就要蓝桥杯了，最后的这几天尤为重要，不可懈怠哦🐾
文章目录
- 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”,也是可以的
