<bitsit>算法

< bitset >头文件
bitset是用来存放bit位元素的，由于每个元素(0或1)只占1bit位，因而可以节约空间（相比于8bit位的bool型变量）。在c++ stl中，提供了操作位的容器，使用前包含< bitset >头文件即可。

相关操作

创建bitset对象

如bitset<100> b,它能容纳100位比特位，每位上的初始值为0
注意：bitset的大小在定义时确定，定义后不能修改
同样，位运算符 & | ^ ~ << 也适用于bitset

常用以上操作来做集合运算，以减少时间常数

输出元素

逐个输出，采用下标法：cout<< b[i];
整体输出，即全部输出:cout<< b;

例题：bzoj 3687
题意：给出n，然后接下来n个数，求这n个数的子集的和的异或
【样例输入】
2
1 3
【样例输出】
6
【样例解释】
6 = 1 ⊗ 3 ⊗ (1 + 3)
思路：很巧妙的应用。
bs[i] 表示用这n个数能够组成的和为i的方案数的奇偶(奇数次为1，偶数次为0)
每次加入一个数字x，就相当于bs中所有存在1的位置都会再加一次x，所以整体往左移位x个，然后再和原来的bs异或。 脑补一下就可以知道。
代码 很简单

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2000000+11;
bitset<maxn>bs;
int main(){
    int n;scanf("%d",&n);
    bs[0]=1; int sum=0;
    for(int i=0;i<n;i++){
        int a;scanf("%d",&a);
        bs^=(bs<<a);
        sum+=a;
    }
    int ans=0;
    for(int i=1;i<=sum;i++){
        if(bs[i])
            ans^=i;
    }
    printf("%d\n",ans);
return 0;
}

牛客例题：

有n个长度为m的文本串，每个串只含有’0’和’1’。接下来有Q次询问，每次给出一个长度为m的字符串，且只含有’0’,‘1’和’’。如10_1_1。下划线可以匹配’0’或’1’。即10_1_1可以匹配101111,101101,100111,100101四种串。每次询问求出n个文本串中有多少个可以与当前询问的串匹配。
输入描述:
第一行输入n,m
接下来n行，每行输入一个长度为m的01串表示一个文本串。
第n+2行输入Q
接下来Q行，每行输入一个长度为m的字符串(只包含’0’,‘1’,’’)。
1<=n,m<=1000,1<=Q<=3000。
输出描述:
对于每次询问，输出n个文本串中有多少个与当前询问的串匹配。
示例1
输入
复制
5 6
101101
011011
100110
111000
101111
2
1011_1
1__1__
输出
复制
2
3
说明
第一次询问：有101101，101111与1011_1匹配
第二次询问：有101101, 100110, 101111与1__1__匹配

#include<bits/stdc++.h>
using namespace std;

const int maxn = 3000+11;
bitset<maxn>bs[maxn],p,q;
char s[maxn][maxn];
int main()
{

    int n,m;
    scanf("%d%d",&n,&m);
    for(int a=1;a<=n;a++)
    {
        scanf("%s",s[a]);
        for(int b=0;b<m;b++)
        {
            bs[a][b]=s[a][b]-'0';
        }
    }
    int t;
    scanf("%d",&t);
    while(t--)
    {
        char v[maxn];
        scanf("%s",v);
        for(int a=0;a<m;a++)
        {
            if(v[a]=='1')
            {
                p[a]=0;
                q[a]=1;
            }
            else if(v[a]=='0')
            {
                p[a]=0;
                q[a]=0;
            }
            else
            {
                p[a]=1;
                q[a]=1;
            }
        }
        int ant=0;
        for(int a=1;a<=n;a++)
        {
            if((p | bs[a])==q)
                ant++;
        }
        printf("%d\n",ant);
    }
    return 0;
}