首页 > 代码库 > HDU 1557 权利指数 状态压缩 暴力
HDU 1557 权利指数 状态压缩 暴力
HDU 1557 权利指数 状态压缩 暴力
ACM
题目地址:HDU 1557 权利指数
题意:
中文题,不解释。
分析:
枚举所有集合,计算集合中的和,判断集合里面的团体是否为关键团队。
代码:
/* * Author: illuz <iilluzen[at]gmail.com> * File: 1557.cpp * Create Date: 2014-06-28 14:47:58 * Descripton: brute force/ set */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 20; int t, n, tot; int a[N], ans[N], sub[N], scnt; int main() { scanf("%d", &t); while (t--) { memset(ans, 0, sizeof(ans)); tot = 0; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); tot += a[i]; } tot /= 2; // half total tickets int ALL = (1 << n); // subset 1 ~ 2^n-1 for (int i = 0; i < ALL; i++) { scnt = 0; // this subset's number int tmp = i, sum = 0, no = 0; while (tmp) { if (tmp & 1) { // if no is in subset sub[scnt++] = no; sum += a[no]; } tmp >>= 1; no++; } if (sum > tot) { // if success for (int j = 0; j < scnt; j++) { if (sum - a[sub[j]] <= tot) { // find out ans[sub[j]]++; } } } } // output printf("%d", ans[0]); for (int i = 1; i < n; i++) { printf(" %d", ans[i]); } puts(""); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。