師徒戀大法好_ZenDei技術網路在線

有了STL，不必再從頭寫大多的標準數據結構和演算法，並且可獲得非常高的性能。（如果沒有氧氣，最好不要用vector，deque，set，multiset，map，string）。廢話不多說，讓我們一起看看STL到底有多好用。 1.vector 可變長度的數組。（可節省空間）常用操作：上面的操作時 ...

有了STL，不必再從頭寫大多的標準數據結構和演算法，並且可獲得非常高的性能。（如果沒有氧氣，最好不要用vector，deque，set，multiset，map，string）。

廢話不多說，讓我們一起看看STL到底有多好用。

1.vector

可變長度的數組。（可節省空間）

常用操作：

#include<vector>
vector<int>a;
a[i];//重載了[]，返回數組的第i+1個元素(從0開始)
a.empty()//數組為空返回1，否則返回0
a.size()//返回數組元素個數
a.push_back(x)//尾部插入元素x
a.pop_back()//刪除尾部元素
a.begin()//返回第一個元素迭代器
a.end()//返回最後一個元素迭代器

上面的操作時間複雜度均為O(1);(但常數大，比數組慢，只有吸氧才能和數組媲美)

下麵的操作慎用：

a.erase(it1，it2)//刪除迭代器it1到it2的元素(前閉後開)
a.erase(it)//刪除迭代器it指向的元素
a.clear();//清空數組
a.insert(it,x)//在迭代器為it的位置加入x，其他後移
a.assign(b.begin(),b.end())//把vector b複製到vector a

這些操作時間複雜度為O(n)，且常數較大。

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

sort(a.begin(),a.end(),cmp);//排序，cmp是自定義函數。
lower_bound(a.begin(),a.end(),x);//返回數組中第一個大於等於x的元素的迭代器。
upper_bound(a.begin(),a.end(),x)//返回數組中第一個大於x的元素的迭代器。
max_element(a.begin(),a.end())//返回數組最大值
min_element(a.begin(),a.end())//返回數組最小值
random_shuffle(a.begin(),a.end())//隨機打亂，在隨機化(亂搞)演算法中用到。
reverse(a.begin(),a.end())//數組反轉

註意：沒有氧氣，慎用vector

下麵通過幾道例題感受vector的簡便。

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

雖然可以用sort，但我們嘗試使用vector來實現。

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

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

例題2：P3378 【模板】堆

雖然可以使用另一個容器priority_queue，但我們可以使用vector切了它。

#include<bits/stdc++.h>
std::vector<int>a;
int main(){
    int n,k,x;
    scanf("%d",&n);
    for(register int i=1;i<=n;++i){
        scanf("%d",&k);
        if(k==1){
            scanf("%d",&x);
            a.insert(upper_bound(a.begin(),a.end(),x),x);
        }
        else if(k==2)printf("%d\n",a[0]);
        else a.erase(a.begin());
    }
    return 0;
}

從上面兩道例題可以看出，vector的操作也不一定慢（玄學n方過百萬），但是最好註意程式的常數，~~能開O2儘量開~~

例題3：洛谷P3369 【模板】普通平衡樹

此題是上述操作的綜合，不要以為數組很菜，它能支(A)持(K)平(I)衡(O)樹(I)的操作呢。~~（騷的一批）~~

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

~~從第一個容器就能看出師徒戀的方便了吧~~

2.stack

常用操作：

#include<stack>
stack<int>st;
st.push(x)//向棧頂加入x,O(1)
st.pop()//棧頂出棧,O(1)
st.top()//返回棧頂,O(1)

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

但棧的思想很重要，尾碼表達式，tarjan強連通分量演算法以及單調棧等都需要用到。

這裡給大家推薦一道單調棧例題，感受一下單調棧

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

如果矩形從左到右單調遞增，答案是以每個矩形的高度為高度，從當前矩形到右邊界為寬度的矩形的面積的最大值

如果下一個比上一個矮，那麼這塊矩形和之前的矩形構成較大面積時，新矩形高度不可能超過此矩形高度，所以可以把比此矩形高的矩形刪掉，用寬度不變，高度為此矩形高度的矩形替代

簡單說，我們維護一個棧，保存高度單調遞增的矩形，然後掃描每個矩形，如果比棧頂矩形高，進棧，否則棧頂出棧直至棧空或棧頂矩形比當前矩形矮~~(簡單吧)~~

#include<bits/stdc++.h>
long long n,p,a[100001],w[100001],ans,kd;
std::stack<long long>st;
int main(){
    while(scanf("%lld",&n)&&n){
        for(register long long i=1;i<=n;++i)scanf("%lld",&a[i]);
        a[n+1]=0;st.push(0);ans=0;//註意棧為空時.top()會出錯,a[n+1]=0避免結束後棧中還有矩形
        for(register long long i=1;i<=n+1;++i)
            if(a[i]>st.top())st.push(a[i]),w[st.size()]=1;//比棧頂矩形高
            else{//否則更新答案
                kd=0;
                while(st.top()>a[i])kd+=w[st.size()],ans=std::max(ans,kd*st.top()),st.pop();
                st.push(a[i]);w[st.size()]=kd+1;
            }
        printf("%lld\n",ans);
    }
    return 0;
}

這就是單調棧,O(n),藉助單調性,能及時排除不可能選項,保持高度有效性和秩序性。

3.queue

迴圈隊列(可節省空間)

常用操作：

#include<queue>
queue<int>q;
q.push(x)//隊尾加入x
q.pop()//隊首出隊
q.front()//返回隊首
q.back()//返回隊尾
q.empty()//隊列為空返回1否則返回0
q.size()//返回隊列大小

迴圈隊列的操作都是O(1)的，並且常數較小，使用方便。

迴圈隊列一般用於廣搜，樹和圖的廣度優先遍歷，拓撲排序和SPFA等演算法中。

樹和圖的廣度優先遍歷：

inline void bfs(){
    memset(d,0,sizeof(d));//d數組記錄點在樹中的深度或點在圖中的層次。
    queue<int>q;
    q.push(1);d[1]=1;
    whiel(!q.empty()){
        int x=q.front();q.pop();
        for(register int i=head[x];i;i=edge[i].next){//鏈式前向星存邊
            if(d[edge[i].to])continue;
            d[edge[i].to]=d[x]+1;q.push(edge[i].to);
        }
    }
}

~~廣搜在騙分博客中會詳講。此處略~~

拓撲排序：

#include<bits/stdc++.h>
int x,n,m,deg[1000001],head[1000001],u,v,a[1000001],cnt;
struct Edge{int next,to;}edge[1000001];
inline void topsort(){
    queue<int>q;
    for(register int i=1;i<=n;++i)if(!deg[i])q.push(i);
    while(!q.empty()){
        int x=q.front();q.pop();a[++cnt]=x;
        for(register int i=head[x];i;i=edge[i].next)if(--deg[edge[i].to])q.push(edge[i].to);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    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];}
    //鏈式前向星存邊並統計入度
    topsort();
    for(register int i=1;i<=cnt;++i)printf("%d ",a[i]);
    return 0;
}

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

關於SPFA ~~它死了~~

#include<bits/stdc++.h>
int n,m,k,x,head[1000001],dis[1000001],vis[1000001],u,v,w;
struct Edge{int next,to,w;}edge[1000001];
inline void spfa(int k){
    for(register int i=1;i<=n;++i)dis[i]=0x7fffffff,vis[i]=0;
    std::queue<int>q;q.push(k);dis[k]=0;vis[k]=1;
    while(!q.empty()){
        x=q.front();q.pop();vis[x]=0;
        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;
                if(!vis[edge[i].to])vis[edge[i].to]=1,q.push(edge[i].to);
            }
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    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;}
    spfa(k);
    for(register int i=1;i<=n;++i)printf("%d ",dis[i]);
    return 0;
}

4.deque

雙端隊列deque==vector+queue，即能高效從隊列兩端進行操作的隊列,包含所有vector支持的操作，還支持：

#include<deque>
deque<int>dq;
dq.push_front(x)//從隊首插入,O(1)
dq.pop_front()//隊首出隊,O(1)

有了vector和queue，為什麼還要deque呢？

因為有單調棧就要有單調隊列啦(霧

雙端隊列可以支持單調隊列的操作

例題：洛谷 P1886 滑動視窗

用兩個雙端隊列維護區間最值

#include<bits/stdc++.h>
int x,n,m,cnt=1,k;
std::deque<std::pair<int,int> >q,q1;//q維護單調遞減序列,q1維護單調遞增序列
int ans[2][1000001];
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        while(!q.empty()&&x>=q.back().second)q.pop_back();//保持單調性
        while(!q1.empty()&&x<=q1.back().second)q1.pop_back();
        q.push_back(std::make_pair(i,x));q1.push_back(std::make_pair(i,x));
        while(i-k>=q.front().first)q.pop_front();//保證序列在區間內
        while(i-k>=q1.front().first)q1.pop_front();
        if(i>=k)ans[0][cnt]=q.front().second,ans[1][cnt++]=q1.front().second;
    }
    for(int i=1;i<cnt;i++)printf("%d ",ans[1][i]);
    puts("");
    for(int i=1;i<cnt;i++)printf("%d ",ans[0][i]);
    return 0;
}

單調棧和單調隊列都是挖掘題目中的單調性，及時排除不可能，能保持序列的高度有效性和秩序性，能解決一些高級數據結構(如線段樹)才能解決的問題，值得我們思考

註意，deque和vector比較相似，最好降低常數，沒有氧氣，慎用deque

~~因為NOIP所以不講單調隊列優化多重背包~~

5.pair

這就是上面代碼中出現的pair~~(沒什麼好講的~~

二元組，尖括弧內為自己定義的類型，用.first()訪問第一元，用.second()訪問第二元，重載了<，第一元優先順序高於第二元

主要用於STL其他容器的存儲類型，如上面程式中雙端隊列的類型為一個二元組，第一元表示序號，第二元表示大小

6.priority_queue

優先隊列，通俗講就是沒素質，插隊

操作：

#include<queue>
priority_queue<int>q;//定義大根堆，即大的插隊
priority_queue<int,vector<int>,greater<int> >q;//定義小根堆，即小的插隊
q.push(x)//將x插入堆,O(logn)
q.pop()//堆頂出堆,O(logn)
q.top()//返回堆頂,O(1)

看完上面的操作，你想到了什麼呢？對，沒錯，它能動態維護序列的最值

堆能優化貪心，dijkstra，prim等演算法

但需要註意優先隊列存儲類型必須重載<。優先隊列不支持erase，這讓我們很蛋疼，解決方案為在刪除時，在堆外記錄(例如記錄元素最新值)，用於鑒別過時元素，在堆頂取出最值時，再檢查是不是過時的，若是，取下一個

例題1：洛谷 P1090 合併果子

思路就是每次取出兩個最小值合併，用堆維護

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

這就是堆優化貪心

例題2：洛谷P4779 【模板】單源最短路徑（標準版）

堆優化dijkstra

#include<bits/stdc++.h>
int x,y,n,m,k,u,v,w,head[1000001],dis[1000001],vis[1000001];
struct Edge{int next,to,w;}edge[1000001];
inline void dijkstra(int k){
    for(register int i=1;i<=n;++i)dis[i]=0x7fffffff,vis[i]=0;//初始化
    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;
    while(!q.empty()){
        x=q.top().second;q.pop();
        if(vis[x])continue;
        vis[x]=1;
        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));
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    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;
    dijkstra(k);
    for(register int i=1;i<=n;++i)printf("%d ",dis[i]);
    return 0;
}

~~毒瘤壓行~~

這就是堆優化dijkstra，O((n+m)logn)比某個~~死了的~~演算法好多了

7.string

字元串string，很多人不是很會使用它，其實它能在水掉很多字元串的題

基本操作：

#include<string>
#include<sstream>//stringstream頭文件
string s,s1;
stringstream ss(s);
ss>>s;
char c;
cin>>s//輸入
[],+,+=,>,<,>=,<=,==,!=,= //重載[]，從0開始編號，+連接兩個字元串，比較運算符從第一個字元開始比較，=賦值
getline(cin,s)//輸入一行
s.push_back(c)//字元串尾端加入字元c
s.append(c)//字元串尾端加入字元c
s.append(n,c)//在字元串尾端加入n個字元c
s.insert(it,c)//在迭代器it處插入c
s.substr(l,r)//返回l到r的字元串(前閉後開)
s.find(s1)//搜索字元串，返回第一次找到的位置，若沒找到返回-1
s.empty()//是否為空，為空返回1,否則返回0
s.erase(it)//清除迭代器it指向的元素
s.erase(it1,it2)//清除迭代器it1到it2之間的元素(前閉後開)
s.replace(a,len,str)//從a開始len個用str替換

常用操作就是這些了，find在一定程度上可以替代KMP，+和substr可以構造字元串~~只要不是模板題或數據卡你~~，就算時間複雜度是錯的，也能在你不會寫時騙到更多的分，且調試難度極低，純模擬至少能拿到分，只要你堅信，n^2過百萬，暴力碾標算，根據常數的優秀以及NOIP的水數據就有可能得到AC的好成績

你肯定會好奇stringstream是什麼，~~讓我來告訴你~~

試想一道題~~因為找不到這樣的題~~,輸入若幹個整數，求和

如果你會快讀，應該能寫出來，但是容易寫錯，也有點難理解，這裡提供一種解決方案,使用stringstream，很容易理解

#include<bits/stdc++.h>
string s;
int sum,x;
int main(){
    getline(std::cin,s);
    stringstream ss(s);
    while(ss>>x)sum+=x;
    printf("%d",sum);
    return 0;
}

現在理解stringstream了吧，它能將讀入的字元串變成其他類型的變數，或一行字元串變成空格分隔的多個字元串。但請註意，string很慢，stringstream更慢，所以還是那句話，沒有氧氣，慎用

綜上，有效地利用各種字元串處理函數和模擬，能使你的NOIP分數提高一個檔次

8.set和multiset

集合和可重集合，內部實現是一棵紅黑樹呵呵，但是常數較大使得它的效率較低

基本操作：

#include<set>
set<int>a;
multiset<int>b;
a.size(x)//返回大小,O(1)
a.empty()//返回是否為空，空返回1，否則返回0
a.clear()//清空，O(nlogn)
a.begin()//返回最小元素迭代器
a.end()//返回最大元素迭代器
a.insert(x)//插入x
a.find(x)//查找x，若存在返回指向該元素的迭代器，若不存在返回a.end(),O(logn)
a.lower_bound(x)//返回第一個大於等於x的元素的迭代器，O(logn)
a.upper_bound(x)//返回第一個大於x的元素的迭代器，O(logn)
a.erase(it)//刪除迭代器it指向的元素，O(logn)
a.erase(x)//刪除所有等於x的元素,O(k+logn),k為等於x的元素個數
if((it=s.find(x))!=s.end())s.erase(it);//可以只刪除一個等於x的元素
a.count(x)//返回元素個數，O(k+logn),k為等於x的元素個數

set能排序並去重，能方便地進行離散化等操作,還能用它實現珂朵莉樹。但註意，set，multiset和map的迭代器的只支持自增或自減且自增或自減的時間複雜度是O(logn)的，所以在使用時一定要註意

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

由於string重載了<，所以把非字母字元轉化為空格，再用stringstream得到單詞丟進set，排序且去重

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

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

例題2：洛谷 UVA136 Ugly Numbers

用優先隊列保存所有已生成的醜數，每次取最小x，生成2x，3x，5x插入堆中，註意一個醜數有多種生成方式，所以可以用set判斷是否已生成過

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

從上可以看出學會同時運用多個容器，融會貫通，能解決更多的題目。

9.map

map映射，它的內部實現也是一棵紅黑樹呵呵,同樣，也因為常數較大使得效率較低

基本操作

#include<map>
map<key，value>a;//建立一個key到value的映射，如map<string，int>a
a.size()//返回大小，O(1)
a.empty()//返回是否為空，空返回1，否則返回0,O(1)
a.clear()//清空,O(nlogn)
a.begin()//返回第一個元素的迭代器,O(1)
a.end()//返回最後一個元素的迭代器,O(1)
a.insert(pair<string,int>)//參數必須是pair,O(logn)
a.erase(pair<string,int>)//參數必須是pair或迭代器,O(logn)
a.erase(it)//O(logn)
a.find(x)//查找x，若存在返回指向key為x的二元組的迭代器,O(logn)
a[x]//重載了[],O(logn),需要註意，若x不存在，則會自動新建一個二元組(x,0或NULL)，強烈建議用[]之前，先用find()檢查存在性

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

例題1:洛谷 P3370 【模板】字元串哈希

用map不光能解決這道題，還能統計單詞的出現次數

#include<bits/stdc++.h>
std::map<std::string,int>a;
int n;
std::string s;
int main(){
    scanf("%d",&n);
    while(n--){
        std::cin>>s;
        if(a.find(s)==a.end())++a[s];//統計單詞的出現次數
    }
    printf("%d",a.size());
    return 0;
}

可以方便的代替hash表，但常數大，有時需要註意

例題2：洛谷 UVA156 Ananagrams

把每個單詞初始化，全部轉化成小寫在排序，然後丟進map統計

#include<bits/stdc++.h>
std::map<std::string,int>mp;
std::vector<std::string>a;
std::string s;
int n;
inline std::string init(const std::string &s){//初始化
    std::string ans=s;
    for(register int i=0;i<ans.size();++i)ans[i]=tolower(ans[i]);
    sort(ans.begin(),ans.end());
    return ans;
}
int main(){
    while(std::cin>>s&&s[0]!='#'){
        a.push_back(s);std::string s1=init(s);
        if(!mp.count(s1))mp[s1]=0;
        mp[s1]++;
    }
    std::vector<std::string>ans;
    for(register int i=0;i<a.size();++i)if(mp[init(a[i])]==1)ans.push_back(a[i]);
    sort(ans.begin(),ans.end());
    for(register int i=0;i<ans.size();++i)std::cout<<ans[i]<<std::endl;
    return 0;
}

此例說明，沒有良好的代碼設計，是無法發揮STL的威力的，如果沒有想到初始化，很難用map簡化代碼

10.bitset

bitset可看做多位二進位數，每8位占用一個位元組，相當於狀壓的bool數組，支持基本位運算，n位bitset執行一次位運算的複雜度可視為n/32，效率較高

#include<bitset>
bitset<1000001>s;//尖括弧中寫位數
~s//按位取反
&,|,^//按位與或，異或
<<,>> //左移右移
==,!= //比較是否相等
s[k]//表示第k位，從0開始
s.count()//返回多少位為1,O(n)
s.any()//若所有位為0返回0，否則返回1
s.none()//若所有位為0返回1，否則返回0
s.set()//所有位變為1
s.set(k,v)//把第k位變為v，即s[k]=v
s.reset()//把所有位變為0,
s.reset(k)//把第k為變為0，即s[k]=0
s.flip()//把所有位取反，即s=~s
s.flip(k)//把第k位取反，即s[k]^=1

例題

11.algorithm

STL的演算法庫，提供了

int a[1000001];
reverse(a+1,a+n+1);//翻轉1~n
int m=unique(a+1,a+n+1)-a-1;//m為去重後的元素個數
random_shuffle(a+1,a+n+1);//隨機打亂
do{
}next_permutation(a+1,a+n+1);//下一個排列，當不存在排名更靠後的排列返回0，否則返回1
sort(a+1,a+n+1);//快排
inline void cmp(const int &a,const int &b){return ...}
sort(a+1,a+n+1,cmp)//cmp自定義快排，返回值為1即交換
lower_bound(a+1,a+n+1,x)//返回第一個大於等於x的元素下標
upper_bound(a+1,a+n+1,x)//返回第一個大於x的元素下標

上述就是STL庫中的常用的函數，其中a數組可用vector，deque，string等容器替換

最後，祝大家NOIP2018 rp++