1.5 枚举子集

发表于 | 更新于 | 分类于 | 阅读次数：

实验任务

对于两个不同的整数集合 \(A\) 与 \(B\)，我们根据两个集合的字典序来比较它们的大小。具体来说：

  1. 先从两个集合中各自取出最大的元素 \(a_1\) 和 \(b_1\)进行比较，若 \(a_1<b_1\)或 \(a_1\) 不存在（即 \(A\) 为空集），那么 \(A<B\)，反之亦然；
  2. 若最大的元素 \(a_1\)和 \(b_1\)相等，再取出各自第二大的元素 \(a_2\)和 \(b_2\)比较。若 \(a_2<b_2\)或 \(a_2\)不存在（即 \(A\) 中只有一个元素），那么\(A<B\)，反之亦然；
  3. 若 \(a_2\)和 \(b_2\)仍相等，则取各自第三大元素进行比较，以此类推。

（例如：{}<{3}<{3,1}<{3,2}<{4}。）

按照以上规则，一个集合的所有子集可以按一定顺序从小到大排列。现在给出一个整数集合 \(S\) 及两个正整数 \(L\)、 \(R\)，你需要输出 \(S\) 的第 \(L\) 小到第 \(R\) 小子集。

数据输入

输入第一行为一个正整数 \(n\)，表示 \(S\) 中的元素数目。第二行 \(n\) 个整数，表示 \(S\) 中的元素，以空格隔开；元素大小在 \(int\) 范围内。第三行两个正整数 \(L\)、 \(R\)，含义如上。

数据输出

按从小到大的顺序输出 \(S\) 的第 \(L\) 小到第 \(R\) 小子集，每个子集一行；每行最外层为大括号“{}”，括号中从大到小列出子集的元素。若元素个数大于 2，相邻元素以逗号“,”隔开。详见以下示例。

输入示例 输出示例
3
3 4 1
1 5		 {}
{1}
{3}
{3,1}
{4}

数据范围

\(L\leq R\leq 2^n\)，\(R-L\leq 1000\)，集合中元素不重复。\(80\%\)的得分点，\(n\leq 10\)，其余 \(20\%\)的得分点，\(n\leq 30\)。

源代码

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
#include <stdio.h>
#include <algorithm>
using namespace std;
#define maxn 31
int Set[maxn];

void print(int num, int n){
    printf("{");
    bool isfirst = true;
    int i;
    for (i = n - 1; i >= 0; --i)//从第0位开始
        if (num & (1 << i)) {
            if (isfirst) {
                printf("%d", Set[i]);
                isfirst = false;
            }
            else
                printf(",%d", Set[i]);
        }
    printf("}\n");
}

int main(){
    int i;
    int n, left, right;
    scanf("%d", &n);
    for (i = 0; i < n; ++i)
        scanf("%d", &Set[i]);
    scanf("%d%d", &left, &right);
    sort(Set, Set + n);
    for (i = left - 1; i < right; ++i)
        print(i, n);
    return 0;
}

设计思路与复杂度分析

首先数据范围\(n\leq 30\)，其次通过观察可以发现集合顺序与二进制顺序高度一致。所以可以将问题转化为一个数二进制表示时1出现的位置。时间复杂度为\(O(n(R-L))\)。

0%