欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

例题 7-7 天平难题(Mobile Computing,ACM/ICPC Tokyo 2005,UVa1354)

程序员文章站 2022-06-02 19:47:19
...

原题链接:https://vjudge.net/problem/UVA-1354
分类:二进制法
备注:枚举二叉树,好题

根据紫书思路:每次从集合任意选两个节点组成一个新节点。

  之前自己试的时候,并没有用什么技巧,但是没做出来,然后看了作者的代码,实在是妙啊。这部分之前的内容讲了子集生成,有增量构造法,位向量法,二进制法。见识了二进制法的妙用,比自己想的快多了。
  以后有时间就算能自己写出例题也应该看看lrj的代码,毕竟都是精品,光顾着自己的那点可怜知识,就算写出了题也不一定有多少进步。

代码如下:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = 7;
struct node {
	double L, R;
	node() :L(0), R(0) {}
};
int t, s, vis[1 << maxn];//标记集合是否被访问过
double r, w[maxn], sum[1 << maxn];//标记集合i的总重量
vector<node>tree[1 << maxn];//tree[i]表示集合i对应的结果
void print(int x) {//自己查看二进制数是如何运行的代码= =、
	int a[7], pos = 0;
	while (x) {
		a[pos++] = x % 2;
		x /= 2;
	}
	for (int i = pos; i < s; i++)printf("0");
	for (int i = pos - 1; i >= 0; i--)
		printf("%d", a[i]);
	printf("\n");
}
void dfs(int subset) {
	if (vis[subset])return;
	vis[subset] = 1;
	bool hav_children = false;
	for (int lef = (subset - 1) & subset; lef; lef = (lef - 1) & subset) {
		//a&(a-1)可以去掉a的二进制数上最右边的1,作为左子树
		hav_children = true;

		int rig = subset ^ lef;//rig为被去掉的所有的1,作为右子树
		/*printf("subset::");
		print(subset);
		printf("lef::");
		print(lef);
		printf("rig::");
		print(rig);*/
		double d1 = sum[rig] / sum[subset];
		double d2 = sum[lef] / sum[subset];
		dfs(lef); dfs(rig);//找遍左右子树的所有可能
		//任意选出一个左子树和一个右子树进行搭配
		for (int i = 0; i < tree[lef].size(); i++) {
			for (int j = 0; j < tree[rig].size(); j++) {
				node t;
				t.L = max(tree[lef][i].L + d1, tree[rig][j].L - d2);
				t.R = max(tree[rig][j].R + d2, tree[lef][i].R - d1);
				if (t.L + t.R < r)tree[subset].push_back(t);
			}
		}
	}
	if (!hav_children)tree[subset].push_back(node());//叶子无子树,要保证父亲能利用
}
int main(void) {
	scanf("%d", &t);
	while (t--) {
		memset(vis, 0, sizeof(vis));
		scanf("%lf %d", &r, &s);
		for (int i = 0; i < s; i++)scanf("%lf", &w[i]);
		for (int i = 0; i < (1 << s); i++) {
			sum[i] = 0;
			tree[i].clear();
			for (int j = 0; j < s; j++)
				if (i & (1 << j))sum[i] += w[j];
		}
		int root = (1 << s) - 1;
		dfs(root);
		double ans = -1;
		for (int i = 0; i < tree[root].size(); i++)
			ans = max(ans, tree[root][i].L + tree[root][i].R);
		printf("%.16f\n", ans);
	}
	return 0;
}


自己的失败代码在此:

  目前找不到错误的原因,每次考虑了左右力臂的两种情况,缺点应该就是慢了点。像上面的二进制法,C++用二进制运算符是很快的,应当加强对二进制在集合上的应用的理解。
  有点可惜的就是这份代码的答案和uDebug的答案误差没超过10^-8,按理来说应该能AC的…
  补:第一个5W例子的,从输出16位小数变成输出15位小数,答案完全匹配…
例题 7-7 天平难题(Mobile Computing,ACM/ICPC Tokyo 2005,UVa1354)

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 6;
int t, s;
double r, ans;
struct node {
	double weight, lef, rig;
	node(int _w = 0, double _l = 0, double _r = 0) :weight(_w), lef(_l), rig(_r) {}
};//中心的位置,左边长和右边长
void dfs(node* g, int len) {
	for (int i = 0; i < len - 1; i++)
		for (int j = i + 1; j < len; j++) {
			double tot = g[i].weight + g[j].weight;
			double lef = g[j].weight / tot;
			double rig = g[i].weight / tot;
			//g[i]在左,g[j]在右                   左臂+原左臂     右臂+原右臂
			node nowNode(g[i].weight + g[j].weight, max(lef + g[i].lef, g[j].lef - rig), max(rig + g[j].rig, g[i].rig - lef));
			node tmp[maxn]; tmp[0] = nowNode;
			for (int k = 1, pos = 0; k < len - 1; k++) {
				while (pos == i || pos == j)pos++;
				tmp[k] = g[pos++];
			}
			if (nowNode.lef + nowNode.rig < r) {
				if (len == 2) ans = max(ans, nowNode.lef + nowNode.rig);
				else dfs(tmp, len - 1);
			}
			//g[j]在左,g[i]在右,此时rig是左臂,lef是右臂
			tmp[0].lef = max(g[j].lef + rig, g[i].lef - lef);
			tmp[0].rig = max(g[i].rig + lef, g[j].rig - rig);
			if (tmp[0].lef + tmp[0].rig < r) {
				if (len == 2) ans = max(ans, tmp[0].lef + tmp[0].rig);
				else dfs(tmp, len - 1);
			}//增加
		}
}
int main(void) {
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	scanf("%d", &t);
	while (t--) {
		node g[maxn];
		scanf("%lf %d", &r, &s);
		for (int i = 0; i < s; i++) {
			double w; scanf("%lf", &w);
			g[i] = node(w, 0, 0);
		}
		if (s == 1) {
			printf("%.15f\n", 0); continue;
		}
		ans = -1;
		dfs(g, s);
		printf("%.15f\n", ans);
	}
	return 0;
}