本文共 1393 字，大约阅读时间需要 4 分钟。

第三题：一个有趣的题

题目大意及算法分析：

说是要找到n的倍数m，且m是一个由0和1表示的十进制数。

由0和1表示的十进制正数最小的是1，然后是10、11、100、 101……我们可以发现，这些数字其实是可以后面的由前面的得到，也就是已知一个数num是具有上述性质的，那么（10 * num） 和（10 * num + 1）也就是具有上述性质的数，所以我们可以用一个队列来模拟枚举。 枚举如下： 最小的是1，1 不满足，则（1 * 10）入队，（1 * 10 + 1）入队，这样依次走下来，就依次从小到大地把只由0和1组成的十进制数都枚举了！

Solving code:

#include 
   
    #include 
    
     #define LL long longusing namespace std;void bfs(int n){	queue
     
       q;	q.push(1);	while(true){		LL ans = q.front();q.pop();		if(0 == ans % n){			printf("%lld\n",ans);			return ;		}		q.push(ans * 10);		q.push(ans * 10 + 1);	}}int main(){	int n;	while(~scanf("%d",&n) && n){		bfs(n);	}	return 0;}
     
    
   

第四题：抓牛

我们在位置n上，牛在位置k上，我们有三种抓牛的策略： ①：可以前进一步 ②：可以后退一步 ③：可以闪现到2 * n的位置上去 问最快需要几步能够抓到牛？

算法分析：

如果我们的位置在牛的位置的后头，那么我们肯定只能够后退！

如果我们的牛的位置k是一个偶数，我们来分析，从n到一个偶数的位置，如果先后退再前进，这肯定是无谓的操作；如果先后退再两倍，这也是无谓的操作，因为我后退再两倍，假设就到达了k，那么我两倍再后退也是一样的，所以我们在这种情况下，只需要考虑一直前进到k和两倍闪现。我们在这里还有一个技巧，就是假设人不动，让牛动，因为我们打算倒着推，这样才能让k有奇偶数的变化。 如果我们的牛的位置k是一个奇数，那么我们只能让牛前进或后退。

Solving code:

#include 
   
    using namespace std;inline int Min(int a, int b){	return a > b ? b : a;}int dp(int n, int k){	if(n >= k)		return n - k;	if(0 == k % 2)		return Min(k - n, dp(n, k / 2) + 1);	else		return Min(dp(n, k + 1), dp(n, k - 1)) + 1;}int main(){	int n, k, add = 0;	cin >> n >> k;	if(!n)	add = 1, n = 1;	cout << dp(n, k) + add;	return 0;}
   

注意：

这里我们需要判断起始位置是不是0，因为0两倍是无效的，所以只能通过从1到0，所以我们预处理一步，假设从0开始，我们第一步只能先变成1！