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;
}