经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置：技术经验 » 程序设计 » C » 查看文章
师徒恋大法好
来源：cnblogs　　作者：wendster　　时间：2018/11/5 11:09:41　　对本文有异议

有了STL，不必再从头写大多的标准数据结构和算法，并且可获得非常高的性能。（如果没有氧气，最好不要用vector，deque，set，multiset，map，string）。

废话不多说，让我们一起看看STL到底有多好用。

1.vector

可变长度的数组。（可节省空间）

常用操作：

  1. #include<vector>
  2. vector<int>a;
  3. a[i];//重载了[]，返回数组的第i+1个元素(从0开始)
  4. a.empty()//数组为空返回1，否则返回0
  5. a.size()//返回数组元素个数
  6. a.push_back(x)//尾部插入元素x
  7. a.pop_back()//删除尾部元素
  8. a.begin()//返回第一个元素迭代器
  9. a.end()//返回最后一个元素迭代器

上面的操作时间复杂度均为O(1);(但常数大，比数组慢，只有吸氧才能和数组媲美)

下面的操作慎用：

  1. a.erase(it1，it2)//删除迭代器it1到it2的元素(前闭后开)
  2. a.erase(it)//删除迭代器it指向的元素
  3. a.clear();//清空数组
  4. a.insert(it,x)//在迭代器为it的位置加入x，其他后移
  5. a.assign(b.begin(),b.end())//把vector b复制到vector a

这些操作时间复杂度为O(n)，且常数较大。

vector支持algorithm库中的某些操作，如：

  1. sort(a.begin(),a.end(),cmp);//排序，cmp是自定义函数。
  2. lower_bound(a.begin(),a.end(),x);//返回数组中第一个大于等于x的元素的迭代器。
  3. upper_bound(a.begin(),a.end(),x)//返回数组中第一个大于x的元素的迭代器。
  4. max_element(a.begin(),a.end())//返回数组最大值
  5. min_element(a.begin(),a.end())//返回数组最小值
  6. random_shuffle(a.begin(),a.end())//随机打乱，在随机化(乱搞)算法中用到。
  7. reverse(a.begin(),a.end())//数组反转

注意：没有氧气，慎用vector

下面通过几道例题感受vector的简便。

例题1：洛谷P1177【模板】快速排序

虽然可以用sort，但我们尝试使用vector来实现。

  1. #include<bits/stdc++.h>
  2. std::vector<int>a;
  3. int main(){
  4.     int n,x;
  5.     scanf("%d",&n);
  6.     for(register int i=0;i<n;++i)scanf("%d",&x),a.insert(upper_bound(a.begin(),a.end(),x),x);
  7.     for(register int i=0;i<n;++i)printf("%d ",a[i]);
  8.     return 0;
  9. }

从上面可以看出，vector可以非常便捷地支持插排。

例题2：P3378 【模板】堆

虽然可以使用另一个容器priority_queue，但我们可以使用vector切了它。

  1. #include<bits/stdc++.h>
  2. std::vector<int>a;
  3. int main(){
  4.     int n,k,x;
  5.     scanf("%d",&n);
  6.     for(register int i=1;i<=n;++i){
  7.         scanf("%d",&k);
  8.         if(k==1){
  9.             scanf("%d",&x);
  10.             a.insert(upper_bound(a.begin(),a.end(),x),x);
  11.         }
  12.         else if(k==2)printf("%d\n",a[0]);
  13.         else a.erase(a.begin());
  14.     }
  15.     return 0;
  16. }

从上面两道例题可以看出，vector的操作也不一定慢（玄学n方过百万），但是最好注意程序的常数，能开O2尽量开

例题3：洛谷P3369 【模板】普通平衡树

此题是上述操作的综合，不要以为数组很菜，它能支(A)持(K)平(I)衡(O)树(I)的操作呢。（骚的一批）

  1. #include<bits/stdc++.h>
  2. std::vector<int>a;
  3. int main(){
  4.     int n,opt,x;
  5.     scanf("%d",&n);
  6.     for(register int i=1;i<=n;++i){
  7.         scanf("%d%d",&opt,&x);
  8.         if(opt==1)a.insert(upper_bound(a.begin(),a.end(),x),x);
  9.         else if(opt==2)a.erase(lower_bound(a.begin(),a.end(),x));
  10.         else if(opt==3)printf("%d\n",lower_bound(a.begin(),a.end(),x)-a.begin()+1);
  11.         else if(opt==4)printf("%d\n",a[x-1]);
  12.         else if(opt==5)printf("%d\n",*(lower_bound(a.begin(),a.end(),x)-1));
  13.         else printf("%d\n",*(upper_bound(a.begin(),a.end(),x)));
  14.     }
  15.     return 0;
  16. }

从第一个容器就能看出师徒恋的方便了吧

2.stack

常用操作：

  1. #include<stack>
  2. stack<int>st;
  3. st.push(x)//向栈顶加入x,O(1)
  4. st.pop()//栈顶出栈,O(1)
  5. st.top()//返回栈顶,O(1)

看出来了吗？stack的所有操作vector都能支持。

但栈的思想很重要，后缀表达式，tarjan强连通分量算法以及单调栈等都需要用到。

这里给大家推荐一道单调栈例题，感受一下单调栈

例题：洛谷SP1805 HISTOGRA - Largest Rectangle in a Histogram

如果矩形从左到右单调递增，答案是以每个矩形的高度为高度，从当前矩形到右边界为宽度的矩形的面积的最大值

如果下一个比上一个矮，那么这块矩形和之前的矩形构成较大面积时，新矩形高度不可能超过此矩形高度，所以可以把比此矩形高的矩形删掉，用宽度不变，高度为此矩形高度的矩形替代

简单说，我们维护一个栈，保存高度单调递增的矩形，然后扫描每个矩形，如果比栈顶矩形高，进栈，否则栈顶出栈直至栈空或栈顶矩形比当前矩形矮(简单吧)

  1. #include<bits/stdc++.h>
  2. long long n,p,a[100001],w[100001],ans,kd;
  3. std::stack<long long>st;
  4. int main(){
  5.     while(scanf("%lld",&n)&&n){
  6.         for(register long long i=1;i<=n;++i)scanf("%lld",&a[i]);
  7.         a[n+1]=0;st.push(0);ans=0;//注意栈为空时.top()会出错,a[n+1]=0避免结束后栈中还有矩形
  8.         for(register long long i=1;i<=n+1;++i)
  9.             if(a[i]>st.top())st.push(a[i]),w[st.size()]=1;//比栈顶矩形高
  10.             else{//否则更新答案
  11.                 kd=0;
  12.                 while(st.top()>a[i])kd+=w[st.size()],ans=std::max(ans,kd*st.top()),st.pop();
  13.                 st.push(a[i]);w[st.size()]=kd+1;
  14.             }
  15.         printf("%lld\n",ans);
  16.     }
  17.     return 0;
  18. }

这就是单调栈,O(n),借助单调性,能及时排除不可能选项,保持高度有效性和秩序性。

3.queue

循环队列(可节省空间)

常用操作：

  1. #include<queue>
  2. queue<int>q;
  3. q.push(x)//队尾加入x
  4. q.pop()//队首出队
  5. q.front()//返回队首
  6. q.back()//返回队尾
  7. q.empty()//队列为空返回1否则返回0
  8. q.size()//返回队列大小

循环队列的操作都是O(1)的，并且常数较小，使用方便。

循环队列一般用于广搜，树和图的广度优先遍历，拓扑排序和SPFA等算法中。

树和图的广度优先遍历：

  1. inline void bfs(){
  2.     memset(d,0,sizeof(d));//d数组记录点在树中的深度或点在图中的层次。
  3.     queue<int>q;
  4.     q.push(1);d[1]=1;
  5.     whiel(!q.empty()){
  6.         int x=q.front();q.pop();
  7.         for(register int i=head[x];i;i=edge[i].next){//链式前向星存边
  8.             if(d[edge[i].to])continue;
  9.             d[edge[i].to]=d[x]+1;q.push(edge[i].to);
  10.         }
  11.     }
  12. }

广搜在骗分博客中会详讲。此处略

拓扑排序：

  1. #include<bits/stdc++.h>
  2. int x,n,m,deg[1000001],head[1000001],u,v,a[1000001],cnt;
  3. struct Edge{int next,to;}edge[1000001];
  4. inline void topsort(){
  5.     queue<int>q;
  6.     for(register int i=1;i<=n;++i)if(!deg[i])q.push(i);
  7.     while(!q.empty()){
  8.         int x=q.front();q.pop();a[++cnt]=x;
  9.         for(register int i=head[x];i;i=edge[i].next)if(--deg[edge[i].to])q.push(edge[i].to);
  10.     }
  11. }
  12. int main(){
  13.     scanf("%d%d",&n,&m);
  14.     for(register int i=1;i<=m;++i){scanf("%d%d",&u,&v);edge[i].next=head[u];edge[i].to=v;head[u]=i;++deg[v];}
  15.     //链式前向星存边并统计入度
  16.     topsort();
  17.     for(register int i=1;i<=cnt;++i)printf("%d ",a[i]);
  18.     return 0;
  19. }

洛谷P3371 【模板】单源最短路径（弱化版）

关于SPFA 它死了

  1. #include<bits/stdc++.h>
  2. int n,m,k,x,head[1000001],dis[1000001],vis[1000001],u,v,w;
  3. struct Edge{int next,to,w;}edge[1000001];
  4. inline void spfa(int k){
  5.     for(register int i=1;i<=n;++i)dis[i]=0x7fffffff,vis[i]=0;
  6.     std::queue<int>q;q.push(k);dis[k]=0;vis[k]=1;
  7.     while(!q.empty()){
  8.         x=q.front();q.pop();vis[x]=0;
  9.         for(register int i=head[x];i;i=edge[i].next)
  10.             if(dis[edge[i].to]>dis[x]+edge[i].w){
  11.                 dis[edge[i].to]=dis[x]+edge[i].w;
  12.                 if(!vis[edge[i].to])vis[edge[i].to]=1,q.push(edge[i].to);
  13.             }
  14.     }
  15. }
  16. int main(){
  17.     scanf("%d%d%d",&n,&m,&k);
  18.     for(register int i=1;i<=m;++i){scanf("%d%d%d",&u,&v,&w);edge[i].next=head[u];edge[i].to=v;edge[i].w=w;head[u]=i;}
  19.     spfa(k);
  20.     for(register int i=1;i<=n;++i)printf("%d ",dis[i]);
  21.     return 0;
  22. }

4.deque

双端队列deque==vector+queue，即能高效从队列两端进行操作的队列,包含所有vector支持的操作，还支持：

  1. #include<deque>
  2. deque<int>dq;
  3. dq.push_front(x)//从队首插入,O(1)
  4. dq.pop_front()//队首出队,O(1)

有了vector和queue，为什么还要deque呢？

因为有单调栈就要有单调队列啦(雾

双端队列可以支持单调队列的操作

例题：洛谷 P1886 滑动窗口

用两个双端队列维护区间最值

  1. #include<bits/stdc++.h>
  2. int x,n,m,cnt=1,k;
  3. std::deque<std::pair<int,int> >q,q1;//q维护单调递减序列,q1维护单调递增序列
  4. int ans[2][1000001];
  5. int main(){
  6.     scanf("%d%d",&n,&k);
  7.     for(int i=1;i<=n;i++){
  8.         scanf("%d",&x);
  9.         while(!q.empty()&&x>=q.back().second)q.pop_back();//保持单调性
  10.         while(!q1.empty()&&x<=q1.back().second)q1.pop_back();
  11.         q.push_back(std::make_pair(i,x));q1.push_back(std::make_pair(i,x));
  12.         while(i-k>=q.front().first)q.pop_front();//保证序列在区间内
  13.         while(i-k>=q1.front().first)q1.pop_front();
  14.         if(i>=k)ans[0][cnt]=q.front().second,ans[1][cnt++]=q1.front().second;
  15.     }
  16.     for(int i=1;i<cnt;i++)printf("%d ",ans[1][i]);
  17.     puts("");
  18.     for(int i=1;i<cnt;i++)printf("%d ",ans[0][i]);
  19.     return 0;
  20. }

单调栈和单调队列都是挖掘题目中的单调性，及时排除不可能，能保持序列的高度有效性和秩序性，能解决一些高级数据结构(如线段树)才能解决的问题，值得我们思考

注意，deque和vector比较相似，最好降低常数，没有氧气，慎用deque

因为NOIP所以不讲单调队列优化多重背包

5.pair

这就是上面代码中出现的pair(没什么好讲的

二元组，尖括号内为自己定义的类型，用.first()访问第一元，用.second()访问第二元，重载了<，第一元优先级高于第二元

主要用于STL其他容器的存储类型，如上面程序中双端队列的类型为一个二元组，第一元表示序号，第二元表示大小

6.priority_queue

优先队列，通俗讲就是没素质，插队

操作：

  1. #include<queue>
  2. priority_queue<int>q;//定义大根堆，即大的插队
  3. priority_queue<int,vector<int>,greater<int> >q;//定义小根堆，即小的插队
  4. q.push(x)//将x插入堆,O(logn)
  5. q.pop()//堆顶出堆,O(logn)
  6. q.top()//返回堆顶,O(1)

看完上面的操作，你想到了什么呢？对，没错，它能动态维护序列的最值

堆能优化贪心，dijkstra，prim等算法

但需要注意优先队列存储类型必须重载<。优先队列不支持erase，这让我们很蛋疼，解决方案为在删除时，在堆外记录(例如记录元素最新值)，用于鉴别过时元素，在堆顶取出最值时，再检查是不是过时的，若是，取下一个

例题1：洛谷 P1090 合并果子

思路就是每次取出两个最小值合并，用堆维护

  1. #include<bits/stdc++.h>
  2. int n,x,ans,a,b;
  3. std::priority_queue<int,std::vector<int>,std::greater<int> >q;
  4. int main(){
  5.     scanf("%d",&n);
  6.     for(int i=1;i<=n;i++)scanf("%d",&x),q.push(x);
  7.     while(q.size()>=2)a=q.top(),q.pop(),b=q.top(),q.pop(),ans+=a+b,q.push(a+b);
  8.     printf("%d\n",ans);
  9.     return 0;
  10. }

这就是堆优化贪心

例题2：洛谷P4779 【模板】单源最短路径（标准版）

堆优化dijkstra

  1. #include<bits/stdc++.h>
  2. int x,y,n,m,k,u,v,w,head[1000001],dis[1000001],vis[1000001];
  3. struct Edge{int next,to,w;}edge[1000001];
  4. inline void dijkstra(int k){
  5.     for(register int i=1;i<=n;++i)dis[i]=0x7fffffff,vis[i]=0;//初始化
  6.     std::priority_queue<std::pair<int,int>,std::vector<std::pair<int,int> >,std::greater<std::pair<int,int> > >q;q.push(std::make_pair(0,k));dis[k]=0;
  7.     while(!q.empty()){
  8.         x=q.top().second;q.pop();
  9.         if(vis[x])continue;
  10.         vis[x]=1;
  11.         for(register int i=head[x];i;i=edge[i].next)if(dis[edge[i].to]>dis[x]+edge[i].w)dis[edge[i].to]=dis[x]+edge[i].w,q.push(std::make_pair(dis[edge[i].to],edge[i].to));
  12.     }
  13. }
  14. int main(){
  15.     scanf("%d%d%d",&n,&m,&k);
  16.     for(register int i=1;i<=m;++i)scanf("%d%d%d",&u,&v,&w),edge[i].next=head[u],edge[i].to=v,edge[i].w=w,head[u]=i;
  17.     dijkstra(k);
  18.     for(register int i=1;i<=n;++i)printf("%d ",dis[i]);
  19.     return 0;
  20. }

毒瘤压行

这就是堆优化dijkstra，O((n+m)logn)比某个死了的算法好多了

7.string

字符串string，很多人不是很会使用它，其实它能在水掉很多字符串的题

基本操作：

  1. #include<string>
  2. #include<sstream>//stringstream头文件
  3. string s,s1;
  4. stringstream ss(s);
  5. ss>>s;
  6. char c;
  7. cin>>s//输入
  8. [],+,+=,>,<,>=,<=,==,!=,= //重载[]，从0开始编号，+连接两个字符串，比较运算符从第一个字符开始比较，=赋值
  9. getline(cin,s)//输入一行
  10. s.push_back(c)//字符串尾端加入字符c
  11. s.append(c)//字符串尾端加入字符c
  12. s.append(n,c)//在字符串尾端加入n个字符c
  13. s.insert(it,c)//在迭代器it处插入c
  14. s.substr(l,r)//返回l到r的字符串(前闭后开)
  15. s.find(s1)//搜索字符串，返回第一次找到的位置，若没找到返回-1
  16. s.empty()//是否为空，为空返回1,否则返回0
  17. s.erase(it)//清除迭代器it指向的元素
  18. s.erase(it1,it2)//清除迭代器it1到it2之间的元素(前闭后开)
  19. s.replace(a,len,str)//从a开始len个用str替换

常用操作就是这些了，find在一定程度上可以替代KMP，+和substr可以构造字符串只要不是模板题或数据卡你，就算时间复杂度是错的，也能在你不会写时骗到更多的分，且调试难度极低，纯模拟至少能拿到分，只要你坚信，n^2过百万，暴力碾标算，根据常数的优秀以及NOIP的水数据就有可能得到AC的好成绩

你肯定会好奇stringstream是什么，让我来告诉你

试想一道题因为找不到这样的题,输入若干个整数，求和

如果你会快读，应该能写出来，但是容易写错，也有点难理解，这里提供一种解决方案,使用stringstream，很容易理解

  1. #include<bits/stdc++.h>
  2. string s;
  3. int sum,x;
  4. int main(){
  5.     getline(std::cin,s);
  6.     stringstream ss(s);
  7.     while(ss>>x)sum+=x;
  8.     printf("%d",sum);
  9.     return 0;
  10. }

现在理解stringstream了吧，它能将读入的字符串变成其他类型的变量，或一行字符串变成空格分隔的多个字符串。但请注意，string很慢，stringstream更慢，所以还是那句话，没有氧气，慎用

综上，有效地利用各种字符串处理函数和模拟，能使你的NOIP分数提高一个档次

8.set和multiset

集合和可重集合，内部实现是一棵红黑树呵呵，但是常数较大使得它的效率较低

基本操作：

  1. #include<set>
  2. set<int>a;
  3. multiset<int>b;
  4. a.size(x)//返回大小,O(1)
  5. a.empty()//返回是否为空，空返回1，否则返回0
  6. a.clear()//清空，O(nlogn)
  7. a.begin()//返回最小元素迭代器
  8. a.end()//返回最大元素迭代器
  9. a.insert(x)//插入x
  10. a.find(x)//查找x，若存在返回指向该元素的迭代器，若不存在返回a.end(),O(logn)
  11. a.lower_bound(x)//返回第一个大于等于x的元素的迭代器，O(logn)
  12. a.upper_bound(x)//返回第一个大于x的元素的迭代器，O(logn)
  13. a.erase(it)//删除迭代器it指向的元素，O(logn)
  14. a.erase(x)//删除所有等于x的元素,O(k+logn),k为等于x的元素个数
  15. if((it=s.find(x))!=s.end())s.erase(it);//可以只删除一个等于x的元素
  16. a.count(x)//返回元素个数，O(k+logn),k为等于x的元素个数

set能排序并去重，能方便地进行离散化等操作,还能用它实现珂朵莉树。但注意，set，multiset和map的迭代器的只支持自增或自减且自增或自减的时间复杂度是O(logn)的，所以在使用时一定要注意

例题1：洛谷 UVA10815 Andy's First Dictionary

由于string重载了<，所以把非字母字符转化为空格，再用stringstream得到单词丢进set，排序且去重

  1. #include<bits/stdc++.h>
  2. std::set<std::string>zd;
  3. std::string s,dc;
  4. int main(){
  5.     while(std::cin>>s){
  6.         for(register int i=0;i<s.size();++i)
  7.             if(s[i]>='a'&&s[i]<='z'||s[i]>='A'&&s[i]<='Z')s[i]=tolower(s[i]);
  8.             else s[i]=' ';
  9.         std::stringstream ss(s);
  10.         while(ss>>dc)zd.insert(dc);
  11.     }
  12.     for(std::set<std::string>::iterator it=zd.begin();it!=zd.end();++it)std::cout<<*it<<std::endl;
  13.     return 0;
  14. }

从上面的例题就能看出set排序加去重的方便了

例题2：洛谷 UVA136 Ugly Numbers

用优先队列保存所有已生成的丑数，每次取最小x，生成2x，3x，5x插入堆中，注意一个丑数有多种生成方式，所以可以用set判断是否已生成过

  1. #include<bits/stdc++.h>
  2. std::priority_queue<long long,std::vector<long long>,std::greater<long long> >q;
  3. std::set<long long>s;
  4. long long a[3]={2,3,5},x,t;
  5. int main(){
  6.     q.push(1);s.insert(1);
  7.     for(register int i=1;;++i){
  8.         x=q.top();q.pop();
  9.         if(i==1500){printf("The 1500'th ugly number is %d.\n",x);break;}
  10.         for(register int j=0;j<3;++j){
  11.             t=x*a[j];
  12.             if(!s.count(t))s.insert(t),q.push(t);
  13.         }
  14.     }
  15.     return 0;
  16. }

从上可以看出学会同时运用多个容器，融会贯通，能解决更多的题目。

9.map

map映射，它的内部实现也是一棵红黑树呵呵,同样，也因为常数较大使得效率较低

基本操作

  1. #include<map>
  2. map<key，value>a;//建立一个key到value的映射，如map<string，int>a
  3. a.size()//返回大小，O(1)
  4. a.empty()//返回是否为空，空返回1，否则返回0,O(1)
  5. a.clear()//清空,O(nlogn)
  6. a.begin()//返回第一个元素的迭代器,O(1)
  7. a.end()//返回最后一个元素的迭代器,O(1)
  8. a.insert(pair<string,int>)//参数必须是pair,O(logn)
  9. a.erase(pair<string,int>)//参数必须是pair或迭代器,O(logn)
  10. a.erase(it)//O(logn)
  11. a.find(x)//查找x，若存在返回指向key为x的二元组的迭代器,O(logn)
  12. a[x]//重载了[],O(logn),需要注意，若x不存在，则会自动新建一个二元组(x,0或NULL)，强烈建议用[]之前，先用find()检查存在性

map可不得了，它可以一定程度上代替hash表

例题1:洛谷 P3370 【模板】字符串哈希

用map不光能解决这道题，还能统计单词的出现次数

  1. #include<bits/stdc++.h>
  2. std::map<std::string,int>a;
  3. int n;
  4. std::string s;
  5. int main(){
  6.     scanf("%d",&n);
  7.     while(n--){
  8.         std::cin>>s;
  9.         if(a.find(s)==a.end())++a[s];//统计单词的出现次数
  10.     }
  11.     printf("%d",a.size());
  12.     return 0;
  13. }

可以方便的代替hash表，但常数大，有时需要注意

例题2：洛谷 UVA156 Ananagrams

把每个单词初始化，全部转化成小写在排序，然后丢进map统计

  1. #include<bits/stdc++.h>
  2. std::map<std::string,int>mp;
  3. std::vector<std::string>a;
  4. std::string s;
  5. int n;
  6. inline std::string init(const std::string &s){//初始化
  7.     std::string ans=s;
  8.     for(register int i=0;i<ans.size();++i)ans[i]=tolower(ans[i]);
  9.     sort(ans.begin(),ans.end());
  10.     return ans;
  11. }
  12. int main(){
  13.     while(std::cin>>s&&s[0]!='#'){
  14.         a.push_back(s);std::string s1=init(s);
  15.         if(!mp.count(s1))mp[s1]=0;
  16.         mp[s1]++;
  17.     }
  18.     std::vector<std::string>ans;
  19.     for(register int i=0;i<a.size();++i)if(mp[init(a[i])]==1)ans.push_back(a[i]);
  20.     sort(ans.begin(),ans.end());
  21.     for(register int i=0;i<ans.size();++i)std::cout<<ans[i]<<std::endl;
  22.     return 0;
  23. }

此例说明，没有良好的代码设计，是无法发挥STL的威力的，如果没有想到初始化，很难用map简化代码

10.bitset

bitset可看做多位二进制数，每8位占用一个字节，相当于状压的bool数组，支持基本位运算，n位bitset执行一次位运算的复杂度可视为n/32，效率较高

  1. #include<bitset>
  2. bitset<1000001>s;//尖括号中写位数
  3. ~s//按位取反
  4. &,|,^//按位与或，异或
  5. <<,>> //左移右移
  6. ==,!= //比较是否相等
  7. s[k]//表示第k位，从0开始
  8. s.count()//返回多少位为1,O(n)
  9. s.any()//若所有位为0返回0，否则返回1
  10. s.none()//若所有位为0返回1，否则返回0
  11. s.set()//所有位变为1
  12. s.set(k,v)//把第k位变为v，即s[k]=v
  13. s.reset()//把所有位变为0,
  14. s.reset(k)//把第k为变为0，即s[k]=0
  15. s.flip()//把所有位取反，即s=~s
  16. s.flip(k)//把第k位取反，即s[k]^=1

例题

11.algorithm

STL的算法库，提供了

  1. int a[1000001];
  2. reverse(a+1,a+n+1);//翻转1~n
  3. int m=unique(a+1,a+n+1)-a-1;//m为去重后的元素个数
  4. random_shuffle(a+1,a+n+1);//随机打乱
  5. do{
  6. }next_permutation(a+1,a+n+1);//下一个排列，当不存在排名更靠后的排列返回0，否则返回1
  7. sort(a+1,a+n+1);//快排
  8. inline void cmp(const int &a,const int &b){return ...}
  9. sort(a+1,a+n+1,cmp)//cmp自定义快排，返回值为1即交换
  10. lower_bound(a+1,a+n+1,x)//返回第一个大于等于x的元素下标
  11. upper_bound(a+1,a+n+1,x)//返回第一个大于x的元素下标

上述就是STL库中的常用的函数，其中a数组可用vector，deque，string等容器替换

最后，祝大家NOIP2018 rp++

 友情链接：直通硅谷 　点职佳 　北美留学生论坛

C热门文章

  • C/C++编程笔记：编写不会在C ++中编译的C程序，我教你呀！
  • 洛谷 P2085 最小函数值
  • 使用C++界面框架ImGUI开发一个简单程序
  • C++ Json解析CJsonObject的详细使用
  • C++编译错误杂记
  • 二分法（二）：采用二分法解决“最小化最大值问题”
  • C++实现json字符串与map的转换
  • C++借助curses库实现俄罗斯方块
  • 长乐培训Day5
  • 【OpenFOAM】——OpenFOAM入门算例学习

    • C推荐文章

  • #8. 「模板」树链剖分
  • 预设型 DP
  • Standard Template Libary or C++ Standard Library
  • 一种优秀的虚拟机内存架构 - AQ
  • 如何让 MGR 不从 Primary 节点克隆数据？
  • TLScanary：Pwn中的利器
  • c++临时对象导致的生命周期问题
  • C++(Qt)-GIS开发-简易瓦片地图下载器
  • 逆向通达信 x 逆向微信 x 逆向Qt
  • C++面向对象

    • 本站QQ群：前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

    W3xue 的所有内容仅供测试，对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
    关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接（目前9元/月）请联系QQ：27243702 沸活量
    皖ICP备17017327号-2　皖公网安备34020702000426号