【叉姐的魔法训练第一课_初级魔法练习】poj 2443 Set Operation ( bitset加速)
题意:给出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}