原始题目
Aizu-ITP2_11_C Aizu原始题面
Aizu-ITP2_11_C Vj题面
题目大意
给定集合大小,同时给定一个子集k,要求输出子集是该子集k的子集。同时输出其在原集合所有子集中的二进制序编号,根据二进制编号从小到大依次输出符合的子集。
解题思路
本题\(n≤28\)还可以枚举全部子集计数求其编号,一一枚举原集合子集计数然后判断会超时。
直接枚举给定子集k的子集,但是要根据其中元素计算在原集合所有子集中的二进制序编号。
实际上,编号就是该元素放在原集合子集中的二进制表示,由于题目本身就是原数字,所以直接二进制位运算可计算出其序号sum += (1 << a[j])
。
解题代码
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
| #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull;
ll a[100], n, m;
#define rep(i, a, n) for (ll i = a; i < n; ++i) #define per(i, a, n) for (ll i = n - 1; i >= a; --i)
void print_subset(ll n, ll m) { rep(i, 0, (1 << m)) { ll sum = 0; ll temp[100]; int ccnt = 0; rep(j, 0, m) { if (((1 << j) & i)) { temp[ccnt++] = a[j]; sum += (1 << a[j]); } } cout << sum << ":"; rep(j, 0, ccnt) { cout << " " << temp[j]; } cout << endl; } }
int main() { ios::sync_with_stdio(false); while (cin >> n) { cin >> m; rep(i, 0, m) cin >> a[i]; sort(a, a + m); print_subset(n, m); } }
|
收获与反思
直接根据元素构成计算其在全部子集中的序号。