OpenJudge百练-2443 Set Operation
题面
输入一个整数N表示N个集合
接下来N行每行先输入一个整数C表示某个集合的数字个数
然后输入C个整数表示这个集合的所有元素
接下来输入一个整数q
然后是q行
每行两个整数x y
判断x 与 y是否可以属于同一个集合
如果可以输出Yes否则输出No
N <= 1000, C <= 10000 , x, y <= 10000, Q <= 200000
总结
这题如果使用朴素的暴力，开一个f[a][b]=0/1 表示a元素是否属于b集合；对于每次询问x,y暴力枚举所有集合s判断f[x][s]与f[y][s]是否都为1，复杂度为 O(q \times N ) ,肯定会超时。
这时我们就要考虑一下用二进制来储存状态了，对于标记某个数是否存在可以充分利用一个整数
的所有二进制位，相应二进制位为0或者1来表示某个数是否存在。bitset可以用来封装相关操作。
AC代码
#include<bits/stdc++.h>
using namespace std;
bitset<1005> st[10005];
int n,q,x,y,c;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&c);
for(int j=1;j<=c;j++){
scanf("%d",&x);
st[x].set(i);
}
}
scanf("%d",&q);
while(q--){
scanf("%d%d",&x,&y);
printf("%s\n",((st[x]&st[y]).count()>0)?"Yes":"No");
}
}