【Aizu-ITP2_11_A】解题报告(二进制枚举)
原始题目
题目大意
根据二进制序编号,从0开始输出子集。
解题思路
枚举所有二进制可能,然后根据各位情况输出元素。
解题代码
1 |
|
收获与反思
枚举子集常见的思路
回溯法(根据排列好的子集字典序输出)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15void print_subset1(int N, int* A, int cnt)
{
cout << "{";
rep(i, 0, cnt)
{
cout << A[i] << " ";
}
cout << "}" << endl;
int nxt = cnt ? A[cnt - 1] + 1 : 0;
rep(i, nxt, N)
{
A[cnt] = i;
print_subset1(N, A, cnt + 1);
}
}枚举二进制位
1
2
3
4
5
6
7
8
9
10
11
12
13void print_subset2(int N, int* A)
{
rep(i, 0, (1 << N))
{
cout << "{";
rep(j, 0, N)
{
if ((1 << j) & i)
cout << A[j] << " ";
}
cout << "}" << endl;
}
}
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!