c++子集枚举

相信大家都做过 烤鸡 这道题。但 $10$ 个循环实在太麻烦。若要 $100、1000$ 个循环呢?

子集枚举！

文章目录

• 一、子集枚举的定义
• 二、代码实现
• 三、例题
• • • P1657 选书
    • • • 时间限制
        • 内存限制
        • 题目描述
        • 输入格式
        • 输出格式
        • 输入输出样例
        • 输出 #1复制
        • 说明/提示
        • 分析
• 四、复杂度分析

一、子集枚举的定义

什么是子集枚举？

• 对于一个数据，若每个数据只有 $2$ 种状态，例如：选或不选，选第一种或第二种……这时，子集枚举就成为一种很好的选择。
• 因为每个数据只有 $2$ 种状态，由此想到 $2$ 进制。$0$ 代表第一种状态， $1$ 代表第二种状态。此时每个十进制数在二进制下的表示就代表一种状态。

二、代码实现

#include 
#include 
using namespace std;int n;  // n 表示共有几个数据// 子集枚举
void work() {int U = (1 << n); // (1 << n) 意为 pow(2, n) 。但不同的是，(1 << n) 为 int 类型， pow(2, n) 为 double 类型。根据情况自己选择。// 0(10) = 0000(2) 是一种选择， 但U(10) = 100...0(n 个 0) 不是选择。所以枚举范围是 [0, U) 。for(int S = 0; S < U; S++) /*遍历每种情况*/ {if(/*判断语句*/ )/*执行语句*/;}/*例：int ans = 0;for(int S = 0; S < U; S++) {if(__builtin_popcount(S) == k) // 这个函数意为计算 S 在二进制下 1 的个数。ans++;}printf("%d", ans);*/printf(/*输出内容*/);return ;    // 返回。
}int main() {scanf("%d", &n);work();return 0;
}

三、例题

P1657 选书

时间限制

1.00s

内存限制

125.00MB

题目描述

学校放寒假时，信息学奥赛辅导老师有1,2,3……x本书，要分给参加培训的x个人，每人只能选一本书，但是每人有两本喜欢的书。老师事先让每个人将自己喜欢的书填写在一张表上。然后根据他们填写的表来分配书本，希望设计一个程序帮助老师求出所有可能的分配方案，使每个学生都满意。

输入格式

第1行：一个数x

第2行~第1+x行：每行两个数，表示ai喜欢的书的序号

输出格式

只有一个数：总方案数total。

输入输出样例

输入 #1复制
5
1 3
4 5
2 5
1 4
3 5

输出 #1复制

2

说明/提示

所有数据：x<=20

（世界上最难出数据的题目，没有之一……）

分析

（本来是道深搜，被我写成了子集枚举）
首先分析题目，每个同学只有两本喜欢的书，可以看成两种情况。
思路见代码注释：

#include 
#include 
#include 
using namespace std;int n, U;
int book[25][3];
int judge[25];// 输入
void input() {scanf("%d", &n);for(int i = 0; i < n; i++)for(int j = 0; j < 2; j++)scanf("%d", &book[i][j]), book[i][j]--;U = 1 << n;// printf("%d", U);return ;
}/*
子集枚举思路：每一个人选两本书 a1, a2。 选 a1 记为 0 ，选 a2 记为 1 ，定义变量 U ，则 U-1 即为全集，范围为 
[0, U) 。操作 (U & (1 << i)) 即判断第 i 位同学选的是第 1 本还是第 2 本。值为 0 是第 1 本， 值不为 
0 是第 2 本。
*/// 子集枚举
void work(int U) {int ans = 0;int f = 1;for(int S = 0; S < U; S++) {f = 1;memset(judge, 0, sizeof(judge));for(int i = 0; i < n; i++)if(S & (1 << i))judge[book[i][1]]++;else judge[book[i][0]]++;for(int i = 0; i < n; i++)if(judge[i] != 1) {f = 0;break;}//     printf("%d: ", S);// for(int i = 0; i < n; i++)//     printf("%d ", judge[i]);// puts("");if(f) {ans++;// printf("%d\n", S);}}printf("%d\n", ans);
}int main() {input();if(n == 0) {printf("0");return 0;}work(U);return 0;
}

四、复杂度分析

子集枚举的时间复杂度是 O ( 2 n ) O(2^n) O(2n)， 所以对于数据太大的题目就束手无策了。一般要求 $n\le 20$。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！