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 (  n  50)
to specify how many given lengths need to measure. The second line contains
n integers d1d2,…dn,
indicating the length values respectively (
di  106i  [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

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

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树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。