T2 题解

bitset大法吼啊

不难发现，如果询问的数的某一位为1，那么要找的数中的这一位也必须为1。所以要找的数中，每一个询问数中这一位为1的位都为1。

每一位开一个bitset，存有哪些数这一位为1。举个例子，对于样例 3 7 ，每一位的bitset应该长这样（最低位是第0位）：

bit[0]:11
bit[1]:11
bit[2]:01
bit[3]:00

询问时，将询问数中为1的位的bitset与起来，得到的bitset中存的数，满足这些位上均为1。那么只需要判断得到的bitset中是否为空即可。

例如，询问 4 ，4 的二进制表达是 100 ，取第2位的bitset，这个bitset的第2位为1，即第2个数 7 与 4 等于 4 ，输出 yes 。

询问 9 ，二进制表达是 1001 ，将第0位和第3位的bitset与起来得到 00 ，输出 no 。

Code:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <bitset>
#define Rint register int
#define INF 0x3f3f3f3f
using namespace std;
typedef long long lxl;
const int maxn=1e5+5;

template <typename T>
inline void read(T &x)
{
    x=0;T f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    x*=f;
}

int n,m;
bitset<maxn> bit[21],ans;

int main()
{
    read(n),read(m);
    for(int i=1,x;i<=n;++i)
    {
        read(x);
        for(int j=0;j<=20;++j)
            if(x&(1<<j))
                bit[j].set(i);
    }
    int x;
    while(m--)
    {
        read(x);
        ans.set();
        for(int i=0;i<=20;++i)
            if(x&(1<<i)) ans=ans&bit[i];
        puts(ans.any()?"yes":"no");
    }
    return 0;
}