ACM-ICPC寒假算法训练1：搜索专题C题和D题

本文主要是介绍ACM-ICPC寒假算法训练1：搜索专题C题和D题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

POJ 1426 寻找倍数

题目大意及算法分析：

说是要找到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 <cstdio>
#include <queue>
#define LL long long
using namespace std;

void bfs(int n){
	queue<LL> 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 <iostream>
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！

这篇关于ACM-ICPC寒假算法训练1：搜索专题C题和D题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！