hdu 3006 枚举集合可以产生的所有并集的集合

2024-05-28 04:38

本文主要是介绍hdu 3006 枚举集合可以产生的所有并集的集合,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

http://acm.hdu.edu.cn/showproblem.php?pid=3006

刚买的CHERRY键盘 手感真好 可惜不习惯 写代码老是打错,一个题写了一上午,都是各种按错键DEBUG.....

开始想的是DFS  发现好像不行

然后想的是两重循环可以枚举所有的2个集合的并集,3重循环可以枚举所有3个集合的并集,那么n个子集貌似需要n重循环,NP问题啊,,,,,

做法还是从小的数去模拟,因为只有14个,所以状压存储

如第一个例子

四个子集1,2,3,4

二进制0001 0010 0011 0100

第一个与其他三个或操作  得到0001 0010 0011 0100 0011  0101....

然后第二个数和新的数异或

代码中第二重循环 i+1开始,放重复,其实省不了多少时间 o(╯□╰)o

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <queue>
using namespace std;#define IN(s) freopen(s,"r",stdin)
#define CL(a,b) memset(a,b,sizeof(a))const int MAXN = 1<<15;
int vis[MAXN],ans[MAXN];int main()
{//IN("hdu3006.txt");int n,m;int k;while(~scanf("%d%d",&n,&m)){CL(vis,0);int cnt=0;for(int j=0;j<n;j++){scanf("%d",&k);int t=0,a=0;for(int i=0;i<k;i++){scanf("%d",&t);a|=1<<(t-1);}if(!vis[a]){vis[a]=1;ans[cnt++]=a;}}int ct=cnt;for(int i=0;i<ct;i++){int s=ans[i];for(int j=i+1;j<cnt;j++){if(!vis[(s|ans[j])] && i!=j){vis[s|ans[j]]=1;ans[cnt++]=s|ans[j];}}}printf("%d\n",cnt);}return 0;
}



这篇关于hdu 3006 枚举集合可以产生的所有并集的集合的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1009563

相关文章

Java枚举类实现Key-Value映射的多种实现方式

《Java枚举类实现Key-Value映射的多种实现方式》在Java开发中,枚举(Enum)是一种特殊的类,本文将详细介绍Java枚举类实现key-value映射的多种方式,有需要的小伙伴可以根据需要... 目录前言一、基础实现方式1.1 为枚举添加属性和构造方法二、http://www.cppcns.co

Python实现将MySQL中所有表的数据都导出为CSV文件并压缩

《Python实现将MySQL中所有表的数据都导出为CSV文件并压缩》这篇文章主要为大家详细介绍了如何使用Python将MySQL数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到... python将mysql数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到另一个

利用Go语言开发文件操作工具轻松处理所有文件

《利用Go语言开发文件操作工具轻松处理所有文件》在后端开发中,文件操作是一个非常常见但又容易出错的场景,本文小编要向大家介绍一个强大的Go语言文件操作工具库,它能帮你轻松处理各种文件操作场景... 目录为什么需要这个工具?核心功能详解1. 文件/目录存javascript在性检查2. 批量创建目录3. 文件

Python容器类型之列表/字典/元组/集合方式

《Python容器类型之列表/字典/元组/集合方式》:本文主要介绍Python容器类型之列表/字典/元组/集合方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 列表(List) - 有序可变序列1.1 基本特性1.2 核心操作1.3 应用场景2. 字典(D

java两个List的交集,并集方式

《java两个List的交集,并集方式》文章主要介绍了Java中两个List的交集和并集的处理方法,推荐使用Apache的CollectionUtils工具类,因为它简单且不会改变原有集合,同时,文章... 目录Java两个List的交集,并集方法一方法二方法三总结java两个List的交集,并集方法一

Java集合中的List超详细讲解

《Java集合中的List超详细讲解》本文详细介绍了Java集合框架中的List接口,包括其在集合中的位置、继承体系、常用操作和代码示例,以及不同实现类(如ArrayList、LinkedList和V... 目录一,List的继承体系二,List的常用操作及代码示例1,创建List实例2,增加元素3,访问元

使用Navicat工具比对两个数据库所有表结构的差异案例详解

《使用Navicat工具比对两个数据库所有表结构的差异案例详解》:本文主要介绍如何使用Navicat工具对比两个数据库test_old和test_new,并生成相应的DDLSQL语句,以便将te... 目录概要案例一、如图两个数据库test_old和test_new进行比较:二、开始比较总结概要公司存在多

C#比较两个List集合内容是否相同的几种方法

《C#比较两个List集合内容是否相同的几种方法》本文详细介绍了在C#中比较两个List集合内容是否相同的方法,包括非自定义类和自定义类的元素比较,对于非自定义类,可以使用SequenceEqual、... 目录 一、非自定义类的元素比较1. 使用 SequenceEqual 方法(顺序和内容都相等)2.

在MyBatis的XML映射文件中<trim>元素所有场景下的完整使用示例代码

《在MyBatis的XML映射文件中<trim>元素所有场景下的完整使用示例代码》在MyBatis的XML映射文件中,trim元素用于动态添加SQL语句的一部分,处理前缀、后缀及多余的逗号或连接符,示... 在MyBATis的XML映射文件中,<trim>元素用于动态地添加SQL语句的一部分,例如SET或W

C#实现获得某个枚举的所有名称

《C#实现获得某个枚举的所有名称》这篇文章主要为大家详细介绍了C#如何实现获得某个枚举的所有名称,文中的示例代码讲解详细,具有一定的借鉴价值,有需要的小伙伴可以参考一下... C#中获得某个枚举的所有名称using System;using System.Collections.Generic;usi