|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 |
#include <iostream> #include <sstream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <map> #include <list> #include <stack> using namespace std; int main(){ ios_base::sync_with_stdio(false); int casecnt; cin >> casecnt; while (casecnt--) { int n; cin >> n; vector<int> vote; int sumvote = 0; for (int i = 1; i <= n; i++) { int tmp; cin >> tmp; sumvote += tmp; vote.push_back(tmp); } //make maxn unsigned int maxn = 1; for (int i = 1; i < n; i++) { maxn <<= 1; maxn++; } int res[22]; memset(res, 0, sizeof(res)); for (int k = 1;k <= maxn; k++) { int curvote = 0,ck = k; for (int l = 0; l < n; l++) { if (ck&1) { curvote+=vote[l]; } ck >>= 1; } if (curvote > sumvote/2) { //effective team desu! for (int i = 1; i <= n; i++) { //make mask unsigned int mask = 1; mask <<= i-1; //done if (k&mask) { //in the team if (curvote - vote[i-1] <= sumvote/2) { res[i]++; } } } } } /* vector<int> res; //Calculation Proccess for (int i = 1; i <= n; i++) { //make mask unsigned int mask = 1; mask <<= i-1; //done int cnt = 0; for (int k = 1;k <= maxn; k++) { if(!(k&mask)) continue; unsigned int build = k & ~mask; //block i unsigned curvote = 0; for (int l = 0; l < n; l++) { if (build&1) { curvote+=vote[l]; } build >>= 1; } if (curvote <= sumvote/2 && curvote+vote[i-1] > sumvote/2) { cnt++; } } res.push_back(cnt); }*/ for (int i = 1; i <= n; i++) { cout << res[i]; if (i != n) { cout << ' '; } }cout << 'n'; } } |
这个题二进制枚举，但是姿势要正确，如果是先枚举每个人，然后根据这个人找到所有符合要求的情况，一个人一个人地出解，这样就太慢了。
好的姿势是直接枚举所有情况，对于每种情况，分别枚举把其中的一个人干掉之后是不是会小于总票数一半，符合要求的话就给那个人的计数器＋1，最后输出结果，这个姿势就快多了。
