刷题与ZZ错误记录14

OpenJudge百练-2443 Set Operation

题面

【VJudge】 【OpenJudge百练】

输入一个整数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");
    }
}

页面: 1 2 3 4 5 6 7

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注