九、并查集
核心模板
朴素并查集：
路径压缩：查找时，如果还没有找到目标值的父结点时，将路径上每个点的父结点，在向上寻找过程中更新记录。
int p[N];//存储每个点的祖宗结点 //返回x的祖宗结点 int find(int x){ if(p[x]!=x) p[x]=find(p[x]); return p[x]; } //初始化，假定结点编号是1~n for(int i=1;i<=n;i++){ p[i]=i; } //合并a和b所在的两个集合 p[find(a)]=find(b); 1
维护size的并查集
//注意size可能与某些内置变量名冲突,故改成了num
int p[N],num[N];
//p[]存储每个结点的祖宗结点，num[]只有祖宗结点有意义，表示祖宗结点所在集合中点的数量
//返回x的祖宗结点
int find(int x){ if(p[x]!=x) p[x]=find(p[x]); return p[x]; } //初始化，假定结点编号是1~n for(int i=1;i<=n;i++){ p[i]=i; num[i]=1; } //合并a和b所在的两个集合 num[find(b)]+=num[find(a)]; p[find(a)]=find(b);
维护到祖宗结点距离的并查集
int p[N],d[N]; //p[]存储每个结点的祖宗结点，d[x]存储x到p[x]的距离 //返回x的祖宗结点 int find(int x){ if(p[x]!=x){ int u=find(p[x]); d[x]+=d[p[x]]; p[x]=u; } return p[x]; } //初始化，假定结点编号是1~n for(int i=1;i<=n;i++){ p[i]=i; d[i]=0; } //合并a和b所在的两个集合 p[find(a)]=find(b); d[find(a)]=distance;//根据具体问题，初始化find(a)的偏移量
题目一
题目链接：836. 合并集合
9.1题目描述
一共有 n 个数，编号是 1∼n，最开始每个数各自在一个集合中。
现在要进行 m 个操作，操作共有两种：
M a b，将编号为 a 和 b 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
Q a b，询问编号为 a 和 b 的两个数是否在同一个集合中；
输入格式
第一行输入整数 n 和 m。
接下来 m 行，每行包含一个操作指令，指令为 M a b 或 Q a b 中的一种。
输出格式
对于每个询问指令 Q a b，都要输出一个结果，如果 a 和 b 在同一集合内，则输出 Yes，否则输出 No。
每个结果占一行。
数据范围
1≤n,m≤105
输入样例：
4 5 M 1 2 M 3 4 Q 1 2 Q 1 3 Q 3 4
输出样例：
Yes No Yes 1
9.2思路分析
套用模板即可，注意细节。
9.3代码实现
#include <iostream> using namespace std; const int N=100010; int n,m; int p[N]; //存储每个结点的父结点 //返回祖宗结点+路径压缩 int find(int x){ //如果x的父结点不是根结点，就向上走一层，看x的父结点的父结点是否是根结点，直至查找到祖宗结点（根结点） ，递归返回过程中将该路径上的结点的父结点都更新成了根结点，起到了路径压缩的作用 if(p[x]!=x) p[x]=find(p[x]); return p[x]; //返回x的父结点 } int main(){ cin>>n>>m; //并查集初始化 ，每个结点的父结点为自己， for(int i=1;i<=n;i++){ p[i]=i; } char op; int a,b; while(m--){ cin>>op>>a>>b; if(op=='M') p[find(a)]=find(b); //将a的根结点的父结点设为b的根结点 else{ if(find(a)==find(b)) cout<<"Yes"<<endl; else cout<<"No"<<endl; } } return 0; }
题目二
题目链接：837. 连通块中点的数量
9.1题目描述
给定一个包含 n 个点（编号为 1∼n）的无向图，初始时图中没有边。
现在要进行 m 个操作，操作共有三种：
C a b，在点 a 和点 b 之间连一条边，a 和 b 可能相等；
Q1 a b，询问点 a 和点 b 是否在同一个连通块中，a 和 b 可能相等；
Q2 a，询问点 a 所在连通块中点的数量；
输入格式
第一行输入整数 n 和 m。
接下来 m 行，每行包含一个操作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。
输出格式
对于每个询问指令 Q1 a b，如果 a 和 b 在同一个连通块中，则输出 Yes，否则输出 No。
对于每个询问指令 Q2 a，输出一个整数表示点 a 所在连通块中点的数量
每个结果占一行。
数据范围
1≤n,m≤105
输入样例：
5 5 C 1 2 Q1 1 2 Q2 1 C 2 5 Q2 5
输出样例：
Yes 2 3
9.2思路分析
套用模板即可，注意细节。
9.3代码实现
#include <iostream> using namespace std; const int N=100010; int n,m; int p[N],num[N]; //p[]存储每个结点的父结点，num[]存储祖宗结点所在集合中结点个数（只有祖宗结点的num有意义） int find(int x){ //如果x的父结点不是根结点，就向上走一层，看x的父结点的父结点是否是根结点，直至查找到祖宗结点（根结点） ，递归返回过程中将该路径上的结点的父结点都更新成了根结点，起到了路径压缩的作用 if(p[x]!=x) p[x]=find(p[x]); return p[x]; //返回x的父结点 } int main(){ cin>>n>>m; //并查集初始化，每个结点的父结点为自己，每个根结点所在集合中结点数量为1 for(int i=1;i<=n;i++){ p[i]=i; num[i]=1; } char op[5]; int a,b; while(m--){ cin>>op; if(op[0]=='C') { cin>>a>>b; if(find(a)!=find(b)){ //如果a、b不在一个集合中，将a所在集合中的元素数量累加进b所在集合中的元素数量中去 num[find(b)]+=num[find(a)]; } p[find(a)]=find(b); //将a的根结点的父结点设为b的根结点 } else if(op[1]=='1'){ cin>>a>>b; if(find(a)==find(b)) cout<<"Yes"<<endl; else cout<<"No"<<endl; } else{ cin>>a; cout<<num[find(a)]<<endl; } } return 0; }
十、堆
堆（STL中优先队列）是一棵 完全二叉树
小根堆：每个结点的值都小于其左右儿子的值。
下标从1开始，若从0开始会造成冲突。
down和up操作时间复杂度 O(logn)。down和up操作均是对对应下标的值进行操作，并不是对下标进行down、up操作
down操作：每次与其左右儿子比较，如果比左或右儿子大，则将其中较小的交换，使其满足堆定义，否则，不交换，完成down操作。
up操作：每次与其父结点比较，若比父结点小，则交换，使其满足堆定义，否则不交换，意味着完成up操作。
建堆操作：从n/2开始，依次从下层往上层每个结点进行down操作，先完成子结点的建堆，再完成父结点的建堆，直到完成所有元素的down操作，建堆完成。
核心模板
//h[N]存储堆中的值，h[1]是堆顶，x的左儿子是2x，右儿子是2x+1 //ph[k]存储第k个插入的点在堆中的位置 //hp[k]存储堆中下标是k的点是第几个插入的 //num代表堆中点的数量 int h[N],ph[N],hp[k],num; //交换两个点及其映射关系 void heap_swap(int a,int b){ swap(ph[hp[a]],ph[hp[b]]); swap(hp[a],hp[b]); swap(h[a],h[b]); } void down(int u){ int t=u; if(u*2<=num&&h[u*2]<h[t]) t=u*2; if(u*2+1<=num&&h[u*2+1]<h[t]) t=u*2+1; if(u!=t){ heap_swap(u,t); down(t); } } void up(int u){ while(u/2&&h[u]<h[u/2]){ heap_swap(u,u/2); u>>=1; } } //O(n)建堆 for(int i=n/2;i;i--) down(i);
题目一
题目链接：838. 堆排序
10.1题目描述
输入一个长度为 n 的整数数列，从小到大输出前 m 小的数。
输入格式
第一行包含整数 n 和 m。
第二行包含 n 个整数，表示整数数列。
输出格式
共一行，包含 m 个整数，表示整数数列中前 m 小的数。
数据范围
1≤m≤n≤105 ，1≤数列中元素≤109
输入样例：
5 3 4 5 1 3 2
输出样例：
1 2 3
10.2思路分析
套用模板即可，注意细节。
10.3代码实现
#include <iostream> using namespace std; const int N=100010; int n,m; int h[N],num; //h[]存储结点的值，num存储结点个数 void down(int u){ int t=u; //t存储该结点及其左右儿子中的最小值的结点编号 if(u*2<=num&&h[u*2]<h[t]) t=u*2; //如果左儿子存在，且比该结点值小，更新t为左儿子 if(u*2+1<=num&&h[u*2+1]<h[t]) t=u*2+1; //如果右儿子也存在，且比该结点和其左儿子值小，更新t为右儿子 //如果该结点不是最小值 if(u!=t){ swap(h[u],h[t]); //将该结点换成其左右儿子中最小值 down(t); //将该结点（编号已经是t，h[t]存储该结点的值）继续与下面的点比较进行down操作 } } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>h[i]; } num=n; //建堆 for(int i=n/2;i;i--) down(i); while(m--){ cout<<h[1]<<' '; //删除堆顶元素 h[1]=h[num]; //用最后一个元素将堆顶元素覆盖 num--; //堆中元素个数-1 down(1); //对堆顶元素使用down操作 } return 0; }
题目二
题目链接：839. 模拟堆
10.1题目描述
维护一个集合，初始时集合为空，支持如下几种操作：
I x，插入一个数 x；
PM，输出当前集合中的最小值；
DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；
D k，删除第 k 个插入的数；
C k x，修改第 k 个插入的数，将其变为 x；
现在要进行 N 次操作，对于所有第 2 个操作，输出当前集合的最小值。
输入格式
第一行包含整数 N。
接下来 N 行，每行包含一个操作指令，操作指令为 I x，PM，DM，D k 或 C k x 中的一种。
输出格式
对于每个输出指令 PM，输出一个结果，表示当前集合中的最小值。
每个结果占一行。
数据范围
1≤N≤105
−109≤x≤109
数据保证合法。
输入样例：
8 I -10 PM I -10 D 1 C 2 8 I 6 PM DM
输出样例：
-10 6
10.2思路分析
套用模板即可，注意细节。
10.3代码实现
#include <iostream> using namespace std; const int N=100010; int n,m; int h[N],num; //h[]存储结点的值，num存储结点个数 int ph[N],hp[N]; //ph[k]存储第k个插入的点的下标，hp[k]存储下标为k的点是第几个插入的 void heap_swap(int a,int b){ swap(ph[hp[a]],ph[hp[b]]); //交换a、b swap(hp[a],hp[b]); //交换a、b的插入数（第几个插入） swap(h[a],h[b]); //交换两点的值 } void down(int u){ int t=u; //t存储该结点及其左右儿子中的最小值的结点编号 if(u*2<=num&&h[u*2]<h[t]) t=u*2; //如果左儿子存在，且比该结点值小，更新t为左儿子 if(u*2+1<=num&&h[u*2+1]<h[t]) t=u*2+1; //如果右儿子也存在，且比该结点和其左儿子值小，更新t为右儿子 //如果该结点不是最小值 if(u!=t){ heap_swap(u,t); //将该结点换成其左右儿子中最小值的结点交换 down(t); //将该结点（编号已经是t）down操作 } } void up(int u){ //如果该结点存在父结点，且父结点比该结点值大 while(u/2&&h[u/2]>h[u]){ heap_swap(u/2,u); //将该结点和其父结点交换 u/=2; //该结点更新为其父结点，继续向上比较 } } int main(){ cin>>n; while(n--){ char op[2]; int k,x; cin>>op; if(op[0]=='I'){ cin>>x; num++; //堆中元素数量+1 m++; //m代表第几个插入的数 ph[m]=num; //第m个插入的点的下标是num hp[num]=m; //下标是num的元素是第m个插入的 h[num]=x; //下标是num的点的值是x up(num); //对新插入的元素进行up操作 } else if(op[0]=='P'){ cout<<h[1]<<endl; //输出堆中最小值 } else if(op[0]=='D'&&op[1]=='M'){ heap_swap(1,num); //用最后一个元素与堆顶元素交换 num--; //堆中元素个数-1 down(1); //对堆顶元素使用down操作 } else if(op[0]=='D'){ cin>>k; k=ph[k]; //k记录需要down或up操作的点的下标 heap_swap(k,num); //用最后一个元素与下标为k的元素交换 num--; //堆中元素个数-1,即第k个插入的点从堆中删除 down(k),up(k); //down和up只会走一个：如果此时k比其左右儿子值大，执行down操作，否则，执行up操作 } else{ cin>>k>>x; k=ph[k]; //让k等于第k个插入点的下标 h[k]=x; //修改下标为k的结点的值为x down(k),up(k); //down和up只会走一个：如果此时k比其左右儿子值大，执行down操作，否则，执行up操作 } } return 0; }
注意：删除操作不能这样写。
else if(op[0]=='D'){ cin>>k; heap_swap(ph[k],num); //这行可以这样写 num--; down(ph[k]),up(ph[k]); //这行不可以，因为ph[k]的值已经在heap_swap()时改成了num，即指向的点的下标是num，而heap_swap()同时也将下标为num的点的值改成了第k个插入的点的值，而这个值已经被删除了，我们应该要down或up的是最后一个点（即与第k个点交换的那个点）。 }
原因：首先要弄清楚，我们的目的是让第k个插入的点与最后一个点交换（包括值交换，ph[]、hp[]数组的交换）,然后把交换后的最后一个点删除（这时最后一个点的值已经是第k个插入的点的值了），所以只需要把堆大小-1就将“原插入的第k个点”删掉了，然后我们就需要来处理交换后的第k个插入的点，此时ph[k]存储的是最后一个插入的点的下标，而这个点的值我们由于也进行了值交换操作，这个点的值其实是存储的是第k个插入的点的值，而我们已经通过num–,来把这个点给删掉了，所以直接进行down()、up()操作就会导致错误。我们需要down()或up()的点是原来最后一个点所代表的值，也就是现在第k个插入的点的下标元素中存储的值。所以我们需要提前将这个下标来存储下来(如果不记录，要通过num来进行down()和up()操作，也会导致错误，因为num的值-1了，堆中元素已经把这个点删了，最大堆元素下标也只是num-1，所以在down()或up()操作中，也会造成错误)，以便后续down()或up()操作。
帮助理解：
下图为算法基础课微信群中好兄弟分享的，帮助理解，如有侵权，立即删除。
十一、一般哈希
哈希：将较大范围的数映射到小范围区间内。
取模的数一般取成质数，且离2的次幂尽可能远。
拉链法：哈希值相同的，找对应位置，在对应位置的链表中插入该元素。
开放寻址法:哈希值相同的，找对应位置，如果该位置不空，依次向后寻找，直到找到空位即可。
取模的数开到题目数据范围的2~3倍。
memset按字节赋值，最常使用0和-1来memset初始化
下图作者如图，来自AcWing官网，如有侵权，立即删除。
核心模板
拉链法
int h[N],e[N],ne[N],idx; //向哈希表中插入一个数 void insert(int x){ int k=(x%N+N)%N; //N取大于区间范围的最小质数 e[idx]=x; ne[idx]=h[k]; h[k]=idx++; } //在哈希表中查询某个数是否存在 bool find(int x){ int k=(x%N+N)%N; for(int i=h[k];i!=-1;i=ne[i]){ if(e[i]==x){ return true; } } return false; }
开放寻址法
int h[N]; //如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置 int find(int x){ int t=(x%N+N)%N; while(h[t]!=null&&h[t]!=x){ t++; if(t==N) t=0; } return t; }
题目链接：840. 模拟散列表
11.1题目描述
维护一个集合，支持如下几种操作：
I x，插入一个数 x；
Q x，询问数 x 是否在集合中出现过；
现在要进行 N 次操作，对于每个询问操作输出对应的结果。
输入格式
第一行包含整数 N，表示操作数量。
接下来 N 行，每行包含一个操作指令，操作指令为 I x，Q x 中的一种。
输出格式
对于每个询问指令 Q x，输出一个询问结果，如果 x 在集合中出现过，则输出 Yes，否则输出 No。
每个结果占一行。
数据范围
1≤N≤105
−109≤x≤109
输入样例：
5 I 1 I 2 I 3 Q 2 Q 5
输出样例：
Yes
11.2思路分析
套用模板即可，注意细节。
11.3代码实现
拉链法：
#include <iostream> #include <cstring> using namespace std; const int N=100003; int h[N],e[N],ne[N],idx; //与单链表定义类似，h[]存储每个链的头结点，e[]存储每个结点的值，ne[]存储每个结点的next指针，idx代表结点编号 void insert(int x){ int k=(x%N+N)%N; //k为哈希值，先%再多+N再%N的目的：将x%N的结果为负数的转成正数 //单链表插入操作 e[idx]=x; ne[idx]=h[k]; h[k]=idx++; } bool find(int x){ int k=(x%N+N)%N; //与上同 //单链表查找操作 for(int i=h[k];i!=-1;i=ne[i]){ if(e[i]==x){ return true; } } return false; } int main(){ int n; cin>>n; memset(h,-1,sizeof h); char op; int x; while(n--){ cin>>op>>x; if(op=='I'){ insert(x); } else{ if(find(x)) cout<<"Yes"<<endl; else cout<<"No"<<endl; } } ret
开放寻址法：
#include <iostream> #include <cstring> using namespace std; const int N=200003,null=0x3f3f3f3f; //null赋值为不在题目区间内的数 int h[N]; //h[]数组为哈希表 int find(int x){ int k=(x%N+N)%N; //与上种方法同 //如果x应该存储的位置不空 while(h[k]!=null&&h[k]!=x){ k++; //向后寻找位置 //如果已经找到表尾，再从表头开始找 if(k==N) k=0; } return k; //如果x在表中返回其位置，如果x不在表中返回其应该存储的位置 } int main(){ int n; cin>>n; memset(h,0x3f,sizeof h); //memset按字节赋值，h为整型，4字节，则将每个字节赋值成了0x3f,即0x3f3f3f3f char op; int x; while(n--){ cin>>op>>x; int k=find(x); //找到x应该存储的位置 if(op=='I'){ h[k]=x; //插入x } else{ //如果x应该存储的位置不空，输出Yes,否则输出No if(h[k]!=null) cout<<"Yes"<<endl; else cout<<"No"<<endl; } } return 0; }
十二、字符串哈希
h[l-1]存储1到l-1位置子串的哈希值(子串下标从1开始)，h[r]存储1到r位置子串的哈希值，要求l到r位置的哈希值：因1到l-1位置在h[l-1]和h[r]中计算哈希值时所乘权重不同(前者计算时l-1位置的权重是P0，而后者计算时r位置的权重是P0)，所以要在h[r]中减去1到l-1位置的哈希值时，需要先将前l-1位置转换成在前r位置中计算时应该得到的数值(让h[l-1]乘上两者相差权重)，然后再用h[r]去减去该数值。
核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低。
小技巧：取模的数用264,这样直接用unsigned long long存储，溢出的结果就是取模的结果。
核心模板
typedef unsigned long long ULL; ULL h[N],p[N];//h[k]存储字符串前k个字母的哈希值，p[k]存储P^kmod2^64 //初始化 p[0]=1; for(int i=1;i<=n;i++){ h[i]=h[i-1]*P+str[i]; p[i]=p[i-1]*P; } //计算子串str[l~r]的哈希值 ULL get(int l,int r){ return h[r]-h[l-1]*p[r-l+1]; }
题目链接：841. 字符串哈希
12.1题目描述
给定一个长度为 n 的字符串，再给定 m 个询问，每个询问包含四个整数 l1,r1,l2,r2，请你判断 [l1,r1] 和 [l2,r2] 这两个区间所包含的字符串子串是否完全相同。
字符串中只包含大小写英文字母和数字。
输入格式
第一行包含整数 n 和 m，表示字符串长度和询问次数。
第二行包含一个长度为 n 的字符串，字符串中只包含大小写英文字母和数字。
接下来 m 行，每行包含四个整数 l1,r1,l2,r2 ，表示一次询问所涉及的两个区间。
注意，字符串的位置从 1 开始编号。
输出格式
对于每个询问输出一个结果，如果两个字符串子串完全相同则输出 Yes，否则输出 No。
每个结果占一行。
数据范围
1≤n,m≤105
输入样例：
8 3 aabbaabb 1 3 5 7 1 3 6 8 1 2 1 2
输出样例：
Yes No Yes
12.2思路分析
套用模板即可，注意细节。
12.3代码实现
#include <iostream> using namespace std; typedef unsigned long long ULL; const int N=100010,P=131; int n,m; char str[N]; ULL h[N],p[N]; //h[i]存储前i个字母的哈希值，p[i]存储P^i%2^64的值 //计算从l到r位置子串的哈希值 ULL get(int l,int r){ return h[r]-h[l-1]*p[r-l+1]; } int main(){ cin>>n>>m>>str+1; p[0]=1; //初始化h[]和p[] for(int i=1;i<=n;i++){ p[i]=p[i-1]*P; h[i]=h[i-1]*P+str[i]; //P进制数，从前往后是从高位到低位，所以每一位的权重都比其后面一位的权重多1 } while(m--){ int l1,r1,l2,r2; cin>>l1>>r1>>l2>>r2; if(get(l1,r1)==get(l2,r2)) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }
十三、STL简介
vector，变长数组，倍增思想 size() 返回元素个数 empty() 返回是否为空 clear() 清空 front()/back() push_back()/pop_back() begin()/end() [] 支持比较运算，按字典序
pair<int,int>(头文件#include <utility>) first 第一个元素 second 第二个元素 支持比较运算，以first为第一关键字，以second为第二关键字（字典序） 1
3. string(头文件#include <string>)
size()/length() 返回字符串长度 empty() clear() substr(起始下标,(子串长度)) 返回子串（若第二个参数省略或大于当前字符串长度，则返回整个字符串） c_str() 返回字符串所在字符数组的起始地址 find() 查找字符第一次出现的位置，如果没有出现过返回string::npos，注意加string作用域，否则编译器不认识npos
头文件#include <string>
stoi()：将字符串转化为int类型，传入string类型字符串。 atoi()：将字符串转化为int类型，传入char类型字符串。 to_string()：将数字常量量转化为string类型字符串。 //注意字符利用ASCII码进行过转换时（加减数字），需要强制类型转换。
queue，队列(头文件#include <queue>) size() empty() push() 向队尾插入一个元素 front() 返回队头元素 back() 返回队尾元素 pop() 弹出队头元素
新建空队列（清空队列q）
priority_queue，优先队列，默认是大根堆(头文件#include <queue>) size() empty() push() 插入一个元素 top() 返回堆顶元素 pop() 弹出堆顶元素 定义成小根堆的方式：priority_queue<int,vector<int>,greater<int>>q; （也可以将正数变成相反数插入堆，得到的便是每个元素是负数的小根堆，需要操作时，取出元素加负号就是原序列的元素）
6. stack,栈(头文件#include <stack>)
size() empty() push() 向栈顶插入一个元素 top() 返回栈顶元素 pop() 弹出栈顶元素
deque，双端队列(头文件#include <deque>) size() empty() clear() front()/back() push_back()/pop_back() push_front()/pop_front() begin()/end()
set，map，multiset，multimap，基于平衡二叉树（红黑树），动态维护有序序列,set、map去重，multise、multimap不去重(头文件#include <set>、#include <map>) size() empty() clear() begin()/end() ++,--返回前驱和后继，时间复杂度O(logn) 有重复元素，map不会插入新元素，所以旧元素不会被覆盖更新
set/multiset(头文件#include <set>) insert() 插入一个数 find() 查找一个数，如果找到返回该数第一次出现的位置的迭代器，否则返回容器尾迭代 count() 返回某一个数的个数 erase() (1)输入是一个数x，删除所有x O(k+logn)（k为x的个数） (2)输入一个迭代器，删除这个迭代器 lower_bound()/upper_bound() lower_bound(x) 返回大于等于x的最小的数的迭代器 upper_bound(x) 返回大于x的最小的数的迭代器
10. map/multimap(头文件#include <map>)
insert() 插入的数是一个pair erase() 输入的参数是pair或者迭代器 find() 同上 [] 注意multimap不支持此操作。时间复杂度O(logn) lower_bound()/upper_bound()
unordered_set，unordered_map，unordered_multiset，unordered_multimap，哈希表(头文件#include <unordered_set>、#include <unordered_map>) 和上面类似，增删改查的时间复杂度为O(1) 不支持 lower_bound()/upper_bound()，迭代器的++，--
bitset，压位(头文件#include <bitset>) bitset<10000> s; ~,&,|,^ >>,<< ==,!= [] count() 返回有多少个1 any() 判断是否至少有一个1 none() 判断是否全为0 set() 把所有位置成1 set(k,v) 把第k位变成v reset() 把所有位变成0 flip() 等价于~ flip(k) 把第k位取反
