【叉姐的魔法训练第一课_初级魔法练习】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出现就好了。
/* ***********************************************
Author :111qqz
Created Time :2016年11月17日 星期四 09时31分16秒
File Name :code/poj/2442.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <bitset>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E4+7;
int n;
set<int>se[N];
bitset<1005>bse[N],tmp;
set<int>myset;
int main()
{
#ifndef ONLINE_JUDGE
freopen("code/in.txt","r",stdin);
#endif
scanf("%d",&n);
for ( int i =1 ; i <= n ; i++)
{
int c;
scanf("%d",&c);
myset.clear();
while (c--)
{
int x;
scanf("%d",&x);
bse[x].set(i);
}
}
int q;
scanf("%d",&q);
while (q--)
{
int x,y;
scanf("%d%d",&x,&y);
tmp = bse[x]&bse[y];
if (tmp.any()) puts("Yes");
else puts("No");
}
#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}