枚举子集

亦凉 2021-11-11 20:48 273阅读 0赞

网易的一道面试题

读入一串操作，操作分两类。格式为1 x或 2 x。

当读入操作1时,将x压入集合A中。

当读入操作2时，查探是否有A的一个子集，将子集中的所有数做“或运算”的结果等于x，如果有则输出YES， 如果没有输出NO.

思想是当读入1的时候，将所有可能出现的情况全部记录下来；当读入2的时候，直接去查询现有的记录是否满足条件。

这里用到了如何枚举集合的子集的技巧。

枚举集合的子集的方法：[https://www.cnblogs.com/Emerald/p/4695672.html][https_www.cnblogs.com_Emerald_p_4695672.html]

//枚举s的子集
    for(int i=s;i;i=(i-1)&s){
      //具体操作
    }

答案参考：[https://www.nowcoder.com/discuss/216237][https_www.nowcoder.com_discuss_216237]

#include<bits/stdc++.h>
    using namespace std; 
    // 对于每一次询问，我们肯定会选择所有y，满足y&x==y，即在二进制表达下，y是x的子集。
    // 那么我们可以维护一个数组p[i]，表示所有为i的子集的数字的Or值是多少。
    // 每次插入一个数字，如果它没有重复出现过，就枚举它的超集更新答案。询问的时候只需要看p[x]是否等于x就好了。
    
    int p[131072] ;
    int mx = 131071 ;  //二进制(1111111111111)转化为十进制为131071 
    int q ;
    int main(){
        scanf("%d",&q) ;
        while(q--) {
            int op , x;
            scanf("%d%d",&op,&x) ;
            if(op == 1) {
                if(p[x] == x) continue ;
                int s = mx ^ x;  //对x取反    
                for(int i=s ; i ; i=(i-1)&s) {   //枚举s的子集 
                    p[i ^ x] = p[i ^ x] | x ;    //i^x 为集间差 
                }
                p[x] = x;
            }
            else {
                if(p[x] == x) puts("YES") ;
                else puts("NO");
            }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/liugl7/p/11303917.html

[https_www.cnblogs.com_Emerald_p_4695672.html]: https://www.cnblogs.com/Emerald/p/4695672.html
[https_www.nowcoder.com_discuss_216237]: https://www.nowcoder.com/discuss/216237