POJ2443 Set Operation —— bitset
2024-08-24 15:41:27
题目链接:https://vjudge.net/problem/POJ-2443
Set Operation
Time Limit: 3000MS | Memory Limit: 65536K | |
Total Submissions: 3554 | Accepted: 1477 |
Description
You are given N sets, the i-th set (represent by S(i)) have C(i) element (Here "set" isn't entirely the same as the "set" defined in mathematics, and a set may contain two same element). Every element in a set is represented by a positive number from 1 to 10000. Now there are some queries need to answer. A query is to determine whether two given elements i and j belong to at least one set at the same time. In another word, you should determine if there exist a number k (1 <= k <= N) such that element i belongs to S(k) and element j also belong to S(k).
Input
First line of input contains an integer N (1 <= N <= 1000), which represents the amount of sets. Then follow N lines. Each starts with a number C(i) (1 <= C(i) <= 10000), and then C(i) numbers, which are separated with a space, follow to give the element in the set (these C(i) numbers needn't be different from each other). The N + 2 line contains a number Q (1 <= Q <= 200000), representing the number of queries. Then follow Q lines. Each contains a pair of number i and j (1 <= i, j <= 10000, and i may equal to j), which describe the elements need to be answer.
Output
For each query, in a single line, if there exist such a number k, print "Yes"; otherwise print "No".
Sample Input
3
3 1 2 3
3 1 2 5
1 10
4
1 3
1 5
3 5
1 10
Sample Output
Yes
Yes
No
No
Hint
The input may be large, and the I/O functions (cin/cout) of C++ language may be a little too slow for this problem.
Source
POJ Monthly,Minkerui
题意:
给出n个集合,每个集合有若干个数。有m个询问,问x、y是否存在于同一个集合中。
题解:
C++ bitset的应用。
具体介绍:https://blog.csdn.net/qll125596718/article/details/6901935
成员函数 | 函数功能 |
---|---|
bs.any() | 是否存在值为1的二进制位 |
bs.none() | 是否不存在值为1的二进制位 或者说是否全部位为0 |
bs.size() | 位长,也即是非模板参数值 |
bs.count() | 值为1的个数 |
bs.test(pos) | 测试pos处的二进制位是否为1 与0做或运算 |
bs.set() | 全部位置1 |
bs.set(pos) | pos位处的二进制位置1 与1做或运算 |
bs.reset() | 全部位置0 |
bs.reset(pos) | pos位处的二进制位置0 与0做或运算 |
bs.flip() | 全部位逐位取反 |
bs.flip(pos) | pos处的二进制位取反 |
bs.to_ulong() | 将二进制转换为unsigned long输出 |
bs.to_string() | 将二进制转换为字符串输出 |
~bs | 按位取反 效果等效为bs.flip() |
os << b | 将二进制位输出到os流 小值在右,大值在左 |
代码如下:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
#include <bitset> //bitset头文件
using namespace std;
typedef long long LL;
const double EPS = 1e-;
const int INF = 2e9;
const LL LNF = 2e18;
const int MAXN = 1e5+; bitset<>a[];
int main()
{
int n;
while(scanf("%d", &n)!=EOF)
{
for(int i = ; i<; i++)
a[i].reset();
for(int i = ; i<=n; i++)
{
int m, x;
scanf("%d", &m);
while(m--)
{
scanf("%d", &x);
a[x][i] = ;
}
} int m, x, y;
scanf("%d", &m);
while(m--)
{
scanf("%d%d", &x,&y);
if((a[x]&a[y]).count()) puts("Yes");
else puts("No");
}
}
}
最新文章
- Python之路,day8-Python基础
- 网站跨站点单点登录实现--cookie
- Hadoop第12周练习—HBase安装部署
- Javascript基础系列之(七)函数(定义和调运函数)
- TCP/IP与UDP区别
- powerdesigner设置唯一键,但不是主键的方式
- Sqlserver查询表结构信息-字段说明、类型、长度等信息
- LVS-DR模式(原理图详解)
- 依赖注入[7]: .NET Core DI框架[服务注册]
- SQLServer之索引简介
- 层居中绝对定位的div的居中方法,下面的写法兼容IE系列浏览器和火狐浏览器
- EMQTT本地源码搭建填坑记录
- 解题(ConflictPhoneNumber--冲突的电话号码)
- Jenkins Installing and migration
- Confluence 6 临时目录(安装目录)
- Redis密码设置与访问限制
- 转载-js如何设置网页横屏和竖屏切换
- java 环境搭建
- Java编程的逻辑 (20) - 为什么要有抽象类?
- 使用Synchronized块同步方法
热门文章
- 深入Java----集合----BitSet
- 谈 API 的撰写 - 子系统
- TCP/IP详解 卷一(第四、五章 ARP、RARP)
- jquery 创建jquery的dom对象---------------获取自身的html节点及其子节点的html
- Windows:小技巧
- ck-reset css(2016/5/13)
- canvas drawImage方法不显示图片的解决方案
- CISCO Configuration Examples and TechNotes
- linux uart驱动&mdash;&mdash;相关数据结构以及API(二)
- 关于海康视频采集卡的简介---基于pci的插潮采集卡