【叉姐的魔法训练第一课_初级魔法练习】poj 2443 Set Operation ( bitset加速)

poj 2443题目链接

题意:给出n个可重集...以及集合中的元素。。。现在若干查询,每个查询给出一对数x,y,询问是否存在某个集合,同时拥有x,y两个元素(x,y可以相同)

思路:由于x,y最大时10000,容易想到对每一个元素开一个集合,记录这个元素出现的集合的标号,然后用 set_intersection 来做...

就是询问的时候交一下两个集合,看是否为空,结果Tle了。。。

正解其实也是这个思路,不过用到了bitset加速一下。因为我求集合相交的时候,并不需要知道交了以后的结果,只需要知道是否为空,那么我们不妨用bitset

对每个元素开一个bitset,每个bitset上,第i位为1表示,该元素在第i个集中中出现了。

求相交的时候,只需要两个bitset 位与一下,然后看结果中是否有1出现就好了。

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2016年11月17日 星期四 09时31分16秒
 4File Name :code/poj/2442.cpp
 5 ************************************************ */
 6#include <cstdio>
 7#include <cstring>
 8#include <iostream>
 9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#include <bitset>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27using namespace std;
28const double eps = 1E-8;
29const int dx4[4]={1,0,0,-1};
30const int dy4[4]={0,-1,1,0};
31const int inf = 0x3f3f3f3f;
32const int N=1E4+7;
33int n;
34set<int>se[N];
35bitset<1005>bse[N],tmp;
36set<int>myset;
37int main()
38{
39#ifndef  ONLINE_JUDGE 
40    freopen("code/in.txt","r",stdin);
41#endif
42    scanf("%d",&n);
43    for ( int i =1 ; i <= n ; i++)
44    {
45	int c;
46	scanf("%d",&c);
47	myset.clear();
48	while (c--)
49	{
50	    int x;
51	    scanf("%d",&x);
52	    bse[x].set(i);
53	}
54    }
55    int q;
56    scanf("%d",&q);
57    while (q--)
58    {
59	int x,y;
60	scanf("%d%d",&x,&y);
61	tmp = bse[x]&bse[y];
62	if (tmp.any()) puts("Yes");
63	else puts("No");
64    }
65#ifndef ONLINE_JUDGE  
66    fclose(stdin);
67#endif
68    return 0;
69}