首页 > 代码库 > [POJ 2443] Set Operation (bitset)
[POJ 2443] Set Operation (bitset)
题目链接：http://poj.org/problem?id=2443
题目大意：给你N个集合，每个集合里有若干个数。M个查询，每个查询有a，b两个数。问是否存在一个集合同时包含a，b这两个数。若存在则输出Yes，否则为No。
康神竟然一下子就想出来了。。
思路：统计每个数在哪个集合出现过，用bitset记录下来。然后对于a，b，则把两个bitset取与。
如果得到空集就是No，否则就是Yes。
1 #include <cstdio> 2 #include <bitset> 3 #include <algorithm> 4 #include <cstdlib> 5 #include <iostream> 6 7 using namespace std; 8 9 const int MAX_N = 222222;10 int N;11 bitset<1111> bs[MAX_N];12 13 int main(){14 while(scanf("%d",&N)!=EOF){15 for(int i=0;i<MAX_N;i++) bs[i].reset();16 for(int i=0;i<N;i++){17 int a,an;18 scanf("%d",&an);19 while( an-- ){20 scanf("%d",&a);21 bs[a].set(i);22 }23 }24 int M;25 scanf("%d",&M);26 while(M--){27 int a,b;28 scanf("%d%d",&a,&b);29 bitset<1111> t = bs[a]&bs[b];30 if( t.count() ){31 puts("Yes");32 } else {33 puts("No");34 }35 }36 }37 38 return 0;39 }
[POJ 2443] Set Operation (bitset)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。