【二进制状态压缩+子集枚举/新增深搜】HDU 1557 权利指数

http://acm.hdu.edu.cn/showproblem.php?pid=1557


Problem Description
在选举问题中，总共有n个小团体，每个小团体拥有一定数量的选票数。如果其中m个小团体的票数和超过总票数的一半，则此组合为“获胜联盟”。n个团体可形成若干个获胜联盟。一个小团体要成为一个“关键加入者”的条件是：在其所在的获胜联盟中，如果缺少了这个小团体的加入，则此联盟不能成为获胜联盟。一个小团体的权利指数是指：一个小团体在所有获胜联盟中成为“关键加入者”的次数。请你计算每个小团体的权利指数。

Input
输入数据的第一行为一个正整数T，表示有T组测试数据。每一组测试数据的第一行为一个正整数n（0<n<=20）。第二行有n个正整数，分别表示1到n号小团体的票数。

Output
对每组测试数据，在同一个行按顺序输出1到n号小团体的权利指数。

Sample Input
2
1
10
7
5 7 4 8 6 7 5

Sample Output
1
16 22 16 24 20 22 16

#include <iostream>
using namespace std;

int main()
{
	int t, n, a[25], i, key[25], k, total, ans[25];
	scanf ("%d", &t);
	while (t--)
	{
		memset (ans, 0, sizeof(ans));
		total = 0;
		scanf ("%d", &n);
		for (i = 0; i < n; i++)
			scanf ("%d", a+i), total += a[i];
		total /= 2;    //总票数的一半【写成total = (total+1)/2 会错……】
		//枚举子集【1】~【2的n次方-1】
		int maxs = 1 << n;
		for (i = 1; i < maxs; i++)
		{
			k = 0;
			int tp = i, j = 0, sum = 0;
			while (tp)
			{
				if (tp & 1)//tp的二进制从左往右数第j位是1，则认为a[j]入了集合
					key[k++] = j, sum += a[j];
				//记住入了集合的a的元素编号j，并累加票数
				tp >>= 1;    //tp的二进制往右移动，即消去二进制最后一位
				j++;
			}
			if (sum > total)    //如果团体的票数超过总票数的一半
				for (j = 0; j < k; j++)
					if (sum - a[key[j]] <= total)
						ans[key[j]]++;
	//如果没了a[key[j]]就不行，则编号为key[j]的元素为“关键加入者”，该元素权利指数+1
		}
		printf ("%d", ans[0]);
		for (i = 1; i < n; i++)
			printf (" %d", ans[i]);
		printf ("\n");
	}
	return 0;
}

深搜：

#include <iostream>
using namespace std;

int con[25], ans[25], total, n, a[25], key;    //con存放a中元素编号
bool visited[25];

void dfs (int x, int sum, int times)//x是元素编号，sum是临时和，times是con中元素个数
{
    if (times == key)
    {
        if (sum > total)
            for (int i = 0; i < times; i++)
                if (sum - a[con[i]] <= total)
                    ans[con[i]]++;
        return ;
    }
    for (int i = x + 1; i < n; i++)
    {
        con[times] = i;
        dfs (i, sum+a[i], times+1);
    }
}

int main()
{
    int t, i;
    scanf ("%d", &t);
    while (t--)
    {
        scanf ("%d", &n);
        total = 0;
        for (i = 0; i < n; i++)
            scanf ("%d", a+i), total += a[i];
        total /= 2;
        memset (ans, 0, sizeof(ans));
        for (key = 1; key <= n; key++)    //枚举获胜联盟中团体个数
        {
            memset (visited, false, sizeof(visited));
            visited[0] = true;
            dfs (-1, 0, 0);
        }
        for (i = 0; i < n - 1; i++)
            printf ("%d ", ans[i]);
        printf ("%d\n", ans[n-1]);
    }
    return 0;
}

评论

2 楼 基德KID.1412 2011-08-02  

breakallerror 写道

木仔细看，貌似还是一种暴力

其实就是暴力

1 楼 breakallerror 2011-08-02  

木仔细看，貌似还是一种暴力