The number of set(位运算+状态dp)一道十分美妙的题目哦!!!!!!
2024-10-16 18:09:58
Given you n sets.All positive integers in sets are not less than 1 and not greater than m.If use these sets to combinate the new set,how many different new set you can get.The given sets can not be broken.
代码:
#include<bits/stdc++.h>
using namespace std;
int s[1<<15];//集合最大容量
int n,m,k,e;
//输入n个集合,每个集合的容量上限是m.
//集合元素 e
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
int ans=0;
memset(s,0,sizeof(s));
while(n--)
{
int set=0;
scanf("%d",&k);
//每个集合元素总数有k个
while(k--)
{
scanf("%d",&e);
//用一个二进制数保存一个集合的元素
set=set|(1<<(e-1));
}
//状态数组吧,我想!
s[set]=1; //(1<<14)
//借助于位运算合并集
for(int j=0;j<=(1<<14);j++)
{
if(s[j]) s[set|j]=1;
}
} for(int i=0;i<=1<<14;i++)
{
if(s[i]) ans++;
}
printf("%d\n",ans);
}
return 0;
}
赏析:
能力积累:
1.
int setval,size,element;//setval作为集合一一对应的特征值。
void f()
{
setval=;
scanf("%d",&size);
while(size--)
{
scanf("%d",&element);
setval=setval|(<<(element-));
}
cout<<setval<<endl;
}
参考:
https://www.cnblogs.com/lonelycatcher/archive/2011/05/27/2060158.html
最新文章
- My Demo Reels
- Windows下Eclipse+Scala+Spark开发环境搭建
- 《C#图解教程》读书笔记之四:类和继承
- java多线程(三)——锁机制synchronized(同步语句块)
- 基于@AspectJ和schema的aop(二)---@AspectJ基础语法
- COUNT(*),count(1),COUNT(ALL expression),COUNT(DISTINCT expression)
- 低电压锁定(UVLO) (转)
- intellij 打开node项目 一直停留在scanning files to index....,或跳出内存不够的提示框
- Java 通过Xml导出Excel文件,Java Excel 导出工具类,Java导出Excel工具类
- Linux安装java环境教程
- Python 爬虫基础知识
- ajax调用WebService实现数据库操作
- 448C - Painting Fence(分治)
- Leaf——美团点评分布式ID生成系统 UUID &; 类snowflake
- Access使用记录
- java 中的包概念
- 【C++】10.18日的C++笔记
- B类——Stas and the Queue at the Buffet
- JAVA基础部分复习(四、抽象类与接口)
- 类与对象 - Java学习(二)