2011培訓(xùn)講義acm之stl篇ACM ICPC國際生程序設(shè)計競賽是以算法為主

01ACM/ICPC競賽之基礎(chǔ)篇一、ACM/ICPC競賽的特點ACM/ICPC競賽以組隊形式參賽，每個參賽隊由三名隊員組成，共同使用一臺計算機(jī)解題。通常每場比賽的試題為6至10題，根據(jù)各隊的完成題數(shù)和罰時進(jìn)行。題目提交通過稱一次，將增加20分鐘罰時。也就是說，參賽隊要盡可能用最快的速度、最少次數(shù)，intn;cin>>for(inti=0;i<n;{}EOF（文件結(jié)束標(biāo)志）作為結(jié)束標(biāo)志。如果從文EOFWindows的終端中，Ctrl+ZEOF。對于這種情況，可以用這樣的輸入模式：intmnwhile{處理整數(shù)對(m}Cintm,while(scanf("%d%d",&m,{處理整數(shù)對(m}1070（多項式求和）中，并未說明輸入多項式的項數(shù)，對這種情況就不宜用數(shù)組02ACM/ICPCSTLSTL，可以在代碼空間、執(zhí)行時間和編碼效率上獲得極大的好處。stable_sort（穩(wěn)定排序）。STLCSTL算法STL中的每一個容器也都定義了其本身所STLSTL，我們STLACMSTL對快速編寫實現(xiàn)代碼會有極大的幫助。STLC++標(biāo)準(zhǔn)中，STL被組織為以下的一組頭文件（注意，沒有.h后綴algorithm/deque/functional/itor/list/mapmemory/numeric/queue/set/stack/utility/vectorSTLC++標(biāo)準(zhǔn)中，STLstd命名空間中的。如下例所示：#include<stack>{std::stack<int>s;return}如果希望在程序中直接STL，也可以在嵌入頭文件后，用usingnamespace語句將#include<stack>usingnamespacestd;{stack<int>s;return}STLC++STLC++語言的思想和STLSTL的基本應(yīng)用。有的同學(xué)，建議可以在有了一些STL的使用經(jīng)驗后，認(rèn)真閱讀一下《C++STL》這本03ACM/ICPCSTL--STL的<utility>pair，用來表示一個二元組或pair<double,double>cin>>p1.first>>pair模板類需要兩個參數(shù)：首元素的數(shù)據(jù)類型和尾元素的數(shù)據(jù)類型。pair模板類對象有兩個成員：firstsecond，分別表示首元素和尾元素。first，firstsecond，這符合大多數(shù)應(yīng)用的邏輯。second表示結(jié)點是由父結(jié)點乘以哪一個因子得到的。#include<iostream>#include<queue>usingnamespacestd;typedefpair<unsignedlong,int> unsignedlongpriority_queue<node_type,vector<node_type>,greater<node_type>>Q;Q.push(make_pair(1,2));for(inti=0;i<1500;{node_typenode=Q.top(); case2:Q.push(make_pair(node.first*2,2));case3:Q.push(make_pair(node.first*3,3)case5:Q.push(make_pair(node.first*5,5)}result[i]=}intn;cin>>n;while(n>0)cout<<result[n-1]<<endl;cin>>n;}return}04ACM/ICPCSTL—式元素序列，可以將vector看作是以順序結(jié)構(gòu)實現(xiàn)的線性表。當(dāng)我們在程序中需要使用動態(tài)數(shù)組時，vector將會是理想的選擇，vector可以在使用過程中vectorvector<int>s;定義一個空的vector對象，的是int類型的元素vector<int>s(n);n個intvectorvector<int>s(first,last);vectorfirstlast定義的序列[first,lavector 直接以下標(biāo)方式容器中的元素 s.push_back(x)向表入元素x。 s.insert(it,x) 向迭代器it指向的元素前插入新元素val。s.insert(it,n,x)向迭代器it指向的元素前插入n個x。s.insert(it,first,last)將由迭代器first和last所指定的序列[first,last)插入到迭代器it指向的元 s.erase(first,last) 刪除由迭代器first和last所指定的序列[first,last)。 預(yù)分配緩沖空間，使空間至少可容納n個元素。 （s.resize(nval)改變序列的長度，超出的元素將會被刪除，如果序列需要擴(kuò)展（n），vals.clear() svectorvs.assign(first, firstlast所指定的序列[first,last)。[first,另外，vectorvector上還定義了序列之間的比較操作運算符，可以按照字典序比較兩#include<iostream>#include<vector>usingnamespacestd;{vector<int>L;intx;while(cin>>x)for(inti=L.size()-1;i>=0;i--)cout<<L[i]<<"";cout<<endl;return}第05篇ACM/ICPC競賽之STL--itor簡數(shù)據(jù)結(jié)構(gòu)中所說的“遍歷指針”，也可以把itor(迭代器)看作是一種泛化的指針。STL中關(guān)于itor(迭代器)的實現(xiàn)是相當(dāng)復(fù)雜的這里我們暫時不去詳細(xì)討論關(guān)于itor(迭代器)的實現(xiàn)和使用，而只對itor(迭代器)做一點簡單的介紹。簡單地說，STL中有以下幾類itor(迭代器輸出itor(迭代器)，把值寫進(jìn)它所指向的容器中；雙向i 隨 itor(迭代器),可以直接以下標(biāo)方式對容器進(jìn)行，vector的itor(迭代器就是這種itor(迭代器每種STL容器都有自己的itor(迭代器)子類，下面先來看一段簡單的示例代碼#include<iostream>#include<vector>usingnamespacestd;{vector<int>for(inti=0;i<10;i++)for(vector<int>::itorit=s.begin();it!=s.end();it++)cout<<*it<<"";cout<<endl;return1;}vector的begin()和end()方法都會返回一個vector::itor對象，分別指向vector的首元素位就是一個非常標(biāo)準(zhǔn)的itor(迭代器)。#include<iostream>#include<vector>usingnamespacestd;{vector<int>s;copy(s.begin(),s.end(),ostream_itor<int>(cout,""));cout<<endl;return}這段代碼中的copy就是STL中定義的一個模板函數(shù)，copy(s.begin(),s.end(),ostream_itocout中，用""作為每個元素的間隔。也就是說，這句話的作用其實就是將表中的所有內(nèi)itor(迭代器)是STL容器和算法之間的“膠合劑”，幾乎所有的STL算法都是通過容器的itor(迭代器)來容器內(nèi)容的。只有通過有效地運用itor(迭代器)，才能夠有效地運用STL強(qiáng)大的算能。06ACM/ICPCSTL--string類對象還支持字符串的拼合、轉(zhuǎn)換等操作。#include<iostream>#include<string>usingnamespacestd;{strings="o!",name;cin>>name;s+=name;s+='!';cout<<s<<endl;return1;}intcinmPstringstr;用來存放還原出來的括號字符串intleftpa=0;//記錄已出現(xiàn)的左括號的總數(shù)for(intj=0;j<m;j++){intcin>>for(intk=0;k<p-leftpa;k++)str+='(';str+=')';leftpa=}#include<iostream>#include<queue>usingnamespacestd;classT{intx,y,T(inta,intb,intc):x(a),y(b),z(c){booloperator<(constT&t1,constT{returnt1.zt2.z;zt1t2}{priority_queue<T>q;while(!q.empty())Tt=q.top();cout<<t.x<<""<<t.y<<""<<t.z<<}return}輸出結(jié)果為(z的順序從大到小出隊的33221544z#include<iostream>#include<queue>usingnamespacestd;classT{intx,y,T(inta,intb,intc):x(a),y(b),z(c){booloperator>(constT&t1,constT{returnt1.z>}{priority_queue<T,vector<T>,greater<T>>q;while(!q.empty())Tt=q.top();cout<<t.x<<""<<t.y<<""<<t.z<<}return}44152233booloperator<(constT&t1,constT{returnt1.z zt1t2}1067--UglyNumbers的代碼：#include<iostream>#include<queue>usingnamespacestd;typedefpair<unsignedlongint,int>node_type;main(intargc,char*argv[]){unsignedlongintpriority_queue<node_type,vector<node_type>,greater<node_type>>Q;Q.push(make_pair(1,3));for(inti=0;i<1500;i++) node_typenode=Q.top(); case3:Q.push(make_pair(node.first*2,3)case2:Q.push(make_pair(node.first*3,2)case1:Q.push(make_pair(node.first*5,1)}result[i]=}intcin>>n;while(n>0){cout<<result[n-1]<<endl;cin>>n;}return}08ACM/ICPCSTL--STL的頭文件<map>map和multimap<constKey,T>constKey部分作為標(biāo)識，mapKey值都必須是唯一的，multimapKeymapKey標(biāo)識元素的元素集合，這類容器也被稱為“關(guān)聯(lián)容器”，可以通過KeyKey值查找元素的容器。mapmap1mapmap<string,int>2mapm[key]=[key]操作是mapmapkey的元素對，則返回該元素map中插入元素對或修改已經(jīng)存在的元素對的值域部分。m.insert(make_pair(key,value)insert方法插入元素對，insertpairmap中沒有與keyfirstsecondtruemap中已經(jīng)存keyfirst是指向該元素對的迭代器，secondi=m[key];keymap<string,int>::itorit=map的end()（參見vectorbeginend操作）。m.erase(key);刪除與指定key鍵值相匹配的元素對，并返回被刪除的元素的個數(shù)。m.erase(it);it所指定的元素對，并返回指向下一個元素對的迭代器。usingnamespacestd;typedefmap<int,string,less<int>>M_TYPE;typedefM_TYPE::itorM_IT;typedefM_TYPE::const_itorM_CIT;intmain(){M_TYPEMyTestMap[3]="No.3";MyTestMap[5]="No.5";MyTestMap[1]="No.1";MyTestMap[2]="No.2";MyTestMap[4]=M_ITit_stop=cout<<"MyTestMap[2]="<<it_stop->second<<endl;it_stop->second="No.2Aftermodification";cout<<"MyTestMap[2]="<<it_stop->second<<endl;cout<<"Mapcontents:"<<endl;for(M_CITit=MyTestMap.begin();it!=MyTestMap.end();it++){cout<<it->second<<endl;}return}MyTestMap[2]=MyTestMap[2]=No.2AftermodificationMapcontents:No.2Aftermodification#include<iostream>#include<map>usingnamespacestd;{map<string,int>m;m["one"]=1;m["two"]=insertstringwhile(cin>>key)map<string,int>::itorit=if(it==m.end())cout<<"Nosuchkey!"<<}elsecout<<key<<"is"<<it->second<<endl;cout<<"Erased"<<m.erase(key)<<endl;}}return}09ACM/ICPCSTL—<algorithm>STL中最大的一個頭文件，它是由一大堆模板函數(shù)組成的。adjacent_find/binary_search/copy/copy_backward/count/count_if/equal/equal_range/fill/fill_n/find/find_end/find_first_of/find_if/for_each/generate/generate_n/includes/inplace_merge/iter_swap/l pare/lower_bound/make_heap/max/max_element/merge/min/min_element/mismatch/next_permutation/nth_element/partial_sort/_sort_copy/partition/pop_heap/prev_permutation/push_heap/random_shuffle/remove/remove_copy/remove_copy_if/remove_if/rece/rece_copy/rece_copy_if/rece_if/reverse/reverse_copy/rotate/rotate_copy/search/search_n/set_difference/set_intersection/set_symmetric_difference/set_union/sort/sort_heap/stable_partition/stable_sort/swap/swap_ranges/transform/unique/unique_copy/upper_bound示例程序之一:for_each遍歷容器：#include<iostream>#include<vector>#include<algorithm>usingnamespaceintVisit(intv){cout<<v<<"";return1;}classMultInt{intfactor;MultInt(intf):factor(f){voidoperator()(int&elem)const{elem*=factor;}{vector<int>for(inti=0;i<10;i++)L.push_back(i);for_each(L.begin(),L.end(),Visit);cout<<endl;for_each(L.begin(),L.end(),Visit);cout<<endl;return}0123456780246810121416示例程序之二:min_element/max_element，找出容器中的最小/最大值：#include<iostream>#include<vector>#include<algorithm>usingnamespace{vector<int>for(inti=0;i<10;i++)vector<int>::itormin_it=min_element(L.begin(),L.end());vector<int>::itormax_it=max_element(L.begin(),L.end());cout<<"Minis"<<*min_it<<endl;cout<<"Maxis"<<*max_it<<endl;return1;}MinisMaxis示例程序之三:sort#include<iostream>#include<vector>#include<algorithm>usingnamespacevoidPrint(vector<int>{for(vector<int>::itorit=L.begin();it!=L.end();it++)cout<<*it<<"";cout<<}{vector<int>for(inti=0;i<5;i++)L.push_back(i);for(inti=9;i>=5;i--)L.push_back(i);sort(L.begin(),L.end());),());//return}012349876012345678987654321示例程序之四 copy在容器間元素#include<vector>#include<algorithm>#include<iostream>usingnamespacestd;main(){v1和v2vector<int>v1,v2;for(inti=0;i<=5;i++)v1.push_back(10*i);for(inti=0;i<=10;i++)cout<<"v1=("for(vector<int>::itorit=v1.begin();it!=v1.end();it++)cout<<*it<<"";cout<<")"<<cout<<"v2=("for(vector<int>::itorit=v2.begin();it!=v2.end();it++)cout<<*it<<"";cout<<")"<<//將v1的前三個元素到v2的中copy(v1.begin(),v1.begin()+3,cout<<"v2withv1insert=("for(vector<int>::itorit=v2.begin();it!=v