首页 > ACM题库 > UVA > UVA 1377-Ruler-BFS[解题报告]C++
2014
01-15

UVA 1377-Ruler-BFS[解题报告]C++

Xiaoming wants to make a special ruler, which can directly measure several given lengths. Xiaoming hopes to find a way, making the scale on ruler as few as possible, while for a given length, there exists two scales
on ruler and the distance between the two scales is equal to the given length. For scales as few as possible, we also hope the length of ruler as short as possible to save the material cost.

Input 

Input contains several cases. Each case has two lines. The first line is an integer n ( $ \leq$ n $ \leq$ 50)
to specify how many given lengths need to measure. The second line contains 
n integers d1d2,…dn,
indicating the length values respectively (
 $ \leq$ di $ \leq$ 106i $ \in$ [1, n]).

The last case is followed by a line containing a zero.

Output 

For each case, output three lines. The first line contains the case number. The second line is an integer Mto
specify the minimized number of scales needed. The third line is 
M integers to specify the distance between the leftmost scales
and the other 
M scales respectively.

Note: output scales in ascending order, the first number is always 0. You can assume that M won’t exceed 7.

Sample Input 

6
5 15 20 25 35 40
0

Sample Output 

Case 1:
4
0 5 25 40

题意:给定一些要测量的刻度,然后你要制造一把尺子,能测量这些,要求尺子的刻度数尽量少,并且尺子尽量短,题目保证刻度数不会大于7.

思路:BFS + 状态判重。每个尺子要测量刻度肯定由当前有的刻度去加或减可以得到一个新刻度,然后新刻度可以和其他的得到一些可以测量的刻度,注意M不会大于7,也就是说虽然题目说测量50个刻度,实际上只有C72,21个刻度,有很多重复的,这使得搜索时间复杂度不会太高。不过题目还有个条件,就是做出来的尺子最大刻度不能超过要测量的最大刻度,这点题目没说,WA了,还是看了别人题解才知道。

代码:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;

const int MAXN = 1000005;

int N, n, id[MAXN], d[25], cas = 0, Max, vis[2222222];

set<int>ans;
struct S {
	int state;
	set<int>ans;
} p;

void init() {
	int D; n = 0; ans.clear();
	memset(id, 0, sizeof(id));
	memset(vis, 0, sizeof(vis));
	for (int i = 0; i < N; i++) {
		scanf("%d", &D);
		if (!id[D]) {
			d[n++] = D;
			id[D] = 1;
		}
	}
	sort(d, d + n);
	Max = d[n - 1];
	memset(id, -1, sizeof(id));
	for (int j = 0; j < n; j++)
		id[d[j]] = j;
}

void BFS() {
	queue<S>Q;
	p.ans.clear(); p.ans.insert(0); p.state = 0;
	Q.push(p);
	while (!Q.empty()) {
		p = Q.front(); Q.pop();	
		if (p.state == (1<<n) - 1) {
			if (ans.size() == 0) {
				ans = p.ans;
			}
			else {
				if (ans.size() < p.ans.size()) return;
				else if (ans.size() > p.ans.size()) ans = p.ans;
				else {
					if (*ans.rbegin() > *p.ans.rbegin())
						ans = p.ans;
				}
			}
		}
		if (p.ans.size() == 7) continue;
		for (int i = 0; i < n; i++) {
			if ((p.state&(1<<i))) continue;
			for (set<int>::iterator it = p.ans.begin(); it != p.ans.end(); it++) {
				if (*it > d[i]) {
					S q = p;
					int sum = *it - d[i];
					for (set<int>::iterator it2 = q.ans.begin(); it2 != q.ans.end(); it2++) {
						int nu = abs(*it2 - sum);
						if (id[nu] == -1) continue;
						q.state = (q.state|(1<<id[nu]));
					}
					q.ans.insert(sum);
					if (!vis[q.state]) {
						Q.push(q);
						vis[q.state] = 1;
					}
				}
				if (*it + d[i] <= Max) {
					S q = p;
					int sum = *it + d[i];
					for (set<int>::iterator it2 = q.ans.begin(); it2 != q.ans.end(); it2++) {
						int nu = abs(*it2 - sum);
						if (id[nu] == -1) continue;
						q.state = (q.state|(1<<id[nu]));
					}
					q.ans.insert(sum);
					if (!vis[q.state]) {
						Q.push(q);
						vis[q.state] = 1;
					}
				}
			}
		}
	}
}

void solve() {
	BFS(); int bo = 0;
	printf("Case %d:\n%d\n", ++cas, ans.size());
	for (set<int>::iterator it = ans.begin(); it != ans.end(); it++) {
		if (bo++) printf(" ");
		printf("%d", *it);
	}
	printf("\n");
}

int main() {
	while (~scanf("%d", &N) && N) {
		init();
		solve();
	}
	return 0;
}

转自:http://blog.csdn.net/accelerator_/article/details/18312437


  1. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  2. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。

  3. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c

  4. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。