天平难题(Mobile Computing, ACM/ICPC Tokyo

  • Post author:
  • Post category:其他


1.重点是求子集的代码

for


(


int


l = (s – 1)&s; l > 0; l = (l – 1)&s),


这里通过l可以求出s的所有子集。



可以举一个例子来理解 。



假设s = 1010 1100,   将s的0,2,4,5位抽出是1111



第一次, s-1 = 1010 1011 l = (s-1)&s = 10101000 l的 0,2,4,5位抽出是1110



第二次, l-1 = 10100111 l = (l-1)&s = 1010 0100, 将l的0,2,4,5位抽出是1101



第三次, l-1 = 1010 0011 l=(l-1)&s = 1010 0000, 将0,2,4,5位抽出是1100



第四次, l-1 = 1001 1111, l = (l-1) &s = 1000 1100, 将0,2,4,5位抽出是1011















可以发现规律,l的0,2,4,5位逐步递减,一直到0,并且其他位始终是0,这样l就遍历了s的所有子集。



证明也很简单,设s的i1,i2,i3……in位是1,并且l是s的子集,将l的i1,i2,i3……in位抽出得到a(i1)a(i2)a(i3)……a(in), 这里的a(ik)可以为0或1, 设l 中a(ix)是1,且其右边均是0,那么a(i(x+1))直到a(in)肯定都是0,当l-1时,相当于l的ix位变成0,后面所有位变成1,与s做与运算后,即a(ix)变成0,a(i(x+1))到a(in)变成1,也就是a(i1)a(i2)…a(i(x-1))1000…0 变成了a(i1)a(i2)…a(i(x-1))01111…1所以就是减一罗.







还有这里的解答树不只一个根节点,需要设置一个容器保存每个以s为根节点的一系列的树

#define _CRT_SECURE_NO_WARNINGS  
#include<iostream>  
#include<algorithm>  
#include<string>  
#include<sstream>  
#include<set>  
#include<vector>  
#include<stack>  
#include<map>  
#include<queue>  
#include<cassert>  
#include<cstdlib>  
#include<cstdio>  
#include<ctime>  
#include<cmath>  
#include<cstring>  
#include<functional>  
using namespace std;  
#define INF 0x3f3f3f3f  
#define max(a,b) ((a)>(b)?(a):(b))  
#define min(a,b) ((a)<(b)?(a):(b))  
using namespace std;  
const int N = 6;  
const int MAXN = (1 << N);  
int t, n, i, j, vis[MAXN];  
double w[N], sumw[MAXN], r;  
struct Node {  
	double l, r;  
	Node() {}  
	Node(double ll, double rr) { l = ll; r = rr; }  
};  
vector<Node> node[MAXN];  

int bitcount(int x) {  //计算二进制中1的个数  
	if (x == 0) return 0;  
	return bitcount(x / 2) + (x & 1);  
}  

void dfs(int s) {  
	if (vis[s]) return;//添加了记忆数组,如果状态s已经被搜索过,直接返回  
	vis[s] = 1;  
	if (bitcount(s) == 1) {  //当只有一个1时,说明是叶子,天平的两臂都是0  
		node[s].push_back(Node(0, 0));  
		return;  
	}  
	for (int l = (s - 1)&s; l > 0; l = (l - 1)&s) { //枚举左右子集情况,(此处利用二进制枚举左右子集的方法值得学习)  
		int r = s^l;  
		dfs(l); dfs(r);  
		for (int i = 0; i < node[l].size(); i++) {  
			for (int j = 0; j < node[r].size(); j++) {  
				double ll = min(-sumw[r] / (sumw[l] + sumw[r]) + node[l][i].l, sumw[l] / (sumw[l] + sumw[r]) + node[r][j].l);//比较 左臂+左子天平的左臂 与 右子天平的左臂-右臂  谁更小  
				double rr = max(sumw[l] / (sumw[l] + sumw[r]) + node[r][j].r, -sumw[r] / (sumw[l] + sumw[r]) + node[l][i].r);//比较 右臂+右子天平的右臂 与 左子天平的右臂-左臂  谁更大  
				node[s].push_back(Node(ll, rr));//将得到的该根节点的左右臂长度放入数组  
			}  
		}  
	}  
}  

void solve() {  
	double ans = -1;  
	int s = (1 << n) - 1;  
	dfs(s);  
	for (int i = 0; i < node[s].size(); i++) {  
		if (node[s][i].r - node[s][i].l < r) {//s结点是根结点,存有所有二叉树的左右臂的长度,选出差值<r的最大值即可  
			if (node[s][i].r - node[s][i].l > ans)  
				ans = node[s][i].r - node[s][i].l;  
		}  
	}  
	if (ans == -1) printf("-1\n");  
	else printf("%.10lf\n", ans);  
}  

int main() {  
	scanf("%d", &t);  
	while (t--) {  
		memset(vis, 0, sizeof(vis));  
		memset(node, 0, sizeof(node));  
		scanf("%lf%d", &r, &n);  
		for (i = 0; i < n; i++)  
			scanf("%lf", &w[i]);  

		//每一个子集对应的重量先存好
		for (i = 0; i < (1 << n); i++) {  
			sumw[i] = 0;  
			for (j = 0; j < n; j++) {  
				if (i&(1 << j))  
					sumw[i] += w[j];  
			}  
		}  
		solve();  
	}  
	return 0;  
} 



版权声明:本文为qq_25974431原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。